<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>哈希表的封装</title>
</head>
<body>
<script>
function hashFunc(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;
}
function HashTable() {
this.storage = [];
this.count = 0;
this.limit = 7 * 2;
//方法
HashTable.prototype.put = function (key, value) {
//根据key获取对应的index
var index = this.hashFunc(key, this.limit);
//根据index取出对应的bucket
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 += 1;
//判断是否需要扩容
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);
//根据index取出对应的bucket
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.remove = function (key) {
var index = this.hashFunc(key, this.limit);
//根据index取出对应的bucket
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) {
this.resize(Math.floor(this.limit / 2));
}
}
}
return null;
};
HashTable.prototype.isEmpty = function (key) {
return this.count == 0;
};
HashTable.prototype.size = function (key) {
return this.count;
};
HashTable.prototype.resize = function (key) {
var oldStorage = this.storage;
//重置所有的属性
this.storage = [];
this.count = 0;
this.limit = newLimit;
for (var i = 0; i < bucket.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
}
}
</script>
</body>
</html>