Hash是一种index by value的数据结构，主要解决的问题是可能的取值空间S压缩至实际的散列表地址空间A，使得|S| = R >> M = |A|。
例如 hash(key) = key % M 将key实际存储于hash(key) 则装填因子load factor
散列函数
- 选择标准
确定，快速，满射，均匀
尽可能覆盖整个散列空间且映射至各位置概率尽可能接近，以避免hash collision、
- 除余法
hash(key) = key % M = key & (M - 1)
M取素数时 数据对散列的覆盖最充分，分布最均匀
缺点
除余法具有不动点，例如0
除余法相邻关键码的散列地址也相邻（零阶均匀） - MAD法
取M为素数，a>0，b>0，a%M != 0
hash(key) = ((a * key) + b) % M
相邻相邻关键码的散列地址不相邻（一阶均匀） - 数字选取
- 平方取中
- 折叠法
取数字等宽的若干段求和 - 位异或法
取数字等宽的二进制段求异或 - 伪随机数
rand(x + 1) = a * rand(x) % M
Hashcode
对于不是数字的key需要先转换为hashcode再求对应的散列地址
- Hashcode的转换方法
多项式法：将字符串各个字符对应的整数作为多项式的各项系数（对于给定a的数值）求出多项式的结果
散列冲突
- 拉链法 / 封闭定址
每个桶存放一个链表，依次存放冲突元素；每次给定key遍历其对应的链表
缺点：
指针需要额外空间
节点需要动态申请
空间不连续分布，系统缓存失效 - 开放寻址法
为将查找链存放于连续的空间，采用open addressing，遇到冲突则将其放在下一个紧邻位置；查找时从key对于散列地址一直查找至空桶；删除元素时为避免空桶的产生使用懒惰删除，将删除元素赋予特殊标记，插入时遇到标记视为空，查找时遇到标记继续查找。
2.1 线性试探
试探位置间距太近，冲突频繁
2.2 平方试探
以平方数%M为间距确定下一个试探单元
优点：
缓解数据聚集
缺点：
一定程度破坏了数据的局部性（每个1kb的缓存页面可以容忍连续16次以下的冲突）
可能会无法找到所有的空桶
- 若需要找到所有的空桶：
M取为素数，n^2%M的取值恰好会有M/2上整个桶，此时装填因子必须小于50%
2.3 双平方试探
为解决平方试探至多半载的问题，在冲突时进行前后步长的交替的试探，且表长M取模4余3的素数时，前后试探不会出现重复和冲突，但M取某些模4余1的素数会导致前后查找链完全相同。
