散列表也称哈希表，散列算法的作用是尽可能快地在数据结构中找到一个值。
如果要在数据结构中获得一个值，需要迭代整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。
散列函数的作用是给定一个键值，然后返回值在表中的地址。
function defaultToString(item){ // 将键转化为字符串 if(item === null){ return ‘NULL‘ }else if(item === undefined){ return ‘UNDEFINED‘ }else{ return item.toString() } }
class valuePair{
// 键值对 constructor(key, value){ this.key = key this.value = value } toString(){ return `[#${this.key}: ${this.value}]` } } class hashTable{ constructor(toStrFn = defaultToString){ this.toStrFn = toStrFn this.table = {} } loseloseHashCode(key){ // 使用loselose散列函数 // 即将每个键中的每个字母的ASCII码相加 if(typeof(key) === "number"){ return key } const tableKey = this.toStrFn(key) let Hash = 0 for(let i=0; i<tableKey.length; i++){ Hash += tableKey.charCodeAt(i) } return Hash % 37 } hashCode(key){ return this.loseloseHashCode(key) } put(key, value){ // 添加键值对 if(key != null && value != null){ const position = this.hashCode(key) this.table[position] = new valuePair(key, value) return true } return false } get(key){ // 通过key查找值, 找不到返回undefined const valuePair = this.table[this.hashCode(key)] return valuePair } }
如下图：
class HashTableSeparateChaining extends hashTable{ constructor(toStrFn = defaultToString){ super(toStrFn) } put(key, value){ // 每个元素为一个链表,依次存储相同hashcode的键值对 if(key != null && value != null){ const position = super.hashCode(key) if(this.table[position] == undefined){ this.table[position] = new LinkedList() // LinkedList类详见链表 } this.table[position].push(new valuePair(key, value)) return true } return false } get(key){ // 通过key获取value const position = super.hashCode(key) const linkedList = this.table[position] if (linkedList != undefined && !linkedList.isEmpty()) { let current = linkedList.getHead() while(current != null){ if(current.element.key === key){ return current.element.value } current = current.next } } return undefined } remove(key){ // 通过key移除对应元素 const position = super.hashCode(key) const linkedList = this.table[position] if(linkedList != undefined && !linkedList.isEmpty()){ let current = linkedList.getHead() while(current != null){ if(current.element.key === key){ linkedList.remove(current.element) if(linkedList.isEmpty()){ delete this.table[position] } return true } current = current.next } } return false } }
class HashTableSeparateChaining extends hashTable{ constructor(toStrFn = defaultToString){ super(toStrFn) } put(key, value){ // 插入元素 // 先判断位置是否被占用，插入一个未被占用的位置 if(key != null && value != null){ const position = super.hashCode(key) if(this.table[position] == undefined){ this.table[position] = new valuePair(key, value) }else{ let index = position + 1 while(this.table[index] != undefined){ index ++ } this.table[index] = new valuePair(key, value) } return true } return false } get(key){ // 获取元素 const position = super.hashCode(key) if(this.table[position] != undefined){ if(this.table[position].key === key){ return this.table[position].value } let index = position + 1 while(this.table[index] !== undefined && this.table[index].key !== key){ index ++ } if(this.table[index] != undefined && this.table[index].key === key){ return this.table[index].value } } return undefined } remove(key){ const position = super.hashCode(key) if(this.table[position] != undefined){ if(this.table[position].key === key){ delete this.table[position] this.verifyRemoveSideEffect(key, position) // 将删除空位补上 return true }else{ index = position + 1 while(this.table[index] != undefined && this.table[index].key !== key){ index ++ } if(this.table[index] != undefined && this.table[index].key === key){ delete this.table[index] this.verifyRemoveSideEffect(key, index) return true } } } return undefined } verifyRemoveSideEffect(key, removedPosition){ // 把删除元素后的且与删除元素相同散列值的元素向上补一位 const Hash = super.hashCode(key) let index = removedPosition + 1 while(this.table[index] != undefined){ // 若在空位处也没有相同的散列值，说明后面都没有了 const posHash = super.hashCode(this.table[index].key) if(posHash <= Hash || posHash <= removedPosition){
// 只移动小于等于删除元素的散列值 this.table[removedPosition] = this.table[index] delete this.table[index] removedPosition = index } index ++ } } }
djb2HashCode(key) { const tableKey = this.toStrFn(key) let hash = 5381 for (let i = 0; i < tableKey.length; i++) { hash = (hash * 33) + tableKey.charCodeAt(i) // 即使loselose散列值相同,djb2也几乎不会相同
} return hash % 1013 }
原文：https://www.cnblogs.com/xt112233/p/15126016.html