散列表¶

散列表（Hash table，也叫哈希表）
是根据键（Key）而直接访问在内存储存位置的数据结构。
也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
hash

构造散列函数¶

直接定址法

取关键字或关键字的某个线性函数值为散列地址。即{\displaystyle hash(k)=k}hash(k)=k或{\displaystyle hash(k)=a\cdot k+b}hash(k)=a\cdot k+b，其中{\displaystyle a\,b}a\,b为常数（这种散列函数叫做自身函数）
数字分析法

假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
平方取中法

取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
随机数法
除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即{\displaystyle hash(k)=k\,{\bmod {\,}}p}hash(k)=k\,{\bmod \,}p, {\displaystyle p\leq m}p\leq m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

冲突解决¶

载荷因子¶

散列表的载荷因子定义为：
alpha= 填入表中的元素个数 / 散列表的长度。 alpha 是散列表装满程度的标志因子。由于表长是定值，alpha与“填入表中的元素个数”成正比，所以alpha 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，alpha 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。