哈希表

[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'))

参考链接

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