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

「点点赞赏,手留余香」

1

给作者打赏,鼓励TA抓紧创作!

微信微信 支付宝支付宝

还没有人赞赏,快来当第一个赞赏的人吧!

声明:本站所有资源及文章均来源于网络及用户分享或为本站原创,仅限用于学习和研究,任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。
码云笔记 » JavaScript数据结构之哈希表的封装

发表评论

IT互联网行业相关广告投放 更专业 更精准

立即查看 联系我们