散列表介绍

散列表（Hash Table，也叫哈希表）：是根据关键码值(Key value)而直接进行访问的数据结构。

通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

散列表的插入、查找和删除跟数组类似，根据散列冲突的解决方式有所不同

装载因子（load factor）

表示散列表中空位的多少。
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

当散列表的装载因子超过某个阈值时，就需要进行扩容；在装载因子小于某个值之后，启动动态缩容。

散列函数

散列函数就是将 key 转换成散列表下标的函数。

设计要求

  1. 散列函数计算得到的散列值是一个非负整数；
  2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
  3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

好的散列函数

  1. 散列函数的设计不能太复杂
  2. 散列函数生成的值要尽可能随机并且均匀分布

设计方法

数据分析法、直接寻址法、平方取中法、折叠法、随机数法

散列冲突

两个不同的 key 通过散列函数得到相同的 hashCode(散列值)，即为散列冲突。

散列冲突的解决方法：开放寻址法（open addressing）和链表法（chaining）
当数据量比较小、装载因子小的时候，适合采用开放寻址法；存储大对象、大数据量的散列表适合使用链表法。

开放寻址法

开放寻址法：出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

优点：散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度；序列化简单。
缺点：删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据；装载因子的上限不能太大，比链表法更浪费内存空间。

线性探测（Linear Probing）
插入：当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

查找：我们通过散列函数求出要查找元素的键值对应的 散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的 元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元 素并没有在散列表中。

删除：删除比较特殊，直接删除数据会导致原来的查找算法失效，所以要将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空 间，并不是停下来，而是继续往下探测。

缺点：散列表插入数值越多，散列冲突发生概率越高，需要探测的时间越久。插入、查找和删除的时间复杂度趋向于 O(n)。

二次探测（Quadratic probing）
二次探测与线性探测类似，线性探测每次探测的步长是 1，而二次探测探测的步长就变成了原来的“二次方”。

双重散列（Double hashing）
使用多组散列函数计算 hashCode，我们先用第一个散列函数，如果计算得到的存储位置已经被 占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽 可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。

链表法

将所有哈希地址相同的都链接在同一个链表中 ，因而查找、插入和删除主要在同义词链中进行。
链地址法适用于经常进行插入和删除的情况。

优点：内存的利用率比开放寻址法要高，对大装载因子的容忍度更高；比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
缺点：比较小的对象的存储，内存消耗大；存储大对象内存消耗忽略不计。

插入：只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，时间复杂度是 O(1)。

查找、删除：通过散列函数计算出对应的槽， 然后遍历链表查找或者删除。这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。

工业级的散列表

特性

  1. 持快速的查询、插入、删除操作；
  2. 内存占用合理，不能浪费过多的内存空间；
  3. 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

设计思路

  1. 设计一个合适的散列函数；
  2. 定义装载因子阈值，并且设计动态扩容策略；
  3. 选择合适的散列冲突解决方法。

应用

Word 文档中单词拼写检查功能
用散列表来存储整个英文单词词典（常用的英文单词有 20 万个左右，1 个字符占用 1 个字节，最多占用 20MB）。
当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正 确；如果没有查到，则说明拼写可能有误，给予提示。

java 中的HashMap
HashMap 底层采用链表法来解决冲突。
在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太 长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。