JavaScript数据结构之哈希表的封装

JavaScript 数据结构之哈希表的封装

function HashTable() {
    this.storage = [] this.count = 0 this.limit = 7

    HashTable.prototype.hashFunc = function(str, size) {
        var hashCode = 0
        for (var i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i)
        }
        var index = hashCode % size
        return index
    }
    HashTable.prototype.put = function(key, value) {
        var index = this.hashFunc(key, this.limit) var bucket = this.storage[index]
        if (bucket == null) {
            bucket = [] this.storage[index] = bucket
        }
        for (var i = 0; i < bucket.length; i++) {
            var tuple = bucket[i]
            if (tuple[0] == key) {
                tuple[1] = value
                return
            }
        }
        bucket.push([key, value]) this.count++
        if (this.count > this.limit * 0.75) {
            var newSize = this.limit * 2
            var newPrime = this.getPrime(newsize) this.resize(newPrime)
        }
    }
    HashTable.prototype.get = function(key) {
        var index = this.hashFunc(key, this.limit) var bucket = this.storage[index]
        if (bucket == null) return null
        for (var i = 0; i < bucket.length; i++) {
            var tuple = bucket[i]
            if (tuple[0] == key) return tuple[1]
        }
        return null
    }
    HashTable.prototype.delete = function(key) {
        var index = this.hashFunc(key, this.limit) var bucket = this.storage[index]
        if (bucket == null) return null
        for (var i = 0; i < bucket.length; i++) {
            var tuple = bucket[i]
            if (tuple[0] == key) {
                bucket.splice(i, 1) this.count--
                return tuple[1]
                if (this.limit > 7 && this.count < this.limit * 0.25) {
                    var newSize = Math.floor(this.limit / 2) var newPrime = this.getPrime(newSize) this.resize(newPrime)
                }
            }
        }
        return null
    }
    HashTable.prototype.isEmpty = function() {
        return this.count == 0
    }
    HashTable.prototype.size = function() {
        return this.count
    }
    HashTable.prototype.resize = function(newLimit) {
        var oldStorage = this.storage this.storage = [] this.count = 0 this.limit = newLimit
        for (var i = 0; i < oldStorage.length; i++) {
            var bucket = oldStorage[i]
            if (bucket == null) {
                continue
            }
            for (var j = 0; j < bucket.length; j++) {
                var tuple = bucket[j] this.put(tuple[0], tuple[1])
            }
        }
    }
    HashTable.prototype.isPrime = function(num) {
        var temp = parseInt(Math.sqrt(num)) for (var i = 2; i <= temp; i++) {
            if (num % i == 0) return false
        }
        return true
    }
    HashTable.prototype.getPrime = function(num) {
        while (!this.isPrime(num)) {
            num++
        }
        return num
    }
}
var ht = new HashTable() ht.put('abc', '111') ht.put('eee', '444') ht.delete('eee') console.log(ht);

以上关于JavaScript数据结构之哈希表的封装的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。