散列算法的作用是尽可能快地在数据结构中找到一个值。
散列函数的作用是给定一个键值，然后返回值在表中的地址。
class ValuePair { //用于存放一对键值对
constructor(key, value) {
this.key = key;
this.value = value;
}
toString() {
return `[#${this.key}:${this.value}]`;
}
}
class HashTable {
constructor() {
this.table = {};
}
toStrFn(str) {
if (str === null) {
return 'null';
} else if (str === undefined) {
return 'undefined';
} else {
return str.toString();
}
}
loseloseHashTable(key) { //散列函数
if (typeof key === 'number') { //key如果是数值直接返回
return key;
}
let hash = 0; //用来储存每个字符的ASCII码之和
const tableKey = this.toStrFn(key);
for (let i = 0; i < tableKey.length; i++) {
hash += tableKey.charCodeAt(i);
}
return hash % 37; //为了得到一个比较小的值
}
hashCode(key) {
return this.loseloseHashTable(key);
}
put(key, value) {
if (key == null || value == null) { //检验key和value是否合法
return false;
}
const position = this.hashCode(key);
this.table[position] = new ValuePair(key, value); //为了信息备份将key保存下来
return true;
}
get(key) {
let valuePair = this.table[this.hashCode(key)];
return valuePair == null ? undefined : valuePair.value;
}
remove(key) {
if (this.table[this.hashCode(key)] != null) {
delete this.table[this.hashCode(key)];
return true;
}
return false;
}
size() {
return Object.keys(this.table).length;
}
isEmpty() {
return this.size() === 0;
}
toString() {
if (this.isEmpty()) {
return "";
}
let keys = Object.keys(this.table);
let objString = `{${keys[0]}=>${this.table[keys[0]]}}`;
for (let i = 1; i < keys.length; i++) {
objString = `${objString},{${keys[i]}=>${this.table[keys[i]]}}`;
}
return objString;
}
}
//测试用例
const hash = new HashTable();
console.log(hash.hashCode('Gandalf') + ' - Gandalf');
console.log(hash.hashCode('John') + ' - John');
console.log(hash.hashCode('Tyrion') + ' - Tyrion');
console.log(' ');
console.log(hash.hashCode('Ygritte') + ' - Ygritte');
console.log(hash.hashCode('Jonathan') + ' - Jonathan');
console.log(hash.hashCode('Jamie') + ' - Jamie');
console.log(hash.hashCode('Jack') + ' - Jack');
console.log(hash.hashCode('Jasmine') + ' - Jasmine');
console.log(hash.hashCode('Jake') + ' - Jake');
console.log(hash.hashCode('Nathan') + ' - Nathan');
console.log(hash.hashCode('Athelstan') + ' - Athelstan');
console.log(hash.hashCode('Sue') + ' - Sue');
console.log(hash.hashCode('Aethelwulf') + ' - Aethelwulf');
console.log(hash.hashCode('Sargeras') + ' - Sargeras');
hash.put('Ygritte', 'ygritte@email.com');
hash.put('Jonathan', 'jonathan@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Jack', 'jack@email.com');
hash.put('Jasmine', 'jasmine@email.com');
hash.put('Jake', 'jake@email.com');
hash.put('Nathan', 'nathan@email.com');
hash.put('Athelstan', 'athelstan@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Aethelwulf', 'aethelwulf@email.com');
hash.put('Sargeras', 'sargeras@email.com');
console.log('**** Printing Hash **** ');
console.log(hash.toString());
// {4 => [#Ygritte: ygritte@email.com]},{5 => [#Aethelwulf: aethelwulf@email.com]},{7 => [#Athelstan: athelstan@email.com]},{8 => [#Jasmine: jasmine@email.com]},{9 => [#Jake: jake@email.com]},{10 => [#Sargeras: sargeras@email.com]}
console.log('**** Get **** ');
console.log(hash.get('Ygritte')); // ygritte@email.com
console.log(hash.get('Loiane')); // jasmine@email.com
console.log('**** Remove **** ');
hash.remove('Ygritte');
console.log(hash.get('Ygritte')); // undefined
console.log(hash.toString());
// {5 => [#Aethelwulf: aethelwulf@email.com]},{7 => [#Athelstan: athelstan@email.com]},{8 => [#Jasmine: jasmine@email.com]},{9 => [#Jake: jake@email.com]},{10 => [#Sargeras: sargeras@email.com]}