散列的實(shí)現(xiàn)
// 散列類 - 線性探測(cè)法
function HashTable () {
this.table = new Array(137);
this.values = [];
this.simpleHash = simpleHash;
this.betterHash = betterHash;
this.showDistro = showDistro;
this.put = put;
this.get = get;
}
function put (key, data) {
let pos = this.betterHash(key);
// this.table[pos] = data;
if (this.table[pos] === undefined) {
this.table[pos] = key;
this.values[pos] = data;
} else {
while (this.table[pos] !== undefined) {
++pos;
}
this.table[pos] = key;
this.values[pos] = data;
}
}
function get (key) {
// return this.table[this.betterHash(key)];
let hash = -1;
hash = this.betterHash(key);
if (hash > -1) {
for (let i = hash; this.table[hash] !== undefined; ++i) {
if (this.table[hash] === key) {
return this.values[hash];
}
}
}
return undefined;
}
function simpleHash (data) {
let total = 0;
for (let i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
return total % this.table.length;
}
function showDistro () {
let n = 0;
for (let i = 0; i < this.table.length; ++i) {
if (this.table[i] !== undefined) {
console.log(`${i}: ${this.table[i]}`);
}
}
}
function betterHash (string) {
const H = 7;
let total = 0;
for (let i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length -1;
}
return parseInt(total, 10);
}
練習(xí)
使用線性探測(cè)法創(chuàng)建一個(gè)字典把沼，用來保存單詞的定義。該程序需要包含兩個(gè)部分：第一部分將一組單詞和它們的定義存儲(chǔ)進(jìn)散列表吁伺；第二部分讓用戶輸入單詞饮睬，程序給出該單詞的定義。
// 字典類
function Dict () {
this.hashTable = new HashTable();
this.save = save;
this.find = find;
}
function save (word, description) {
this.hashTable.put(word, description);
}
function find (word) {
return this.hashTable.get(word);
}
// 示例
let d = new Dict();
d.save('Mazey', 'a strong man.');
d.save('Cherrie', 'a beautiful girl.');
d.save('John', 'unknown.');
console.log(d.find('John')); // unknown.
console.log(d.find('Mazey')); // a strong man.
console.log(d.find('Ada')); // undefined
