（点击上方公众号，可快速关注）
来源：taozj
taozj.org/201611/data-structure-and-algorithm-(1)-hash.html
散列技术常常用于键－值关系的数据结构中，比如数据库索引、map、缓存等地方，其是通过在记录(值)的存储位置和其关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。散列技术的实现方式决定了其最适合的求解问题是查找与给值相等的记录(是否存在及其位置)，而对于其他查找不适合：比如某个关键字对应很多记录的情况、范围查找、查找最值等。
1.1 散列函数
散列函数可以说是散列数据结构的核心，最直接的感受就是好的散列函数能够让记录能够在hash表中分布均匀(uniform distribution)，当然用于相似性查找的特殊hash类别不考虑在内。此外，在我们平常习惯性的思维中，认为只要满足X != Y，则f(X)!=f(Y)就是好的满足条件的hash函数，比如常用的CRC函数，其实如果将这类函数用在hash中，大多数情况下要比精心设计的hash函数冲突的可能性更大，会影响到hash的效率和性能。
1.1.1 散列函数通常具备条件
(1). 散列均匀分布：
由于空间的**散列表不可能无限的大，而散列冲突的几率会因为空间的**而增大，这个时候就需要一个perfect的散列函数来作为弥补，通常设计一个好的均匀分布的散列函数是比较困难的，这也是很多散列函数专家努力的方向。
在绝大多数场合下，散列表的容量都设计成2的指数长度大小，而算出来的散列值通常采用掩码的方式快速得到散列表的索引值，所以此时的散列函数可以设计优化成在二进制的各个bit位为随机分布就可以了。不过murmur的作者也说了，好的hash函数不应当假定其用户采用’hash % tablesize’的方式来hash-to-table-index，只是作为一种常用的习惯性方法而已。
(2). 计算简单高效：
hash值不应当过于的复杂，hash计算的吞吐量也是hash函数的一个重要衡量标准，除了在设计中不要用过于复杂的计算操作外，实用新式CPU的高效运算指令也是提升性能的一个方面。
1.1.2 简单常用构造散列函数的方法
(1). 直接定值法：就是利用元素的关键码设计成某个线性函数的形式，比如
f = a × key b;
其计算简单而且不会冲突，但是需要事先知道关键码的在小范围连续分布比较适用；
(2). 数字分析法：抽取部分数字进行诸如：反转、左环位移、右环位移、前两数与后两数相加等各种操作，其也主要用于事先知道关键字分布且关键字位数较多且若干位分布比较均匀的情况；
(3). 平方取中法：关键字位数不多的情况，先对关键字平方计算，然后取其中的某些固定位组合；这其实在实际中常用的方法，采用先放大再抽取的方式，是一种伪随机数的生成方法；
(4). 折叠法：将数字串平均分几个部分后重叠(移位法)对齐或者折叠(分界法)对齐后求和，通常用在关键字位数较多的情况下；
(5). 除留余数法：也是最常用的，mod取模缩减散列空间，这个操作可以直接针对关键字，或者是其他操作后的中间结果；若散列表表长为m，通常p为小于或等于表长的最小质数或包含不小于20的质因子的合数，因为这样产生hash冲突的可能性要少的多；
(6). 乘余取整法：
f(key) = { Z × (a × key % 1) }
a通常取黄金分割数0.6180339，%1表示取结果的小数部分，Z为散列表的容量；
(7). 随机数法：f(key) = random(key)，适合于关键字长度不等的情况。
1.2 散列表的冲突处理
散列表的冲突处理主要分为闭散列法和开散列法，闭散列法也称为开放定址法。
1.2.1 闭散列法（开放定址法）
当插入元素的时候，一旦发生了散列冲突，就去寻找下一个空的散列地址供插入，而查找的时候逐个查找，直到碰到开放的地址查找失败。闭散列法是通过将冲突的元素以一定的模式存储在原散列的空间中。
之所以叫做闭散列法，就是因为冲突的元素没有开辟额外的存储空间，还是在原先hash表的空间范围之内。
(1). 线性探测法：将散列表看作是一个循环向量，若初始地址是f(key)=d，则依照顺序d、d 1、d 2…的顺序取查找，即f(key)=(f(key) 1)mod N;
(2). 二次探测法：基本思路和线性探测法一致，只是搜索的步长和方向更加的多样，会交替以两个方向，步长为搜索次数的平方来查找；
(3). 双重散列法：通常双重散列法是开放地址中最好的方法，其通过提供hash()和rehash()两个函数，前者产生冲突的时候，定制化后者rehash()重新寻址，其机制比前面两种固定格式的要灵活的多；
开放定址法一般用于冲突极少的情况，同时因为没有用到指针，所以对于数据的传输是友好的。
1.2.1 开散列法
与前面闭散列法对应的开散列法，一般也叫作拉链法或者链地址法，通过将冲突的元素组织在链表中，采用链表遍历的方式查找。链地址法和上面的开放定址法最大的优势是解决方法直观，实现起来简单，尤其在删除元素的时候此处只是简单的链表操作，但是前面需要考虑后面可能有元素，处理会比较复杂。同事开散列法可以存储超过散列表容量个数的元素。
(1). 链地址法：相同散列值的记录放到同一个链表中，他们在同一个Bucket中；
(2). 公共溢出法：将所有的冲突都放到一个公共的溢出表中去，适用于冲突情况很小的时候。
除了使用传统的链表，还可以使用dynamic array的方式存储，分配的时候也可以预分配多个，以保证对CPU的缓存优化友好。
1.3 散列表的装填因子
装填因子=填入表中的记录个数/散列表的长度，实践中无论设计多好的散列函数，当装填因子超过0.7后散列表的性能就会因为散列冲突开始下降，当填入表的记录越多，装填因子就越大，产生冲突的可能性也就越大。此时可以考虑增加hash表的容量，以维持查找的性能，而且更重要的是常常在实践中，是事先不知道需要管理元素的个数的，所以动态增加散列表的容量是必须的。
修改散列表容量会导致之前元素寻址失效，这个过程也成为resize(rehash)的过程，Java的HashMap在loadfactor | 
注册
登录
