字典或称为映射是常用的数据结构，各种语言都提供了相关的库或内置的实现，如 pyhton 中的 dict，java 中的 HashMap/TreeMap，以及 c++ STL 中的 map/unordered_map 都是字典具体的实现。

分类

从实现字典的内部数据结构看，可以分为两类字典：

• 哈希字典
• 红黑树字典

其中哈希字典内部使用哈希表实现，红黑树字典使用红黑树作为内部数据结构，二者主要区别是：

• 哈希字典的 key 无序
• 红黑树字典的 key 有序
• 哈希字典近似 O(1) 时间复杂度，不稳定
• 红黑树字典时间复杂度 O(logN)， 稳定

红黑树字典实现

只要按照 key 的大小关系实现一颗红黑树，每个节点用于记录 key 和 value 即可，红黑树实现不是本文讨论重点，不再研究。

哈希字典实现

哈希字典一般用哈希表实现，哈希表是一个数组，通过对 key 按照固定的哈希函数进行哈希，并将哈希值对哈希表数组的长度求余，即得到这个 key 在哈希表中的下标，将 key-value 对存入对应下标的哈希表位置即可。

上述是没有哈希冲突的情况，如果存在哈希冲突，即两个不同的 key 进行哈希求余后得到的下标值相同，此时常用的处理方法有两种：

• 链表法
• 开放寻址法

两种方法的优缺点先做一个对比：

• 开放寻址法的负载因子（字典元素个数/哈希表长度）必须小于等于1，而链表法可以允许更大的负载因子，开放寻址法需要分配更大的哈希表
• 存储的元素值较小时，链表指针相对来讲占用的存储空间不可忽略，而开发寻址法不需要占用多余的空间
• 删除元素时，链表法直接从链表上移除元素，开发寻址法将元素标记位删除，而实际不能删除，增加了处理步骤
• 开放寻址法由于存储在哈希表数组上，内存连续，可以有效利用 CPU 缓存加快查找

链表法

哈希表数组的每个位置存储一个链表，key-value 对以链表节点的形式插入对应哈希表位置的链表上，可见同一链表上的元素都是哈希冲突的。查找元素时，先通过 key 定位到哈希表下标处的链表，遍历链表，比较链表节点上的 key 和待查找的 key 是否相同。可见由于哈希冲突的存在，需要遍历链表进行查找，降低了字典的效率。

当哈希冲突过多，链表太长时，将严重影响字典的性能，此时需要扩大哈希表数组的长度，进行 rehash 。

Redis 即是采用链表法解决哈希冲突的。

开放寻址法

开放寻址法的核心思想是，如果出现了哈希冲突，就在哈希表上重新探测一一个空闲位置，将其插入。

最简单的探测方法是线性探测，比如计算出应该插入下标2的哈希表位置，但该位置已经有元素了，那么继续找哈希表下一个下标位置3，如果到哈希表末尾都没有找到空闲位置，那么从哈希表开头继续寻找，直到找到空闲的下标位置。

查找元素时，先求出 key 对应的哈希表内下标，比较下标处元素 key 和待查找的 key 是否相同，相同则找到元素，不相同则继续找哈希表下一个下标处元素进行比较，直到找到哈希表下标处空闲的位置，说明哈希表内没有这个 key 。

删除元素时，不能直接将该下标位置置空，因为这样会导致查找元素时，遇到已删除的元素位置为空闲，提前终止查找。因此删除元素时，可以标记为 deleted，表示该元素无效，这样查找元素时，跳过 deleted 标记的元素，继续往下查找。

线性探测法存在很大问题。当哈希表插入的元素越来越多时，其哈希冲突的可能性就越大，极端情况下甚至要探测整个哈希表，因此最坏时间复杂度为 O(N) 。在开放寻址法中，除了线性探测法，还有二次探测和再散列等方式。

二次探测：冲突发生时，在表的左右进行跳跃式探测，比如依次探测冲突下标位置后 +k 下标位置和前 -k 下标位置。

再散列法：就是使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置，每次冲突都要重新散列，计算时间增加。

参考

• 互联网公司面试经——你不得不知道的哈希表
• 解决哈希冲突的三种方法（拉链法、开放地址法、再散列法）