散列表
散列表也称哈希表，散列算法的作用是尽可能快地在数据结构中找到一个值。
如果要在数据结构中获得一个值，需要迭代整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。
散列函数的作用是给定一个键值，然后返回值在表中的地址。
loselose散列函数
下图为常见的散列函数——lose lose散列函数，方法是简单地将每个键值中的每个字母的 ASCII 值相加
创建散列函数
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 } }
处理散列表中的冲突
有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突
1.分离链接
分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是在 HashTable 实例之外还需要额外的存储空间。
如下图：
实现：
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 } }
2.线性探查
另一种解决冲突的方法是线性探查。之所以称作线性，是因为它处理冲突的方法是将元素直接存储到表中，而不是在单独的数据结构中。
添加元素
当想向表中某个位置添加一个新元素的时候，如果索引为 position 的位置已经被占据了，就尝试 position+1 的位置。如果 position+1 的位置也被占据了，就尝试 position+2 的位置，以此类推，直到在散列表中找到一个空闲的位置。
如下图：
删除元素
在删除某个元素之后，需要检验是否有必要将其后一个或多个元素移动到之前的位置。当搜索一个键的时候，这种方法可以避免找到一个空位置。如果移动元素是必要的，我们就需要在散列表中挪动键值对。
下图展现了这个过程：
实现：
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 ++ } } }
创建更好的散列函数
我们实现的 lose lose 散列函数并不是一个表现良好的散列函数，因为它会产生太多的冲突。一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），以及较低的冲突可能性
另一个可以实现的、比 lose lose 更好的散列函数是 djb2，这并不是最好的散列函数，但这是最受社区推崇的散列函数之一。
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 }