散列函数

将key转换成数组索引的函数

• 散列函数采用Mod方式时，用素数作为TableSize能减少碰撞
• 散列函数产生重复的散列值，被称为产生了冲突
• 装填因子：Count除以TableSize

解决散列函数冲突的方法

分离连接法

用链表来存储元素，具有相同散列值的元素存储在同一个链表里。

开放定址法

引入冲突解决函数F(i)， i是冲突次数

1. 线性探测法

F(i) = i， 线性查找空区域

2. 平方探测法

F(i) = i2 （平方）

3. 双散列

F(i) = i * hash2(X) 引入额外的散列函数hash2(X)

4. 再散列

对填充太满的表重新散列，建立大约2倍大小的新表，将旧表中的元素重新散列到新表中。

5. 可扩散列

深度为1的 B-树
扩展方式：树叶分裂