映射的碰撞：多key对应1个hash值

哈希函数的设计

目的：让关键字平均分配
evenly

直接定址法

数字分析法

根据数据特点：

Hash(Key) = key%p p<=m
p是小于m的最大质数

平方取中法

折叠法

除留余数法

随机数法

碰撞策略

开放定址法

线性试探法

再哈希法

链地址法

公共溢出区

地址+1，直到找到空单元

查找
位置空
位置放着确切的地址
位置放着其他地址

ASL 1/n*

关键字数量(m)和哈希表空间(n个内存单元)

哈希表的负载因子：m/n
0.75