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);