- 《数据结构与算法》专栏完整版在公众号【书伟认视界】中查看，转载需联系微信【econe0219】
散列表
散列表（Hash Table），也可直译为哈希表。散列表是基于数组扩展得到的一种新的数据结构，因此有延续了数组最重要的一条性质：支持按下标随机访问，时间复杂度是O(1)。
通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。我们熟悉的python的字典就是由散列表实现的。
散列函数：
直观定义为hash(key)，key表示元素的键值，hash(key)指的就是经过散列函数得到的散列值。
用python的字典大概举个例子：
定义一个变量 student = {‘name’: ‘张三’, ‘age’: 20}
hash(‘name’)得到散列值0，即第一个位置，对应元素是’张三’；hash(‘age’)得到散列值1，对应元素是20。
因为散列表中的元素不可重复，所以散列函数的设计需要有以下三个要求：
- 散列函数计算得到的散列值是一个非负整数（数组下标从0开始）；
- 如果key1≠key2，则hash(key1)≠hash(key2)；
- 如果key1=key2，则hash(key1)=hash(key2)；
散列冲突/碰撞：
指的是多个关键字映射到同一个数组下标位置（其实就是鸽巢原理）。解决散列冲突的办法有开放寻址法和链表法。（参考链接）
1. 开放寻址法：如果出现了散列冲突，那就重新探测一个空闲位置，将其插入。
探测方法主要有三种：线性探测、二次探测、双重探测
线性探测如下图所示。散列表只有两个空位置，现有一元素经过散列函数计算后，被散列的位置是下标6，而该位置以及有数据，于是就产生了散列冲突，于是开始往后依次遍历找到空位置，直到找到下标为2的位置，将被散列的元素插入其中。
线性探测在极端情况下可能需要探测整个散列表，最坏情况下的时间复杂度时O(n)，因为线性探测每次探测的步长是1，即下标序列依次是hash(key)+0，hash(key)+1，hash(key)+2……而二次探测的步长是原来的“二次方”，即下标序列是hash(key)+0，hash(key)+ 1 2 1^2 12，hash(key)+ 2 2 2^2 22……
双重散列是指，使用多个散列函数hash1(key)、hash2(key)、hash3(key)…… 用第一个哈希函数计算得到的位置如果被占用，那么再用第二个哈希函数计算散列位置，以此类推。
无论那种方法，只要散列表中的空位置太少的话就容易构成散列冲突。为了保证散列表的操作效率，散列表中需要有一定比例的空闲位置。于是引入一个**加载因子（load factor）**来表示空位的多少。
加载因子 = 填入表中的元素个数 / 散列表的长度。 加载因子越大，说明空闲位置越少，冲突越多，散列表的性能越差。
2. 链表法
链表法相对更常用，也更简单。如上图所示，每个散列表中的每个槽位都有一条链表，所有散列值相同的元素都放在相同槽位对应的链表中。插入的时间复杂度是O(1)，查找删除的时间复杂度和链表的长度k成正比，即O(k)。
开放寻址法和链表法的对比
开放寻址的冲突代价更高，加载因子不能太大，适合小数据量的情况。链表法不受加载因子大小的影响，但如果小数据量的话，存储链表指针消耗的内存代价更高，但是对于大数据量，指针消耗的内存可以忽略不计。而且链表还可以改造为其他的高效数据结构，如跳表、红黑树等，使用更加灵活，容易优化。
散列表的扩容
有不断插入的数据，加载因子过大时，就需要对散列表进行动态扩容。每次扩容都申请原散列表大小的两倍空间，新散列表的加载因子就变成原来的一半。扩容之后，需要对数据进行搬移操作，这时候还需要计算原散列表中的数据在新散列表中的对应位置。
数据量大时，“一次性”扩容耗时比较多。但是可以分批完成，扩容操作和插入操作交替完成。也就是说，加载因子超过一定的阈值之后，先申请新空间，但不把数据一次性都搬移过去。当再有新数据插入时，将新数据直接插入到新散列表中，并在旧散列表中拿一个数据放到新散列表中。每次都交替插入和搬移操作，这样均摊分析实现的插入操作就快很多，时间复杂度从O(n)变为O(1)。
《数据结构与算法》专栏完整版在公众号【书伟认视界】中查看，转载需联系微信【econe0219】
.