哈希表

[conan1992]

哈希表

• 数组为基础
• 哈希函数
• 均匀分布

实现

function hashFunc(str, max) {
    // 1.初始化hashCode的值
    var hashCode = 0

    // 2.霍纳算法, 来计算hashCode的数值
    for (var i = 0; i < str.length; i++) {
        hashCode = 37 * hashCode + str.charCodeAt(i)
    }
    console.log( hashCode )
    // 3.取模运算
    hashCode = hashCode % max
    return hashCode
}
function HashTable(){
    this.storage = [];
    this.count = 0;
    this.limit = 8;
}
HashTable.prototype.hashFunc = hashFunc;
HashTable.prototype.put = function(key, value){
    var index = this.hashFunc(key, this.limit)
    console.log(index)
    var bucket = this.storage[index];
    if(!bucket){
        bucket = [];
        this.storage[index] = bucket;
    }
    var override = false;
    for(var i=0;i<bucket.length;i++){
        var tuple = bucket[i];
        if(tuple[0]===key){
            tuple[1] = value;
            override = true;
        }
    }
    if(!override){
        bucket.push([key, value])
        this.count++;
        //判断是否需要扩容--0.75装填因子
        if(this.count > this.limit*0.75){
            this.resize( this.limit*2 )
        }
    }
    return true
}
HashTable.prototype.get = function(key){
    var index = this.hashFunc(key, this.limit)
    var bucket = this.storage[index];
    if(!bucket){
        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.remove = function(key){
    var index = this.hashFunc(key, this.limit)
    var bucket = this.storage[index];
    if(!bucket){
        return null;
    }

    for(var i=0;i<bucket.length;i++){
        var tuple = bucket[i];
        if(tuple[0]===key){
            bucket.splice(i, 1)
            this.count--;
            //判断是否需要缩小容量 --0.75装填因子
            if(this.count < this.limit*0.25){
                this.resize( this.limit*2 )
            }
            return tuple[1]
        }
    }
    return null
}
//扩容
HashTable.prototype.resize = function(newLimit){
    this.limit = newLimit;
    var oldStorage = this.storage;
    this.storage = [];
    this.count = 0;
    var oldStorageLength = oldStorage.length
    for(var i=0;i<oldStorageLength;i++){
        var bucket = oldStorage[i]
        if(bucket){
            for(var j=0;j<bucket.length;j++){
                let tuple = bucket[j]
                this.put(tuple[0], tuple[1])
            }
        }
    }
}
var hashTable = new HashTable();
hashTable.put('name', "吉良吉影")
hashTable.resize(10)
console.log(hashTable, hashTable.get('name1'))

参考链接

• 数据结构(十)之哈希表实现