对于频繁使用的查找表,希望 ASL = 0
记录在表中位置和其关键字之间存在一种确定的关系
HASH
定义
根据设定的哈希函数 H(key) 和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集...将关键字分割成若干部分,然后取它们的叠加和为哈希地址。...给定一组关键字为: 12, 39, 18, 24, 33, 21若取 p=9, 则他们对应的哈希函数值将为:
3, 3, 0, 6, 6, 3
可见,若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到...开放定址法
---
基本思想
有冲突时就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总能找到,并将数据元素存入线性探测法
Hi=(Hash(key)+di) mod m ( 1≤...哈希表饱和的程度,装载因子 α=n/m 值的大小(n—记录数,m—表的长度)α 越大,表中记录数越多,说明表装得越满,发生冲突的可能性就越大,查找时比较次数就越多[在这里插入图片描述