散列表

利用数据支持随机访问的特性为基础，是对数组的一种扩展。是一种key-value型数据结构，但是在存储的时候需要通过散列函数将key转换为对应的数组下标，结算后得到的值叫做散列值或者哈希值。

散列函数

通过散列表的概念可以知道散列函数是非常重要的，决定了数据存储的位置。散列函数设计的基本要求：

  • 计算得到的散列值是非负整数
  • 如果 key1=key2，则 hash(key1) = hash(key2)
  • 理想情况下，key1 != key2，则 hash(key1) != hash(key2)

现在已有的MD5、SHA、CRC等哈希算法，也无法避免散列冲突。

散列冲突

上述第三点，如果不同的 key，计算后的哈希值一样，则存在散列冲突，需要用一些其他方法来处理散列冲突。

开放寻址法

当产生哈希冲突后，继续寻找出一个可以存放数据的空闲地址，主要有以下几种方式。

线性探测

当产生冲突后，继续向后查找是否有空闲位置，直到查完全表。这种方式会造成原本计算出是该位置的数据结果被其他冲突的元素占用，所以该元素只能继续向后查找。如果冲突元素删除时也会对查找造成影响，例如：A 元素产生了哈希冲突存储在 X 位置，B 元素通过哈希计算位置是 X，但是因为 X 位置已经有了 A，所以需要继续向后寻址存储在 Y 位置，当 A 元素被删除后，此时来查找 B 元素，通过哈希计算 B 元素的位置是 X，此时 X 位置是空的所以就查找不到了。

这种方式虽然解决了一部分冲突元素的存储，但是带来了很多其他需要解决的问题。

二次探测再散列

类似于线性探测，线性探测的步长是 1，二次探测则是跳跃性探测

双重散列

当一个哈希函数计算后产生了冲突，采用另一个哈希函数计算，直到计算出空闲位置。这样会导致计算时间变长。

链表法

散列表的每个位置指向一个链表，当产生冲突后继续向链表后添加元素。

装载因子

1
散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大,说明空闲位置越少，冲突越多，散列表的性能就降低了。

工业级散列表设计

特性

  • 具备快速的查询、插入、删除操作
  • 内存占用合理，不浪费过的内存空间
  • 性能稳定，极端情况下不会退化到最坏情况

设计思路

  • 均匀的散列函数
  • 装载因子阈值，设计动态扩容，动态扩容时降低性能影响（将动态扩容任务分摊，在插入过程中扩容）
  • 合适的散列冲突解决方案

散列表使用举例

LRU 缓存淘汰算法

LRU(Least Recently Used) 最近最少使用算法。LRU 算法需要维护一个按照访问时间从大到小的排列的链表，涉及到的操作：

  • 新增一个节点
  • 查询一个节点
  • 删除一个节点

如果采用双向链表则新增和删除的复杂度都是 $O(1)$，但是查找性能是$O(n)$。为了降低查找时间复杂度，引入散列表，将所有节点维护在散列表中。通过散列表快速定位节点位置，通过双向链表快速插入或者更新节点位置。

如果有新的节点过来，先插入散列表然后将其插入到双向链表的尾部；如果已有节点被访问，则通过散列表定位然后改变该节点的前继和后继指针指向，可以直接将其移到尾节点。删除时在散列表中删除节点然后通过头指针在链表中删除节点。这样插入、删除、查询都实现了$O(1)$的复杂度。

Redis 有序集合(sorted set)

Redis 的有序集合是利用散列表+跳表来实现的。sorted set有两个属性：key 和 score，具有的操作：

  • 添加元素
  • 根据 key 查找、删除元素
  • 根据 score 范围查找数据
  • 根据 score 对元素排序

可以看到如果仅仅利用跳表或者散列表一种来实现，是无法达到上面的功能操作的。

Java LinkedHashMap

Java 中的 LinkedHashMap 是利用双向链表和哈希表来实现的。会根据元素的插入顺序和访问顺序来排序，LinkedHashMap 的原理就是 LRU 缓存算法的实现。两者是一样的。