哈希表
所谓的哈希表实际上就是一个数组，属于数组的一种扩展应用。一般来说是通过申请一段长度已知的数组，通过hash函数计算数据映射到数组上的下标位置。数组存储的可以是指向某个对象的指针，也可以是特定的值，从而达到O(1)时间复杂度的检索时间。
哈希桶数在设计上优先选择素数，因为素数能够使哈希冲突的概率更低，在进行扩容时一般是以两倍大的方式增长，然后再查找附近的素数。
以 C++ 的 unordered_map、unordered_set 为例，这两个数据结构的底层容器都是 hashtable，它定义了28个素数作为桶容量：
enum { __stl_num_primes = 28 };
static const unsigned long __stl_prime_list[__stl_num_primes] ={
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
而 Python 的字典设计则没有使用素数作为桶数，初始桶数为 8，后续每次只是以两倍大的方式进行增长：
#define PyDict_MINSIZE 8
哈希冲突
当多个数据经过 hash 函数计算后得到了相同的数组下标，此时就出现了哈希冲突现象。
解决哈希冲突的方式有多种，主要有以下几种：
- 开放寻址法：
- 线性探测法
- 二次探测法
- 随机探测法
- 再散列函数法
- 链地址法
开放寻址法
开放寻址法的核心思想是：如果出现了散列冲突，我们就重新探测一一个空闲位置，将其插入。在这种方法思想下，有线性探测法、二次探测法、随机探测法、再散列函数法几种应用
线性探测法
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，如果遍历到尾部都没有找到空闲的位置，那么我们就再从表头开始找，直到找到为止。
fi(key) = (f(key) + di) MOD m (di = 0,1,2,3,4....,m-1)
如下表所示，哈希表的长度为12，已被占用 5 个位置：
当计算 key = 25 时，假设计算得到的值是f(25) = 5，该位置已经被另外的数占用了，因此我们应用上面的公式重新计算得到f(25) = (f(25) + 1) mod 12 = 6，所以 25 存入下标为 6 的位置。
Python 字典使用的就是这种方式去解决哈希冲突。
二次探测法
假设上表已填充的数如下：
当计算 key = 35 时，如果计算到的值是f(35) = 5，那么如果按照线性探测法，那么会逐个往后查找，从当前表的数据可以看出将会连续探测 5 个位置之后才会找到空位，而实际上位置 5 的左边实际就有空位。因此二次探测法改进了探测方法：
fi(key) = (f(key) + di) MOD m (di = 1^2, -1^2, 2^2, -2^2, ...q^2, -q^2 q<=m/2)
这种方式是双向寻找空位置，增了平方运算的目的是为了不让关键字都聚集在某一块区域
随机探测法
这种方式利用的是伪随机数，即固定一个随机种子，则可以生成一个随机的但是固定的 di 数列，因此探测方法为：
fi(key) = (f(key) + di) MOD m (di 是一个伪随机数列)
再散列函数法
这种方式是通过设置了多个不同的散列函数，当发生散列地址冲突时，就换一个散列函数再计算，这种方式可以使关键字不产生聚集，不过也增加了计算的时间
查找与删除
散列表中查找元素的时候，我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就依据散列函数再计算一个新的下标值。如果这个过程中找到一个空闲位置，那么说明目标元素并不存在散列表中。
对于删除操作稍微有些特别，不能单纯地把要删除的元素设置为空，否则就会造成误判。所以在删除时我们需要把可以将删除的元素，标记成一个特殊的状态deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。后续在插入新数据时，遇到deleted状态位置相当于是空的，因此可以插入。
Python 字典会将被删除的位置标记为 DKIX_DUMMY。
弊端
当散列表中插入的数据越来越多时，其散列冲突的可能性就越大，极端情况下甚至要探测整个散列表，因此最坏时间复杂度为 O(N)。一般来说为了避免时间复杂度过低，会将负载因子设置为为较小值，这也意味着 rehash 的概率更大，造成的内存空间浪费也会更大。
Python 字典的负载因子设定为 2/3。
链地址法
链表法的原理是：如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可。
C++、Redis 就是使用链表法解决哈希冲突。
查找与删除
链地址法的查找与删除就比较简单了，只需要根据哈希函数计算得到的位置去顺序遍历节点链表即可。
弊端
这种方式解决哈希冲突是比较容易的，但是如果节点链表过长，那么也会使得搜索性能退化为O(N)。为了尽可能的保证链地址法的性能效率，Java 在 HashMap 中当链表长度大于8 时，就会转换为红黑树，提升效率。
负载因子和rehash
负载因子 = 表中元素数量/哈希表的长度
负载因子越大，代表元素数量越多，空闲位置越少，哈希冲突也就越多，整体性能会下降。过小的负载因子又会造成内存空间的浪费，因此需要 rehash 进行数组容量的扩容或缩容，以维持一个良好的平衡。
开放寻址法和链表法比较
对于开放寻址法解决冲突的散列表，由于数据都存储在数组中，因此可以有效地 利用 CPU 缓存加快查询速度 (数组占用一块连续的空间)。但是删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。此外由于所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，负载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
对于链表法解决冲突的散列表，对内存的利用率比开放寻址法要高，因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于1的情况。接近1时，就可能会有大量的散列冲突，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。但是，链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，而且链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这对于执行效率有一定的影响。