javascript - 使用javascript实现哈希表
问题描述
我正在尝试使用 javascript 实现哈希表。目前,到目前为止一切正常,但我的 get 方法在给定特定键的情况下检索哈希表中的值时遇到问题。我正在使用线性探测以避免碰撞。当我散列键“Alejandro”时,我将键映射到 0 索引。然后我将它添加到我的哈希表中。然后我尝试“Rosalby”,它也映射到 0 索引。我使用线性探测来查找下一个可用插槽,在我的情况下,空索引是 1,我将 Rosalby 的值放在该插槽中。到目前为止,我似乎很好地管理了我的碰撞。然而; 当我尝试在我的 get 方法中获取值时,我无法获得正确的值,这就是我的哈希表的样子。
另外,我想提一下,我已经使哈希表的大小更大了,并且在给定特定键的情况下我得到了正确的值,这仅仅是因为我没有冲突。先感谢您。
// Hash table implementation
class HashTable {
// constructor functio
constructor(size) {
this.size = size;
this.buckets = this.initArray(size);
this.limit = 0;
}
// init array function
initArray(size) {
// init an array
const array = [];
// populate the array base on the size
for (let i = 0; i < size; i++) {
// push null to the array
array.push(null);
}
// return the array
return array;
}
// mapping key to index
hash(key) {
let total = 0;
// get unique code of character in the string
for (let i = 0; i < key.length; i++) {
let keyCode = key.charCodeAt(i)
// console.log("Key code:", keyCode)
// sum up the unique code
total += keyCode;
// console.log(total);
}
// mod the total to the size of the hash table
const hashIndex = total % this.size;
// return that index
return hashIndex;
}
// put method
put(key, value) {
// throw an erro if hashTable is full
if (this.limit >= this.size) throw "Hash Table is full";
// hash the key
let hashIndex = this.hash(key);
// console.log(hashIndex);
// linear probing
while (this.buckets[hashIndex] != null) {
hashIndex++;
hashIndex = hashIndex % this.size;
}
// add the value at that key to the buckets array
this.buckets[hashIndex] = value;
// increase the limit
this.limit++;
}
// get method
get(key) {
// hash the key
let hashIndex = this.hash(key);
let value = this.buckets[hashIndex];
// return the value at that index
return value;
}
} // end of hash table
// sanity check
const ht = new HashTable(3);
console.log(ht);
// ht.hash("Rosalby");
console.log();
ht.put("Alejandro", "555-5555");
ht.put("Rosalby", "123-1231");
ht.put("Lalaland", "000-0000");
// ht.put("Lalaland", "919-1919");
console.log();
console.log(ht);
console.log("Alejandro:", ht.get("Alejandro"), "Rosalby:", ht.get("Rosalby"), "Lalaland:", ht.get("Lalaland"));
解决方案
这是哈希表的快速工作实现:
class HashTable
{
constructor(getHash)
{
if(!getHash) throw "Argument is null: getHash";
this.getHash = getHash;
this.buckets = {};
this._count = 0;
}
// throws an exception if the key already exists
add(key, value)
{
const hashCode = this.getHash(key);
const bucket = this.buckets[hashCode];
if(!bucket)
{
this.buckets[hashCode] = [{key, value}];
++this._count;
return;
}
for(let length = bucket.length, i = 0; i < length; ++i)
{
const item = bucket[i];
if(item.key == key) throw "Duplicate key.";
}
bucket.push({key, value});
++this._count;
}
// replaces the value if the key already exists
set(key, value)
{
const hashCode = this.getHash(key);
const bucket = this.buckets[hashCode];
if(!bucket)
{
this.buckets[hashCode] = [{key, value}];
++this._count;
return;
}
for(let length = bucket.length, i = 0; i < length; ++i)
{
const item = bucket[i];
if(item.key == key)
{
item.value = value;
return;
}
}
bucket.push({key, value});
++this._count;
}
get(key, defaultValue)
{
const hashCode = this.getHash(key);
const bucket = this.buckets[hashCode];
if(!bucket) return defaultValue;
for(let length = bucket.length, i = 0; i < length; ++i)
{
const item = bucket[i];
if(item.key == key) return item.value;
}
return defaultValue;
}
has(key)
{
const hashCode = this.getHash(key);
const bucket = this.buckets[hashCode];
if(!bucket) return false;
for(let length = bucket.length, i = 0; i < length; ++i)
{
const item = bucket[i];
if(item.key == key) return true;
}
return false;
}
get count()
{
return this._count;
}
}
HashTable.unitTests = function()
{
function getHash(value)
{
const stringValue = String(value);
let result = 0;
for(let length = stringValue.length, i = 0; i < length; ++i) result ^= stringValue.charCodeAt(i);
return result;
}
let ht;
// empty
ht = new HashTable(getHash);
if (ht.count != 0) throw "failed";
if (ht.has(null)) throw "failed";
if (ht.has("")) throw "failed";
if (ht.get(null) != void (0)) throw "failed";
if (ht.get("") != void (0)) throw "failed";
if (ht.get(null, 1) != 1) throw "failed";
// add new
ht = new HashTable(getHash);
ht.add("a", 1);
if (ht.count != 1) throw "failed";
if (!ht.has("a")) throw "failed";
if (ht.get("a") != 1) throw "failed";
// set new
ht = new HashTable(getHash);
ht.set("a", 1);
if (ht.count != 1) throw "failed";
if (!ht.has("a")) throw "failed";
if (ht.get("a") != 1) throw "failed";
// add duplicate
ht = new HashTable(getHash);
ht.add("a", 1);
try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }
// add+set duplicate
ht = new HashTable(getHash);
ht.add("a", 1);
ht.set("a", 1);
if (ht.count != 1) throw "failed";
if (!ht.has("a")) throw "failed";
if (ht.get("a") != 1) throw "failed";
// set+add duplicate
ht = new HashTable(getHash);
ht.set("a", 1);
try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }
// set duplicate
ht = new HashTable(getHash);
ht.set("a", 1);
ht.set("a", 1);
if (ht.count != 1) throw "failed";
if (!ht.has("a")) throw "failed";
if (ht.get("a") != 1) throw "failed";
// add multiple
ht = new HashTable(getHash);
ht.add("a", 1);
ht.add("b", 2);
if (ht.count != 2) throw "failed";
if (!ht.has("a")) throw "failed";
if (!ht.has("b")) throw "failed";
if (ht.get("a") != 1) throw "failed";
if (ht.get("b") != 2) throw "failed";
// add with collision
ht = new HashTable(getHash);
ht.add("ab", 1); // hash code 3
ht.add("ba", 2); // hash code 3
if (ht.count != 2) throw "failed";
if (!ht.has("ab")) throw "failed";
if (!ht.has("ba")) throw "failed";
if (ht.get("ab") != 1) throw "failed";
if (ht.get("ba") != 2) throw "failed";
// set with collision
ht = new HashTable(getHash);
ht.set("ab", 1); // hash code 3
ht.set("ba", 2); // hash code 3
if (ht.count != 2) throw "failed";
if (!ht.has("ab")) throw "failed";
if (!ht.has("ba")) throw "failed";
if (ht.get("ab") != 1) throw "failed";
if (ht.get("ba") != 2) throw "failed";
}
HashTable.unitTests();
console.log("OK");
<html>
<head>
<script src="HashTable.js"></script>
</head>
<body>
</body>
</html>
一些澄清:
- 散列函数是有意作为散列表的配置提供的;使类更可重用;
- 使用 this._count 是实施容量限制的更好方法(但未实现,但易于添加);
- 单元测试可以扩展更多。不过,我们这里的内容足以证明 HashTable 类是可操作的;
- ^ 运算符(按位异或)通常提供生成的哈希码的更好分布。请参阅为什么在 java hashCode() 中经常使用 XOR,但很少使用另一个位运算符?.
推荐阅读
- python - 带有环境变量的 if-else
- c++ - 使用 boost::gil 编写 jpeg 文件
- javascript - 我应该使用什么方法来使用 React Native 在本地存储数据集合?
- python - Python 替换函数中的“搜索”参数是否有限制?
- c++ - CDialogEx 构造函数和继承的 Create() 方法
- reactjs - 在 useEffect React 钩子中清理异步函数
- javascript - 为什么我的 javascript 显示此错误,Uncaught ReferenceError: getElementsByClassName is not defined?
- python-3.x - 是否可以在不重新启动 Selenium webdriver 的情况下更改代理?
- reactjs - 连接的 React 路由器 - 不要更新视图
- testing - 如何在视频捕捉应用中测试贴纸和效果?