散列表（上）

散列思想

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来，它的时间复杂度是O(1)。

如何构造散列

通过散列函数将元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，使用同样的散列函数，将键值转化为数组下标，从对应的数组下标的位置获取数据。

散列函数

就是一个函数，可以定义为hash(key)，key表示元素的键值，hash(key)表示经过散列函数计算得到的散列值，也就是数组的下标。

构造散列函数的基本要求

1.散列函数计算得到的散列值是一个非负整数（因为数组下标从0开始）；
2.如果key1=key2，那么hash(key1)==hash(key2)；
3.如果key1≠key2，那么hash(key1)≠hash(key2)（散列冲突无法避免）。

开放寻址法解决散列冲突

核心思想是如果出现了散列冲突，就重新探测一个空闲位置，将值插入。这个“重新探测”新位置的方法，最简单的就是线性探测（Linear Probing），此外还有2种比较经典二次探测(探测步长变为线性探测的二次方)（Quadratic probing）和双重散列(不止一个散列函数)（Double hashing）。

装载因子

当散列中空闲位置不多时，散列冲突的概率会大大提高，为尽可能保证散列表的操作，尽可能保证散列表中有一定比例的空闲槽位。装载因子表示空位的多少。
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

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

链表法解决散列冲突

在散列表中，每个桶或槽会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。此时，插入操作的时间复杂度是O(1)，查找和删除元素要遍历链表，时间复杂度和链表长度k成正比O(k)。对于散列比较均匀的散列函数来说，理论上k=n/m，n表示散列中数据的个数，m表示散列中“槽或桶的个数”。