概念

散列表Hash Table，又称为“哈希表”或者“Hash 表”。散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。
image.png

散列函数

散列函数hash(key)在散列表中起着非常关键的作用。
散列函数的基本要求：

  1. 散列函数计算得到的散列值是一个非负整数；
  2. 如果 key1 = key2，那 hash(key1) == hash(key2)；即相同的key，对应的散列值也应该是相同的
  3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。不同的key对应不同的散列值，几乎不可能。著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。

散列函数设计的好坏决定了散列冲突的概率，也就决定散列表的性能。
设计一个好的散列函数要求：

  1. 设计不能太复杂
  2. 散列函数生成的值要尽可能随机并且均匀分布，才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。

    散列冲突

    当散列函数对于不同的输入产生同样的散列值时，就产生了散列冲突（散列碰撞）。
    解决散列冲突的方法有两类，开放寻址法（open addressing）和链表法（chaining）。

    开放寻址法

    核心思想：如果出现了散列冲突，就重新探测一个空闲位置，将其插入。如何重新探测新的位置？
    线性探测（Linear Probing）
    一个比较简单的探测方法：线性探测（Linear Probing）。
    插入：如果数据被散列到的下标位置上已经存在数据，就按顺序往后一个一个找空闲位置，遍历到尾部还没有，就从表头重头开始遍历找
    查找：通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遇到为空闲位置，就说明要查找的元素并没有在散列表中。
    删除：将删除的元素，特殊标记为 deleted。主要是用于线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
    弊端：当插入的数据越来越多，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。
    二次探测（Quadratic probing）
    二次探测跟线性探测很像，线性探测每次探测的步长是 1，而二次探测探测的步长就变成了原来的“二次方”，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……
    双重散列（Double hashing）
    使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，要尽可能保证散列表中有一定比例的空闲槽位。用装载因子（load factor）来表示空位的多少。装载因子 = 填入表中的元素个数 / 散列表的长度装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。如果一开始散列表数组存储大小固定，可以通过”动态扩容“的方式解决。

链表法

image.png
插入：只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是 O(1)。
查找、删除：通过散列函数计算出对应的槽，然后遍历链表查找或者删除。这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

二者比较

  1. 当数据量比较小、装载因子小的时候，适合采用开放寻址法。 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突。
  2. 链表法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。Java 中 LinkedHashMap 就采用了链表法解决冲突(散列表+双向链表)。
  3. 开放寻址法数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。序列化起来比较简单；链表法包含指针，序列化起来就没那么容易。

  4. 删除数据的时候，开放寻址法比较麻烦，还要特殊标记，冲突的代价更高；链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。

    代码实现

    ```javascript class HashTable { constructor() { this.table = [] // 数组形式存储 }

    // 散列函数，可自定义 // 此处是最常见的散列函数 ‘lose lose’ static loseloseHashCode(key) { let hash = 0 for (let codePoint of key) { // 1、先将字符串中每个字符的ASCll码值“进位”相加 hash += codePoint.charCodeAt() } // 2、然后再求余、取模，作为散列值 return hash % 37 // 用一个质数来避免碰撞 }

    // 修改和增加元素 put(key, value) { const position = HashTable.loseloseHashCode(key) if (this.table[position] === undefined) { this.table[position] = { key, value } console.log(${position} - ${key}) } else { // 解决散列冲突 let index = ++position while (this.table[index] !== undefined) {

    1.  index++

    } this.table[index] = { key, value } } } // 读取(查找)数据 get(key) { const position = HashTable.loseloseHashCode(key) const getElementValue = index => { if (this.table[index] === undefined) return undefined if (Object.is(this.table[index].key, key)) { 

     return this.table[index].value

    } else {

     // 解决散列冲突，向后查找遍历
 return getElementValue(index + 1)

    } } return getElementValue(position) } // 删除数据 remove(key) { const position = HashTable.loseloseHashCode(key) const removeElementValue = index => { if (this.table[index] === undefined) return false if (Object.is(this.table[index].key, key)) {

     this.table[index] = undefined
 return true

    } else {

     // 解决散列冲突，向后查找遍历
 return removeElementValue(index + 1)

    } } return removeElementValue(position) } }

const hash = new HashTable() hash.put(‘Surmon’, ‘surmon.me@email.com’) // 15 - Surmon hash.put(‘Jhon’, ‘Jhonsnow@email.com’) // 29 - Jhon hash.put(‘Tyrion’, ‘Tyrion@email.com’) // 16 - Tyrion

console.log(hash.get(‘Surmon’)) // surmon.me@email.com console.log(hash.get(‘Loiane’)) // undefined console.log(hash) // HashTable { // table: [ // <15 empty items>, // ‘surmon.me@email.com’, // ‘Tyrion@email.com’, // <12 empty items>, // ‘Jhonsnow@email.com’ // ] // } ```

场景应用

Word 文档中单词拼写检查功能

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。对于现在的计算机来说，这个大小完全可以放在内存里面。所以可以用散列表来存储整个英文单词词典。
当用户输入某个英文单词时，拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。借助散列表这种数据结构，就可以轻松实现快速判断是否存在拼写错误。

LRU 缓存淘汰算法

LRU 缓存淘汰算法如果单纯地采用链表，时间复杂度是 O(n)。如果将散列表和链表两种数据结构组合使用，可以将查找、删除、添加这三个操作的时间复杂度都降低到 O(1)。image.png