什么是散列表

散列表（Hash table，也叫哈希表），是根据键（Key）直接访问内存储存位置的数据结构。

一般而言，散列表通过一个散列函数将待查找的元素映射为数组下标（散列值，hash值），将元素存储在下标位置，查询时同样用这个散列函数得到下标，这样理论上定位元素的时间复杂度可以到O(1)

散列函数的设计要求

由于散列函数hash()的作用是将查找元素value映射为下标key（散列值），因此有以下基本要求

1. 散列值为非负整数
2. 如果value1 = value2，则hash(value1) = hash(value2)，这一点是必须实现的，否则散列表就失去了基础的查找作用，你先在表中插入了一个value，当你再去寻找时却再也找不到了
3. 如果value1 ≠ value2，则hash(value1) ≠ hash(value2)，这一点也好理解，不同的value应该存到不同的位置。现实情况是这一点不能完美实现，于是出现散列（哈希）冲突

散列冲突的原因

影响散列冲突的因素一般有三点：

1. 散列函数的设计

考虑一个极端情况，假如散列函数是个常数函数：hash() = 0，所有元素都会被映射到下标为0的位置，这种情况下散列冲突就非常严重了

当然谁也不会选这样的散列函数，但是要确保散列函数的结果足够随机，最好接近另一个极端：所有元素都被映射到不同位置

2. 数据本身

我可能设计了一个输出结果很随机的散列函数，可如果输入数据本身被设计过也会造成散列冲突。这就不得不提到一种DoS攻击：哈希洪水攻击。如果有恶意攻击者，掌握了算法细节，专门设计了一批结果冲突的输入数据，使得所有的数据经过散列函数之后到一个槽里，散列表查询时间从o(1)退化成o(n)，就能用很低的成本让服务器宕机

这时只能避免攻击者掌握算法细节，比如研究带密钥的散列函数（Keyed Hash Function）

3. 装载因子

另外，数据量和散列表容量的比重也会对散列冲突有影响，把10条数据分别插入容量为1，100、10w的散列表，第一种情况肯定会有散列冲突，而表的容量越大，冲突的概率也越小。这里数据量和散列表容量的比重也称为装载因子

之后HashMap的讲解中，我们将看看它是如何设计，从而尽量避免散列冲突，以及解决已存在的散列冲突的

解决已经发生的散列冲突

开放寻址法

• 线性探测法：核心思想就是查找散列表中离冲突单元最近的空闲单元（hash(x)冲突，就注意探测hash(x)+1, hash(x)+2），并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。需要注意的问题是：

  • 查找元素时，遇到散列冲突，会逐个探测邻近单元，直到查到null就认为元素不存在
  • 由上一点可知，删除元素时，不能直接置为null，而是要标记为deleted。因为置为null会导致之后查找探测到该位置时，会判断元素不存在，而实际上元素可能就在后面的单元中。
  • 插入元素时，遇到deleted的元素可以覆盖

  结合这三点可以看出，线性探测法中，所有发生散列冲突的元素（包括已删除的元素）一定是连续保存在散列表中，中间不会有null值打断。

  也因此，线探探测法有以下的问题：

  • 数据聚集：散列值本来就不会均匀分布在下标中，线性探测法会加剧聚集的现象，让某个区域冲突概率特别大，查询的时间会更长，极端情况下插入和查询都会到O(n)

  为了改进数据聚集，其他开放寻址法还有：

• 二次探测法：和线性探测相比步长变了，hash(key)+0，hash(key)+1^2， hash(key)+2^2……

• 双重探测法：使用一组散列函数 hash1(key)， hash2(key)，hash3(key)…我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数

拉链法（链表法）

将散列到同一个存储位置的所有元素保存在一个链表中，是HashMap使用的思想

两种方法的比较

1. 开放寻址法

   • 优点：
     • 数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度（连续空间）
     • 序列化更简单，链表法包含指针，序列化没那么容易
   • 缺点
     • 删除数据的时候比较麻烦
     • 所有数据都存在一个数组里，尤其装载因子大的时候，探测时间会很长（因为这条探测的路径上除了散列值相同的元素，还可能会遇到其他不同的元素）

   总结：数据量不大，用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

2. 链表法

   • 优点：
     • 对大装载因子的容忍度更高，探测的路径上只会有散列值相同的元素。极端的例子：第一次插入散列值为a的元素，后面n-2次都没冲突，第n次的元素散列值也是a但是和第一个元素key不同。这样在查找第n个元素时，线性探测法就是n，但链表法就是1
     • 链表本身要存指针，消耗更多内存，但是如果本来就要存大对象，指针大小也就可以忽略不计了

   总结：适合大数据量、大对象，并且更灵活，可以用红黑树代替链表进行查询优化