查找
顺序查找
二分查找
分块查找
B树
散列
hash表的实现主要包括构造哈希和处理哈希冲突两个方面:
对于构造哈希来说,主要包括直接地址法、平方取中法、除留余数法等。
对于处理哈希冲突来说,最常用的处理冲突的方法有开放定址法、再哈希法、链地址法、建立公共溢出区等方法。SGL版本使用链地址法,使用一个链表保持相同散列值的元素。
虽然链地址法并不要求哈希桶长度必须为质数,但SGI STL仍然以质数来设计哈希桶长度,并且将28个质数(逐渐呈现大约两倍的关系)计算好,以备随时访问,同时提供一个函数,用来查询在这28个质数之中,“最接近某数并大于某数”的质数。
散列函数
除留取余法:
H(key)=key%p(p<=N)
,关键字除以一个不大于哈希表长度的正整数 p,所得余数为地址,当然 HashMap 里进行了优化改造,效率更高,散列也更均衡。直接定址法:直接根据
key
来映射到对应的数组位置,例如 1232 放到下标 1232 的位置。数字分析法:取
key
的某些数字(例如十位和百位)作为映射的位置平方取中法:取
key
平方的中间几位作为映射的位置折叠法:将
key
分割成位数相同的几段,然后把它们的叠加和作为映射的位置
冲突解决方法
线性探查法
直接加1向后查,直到找到空位。
$ASL_{unsucc}$要加到空,意思是每一个位置查找失败长至少是1。
二次探查法
跳跃向后查,直到找到空位。
具体的查询序列是:$d,(d+1^2)mod(m),(d-1^2)mod(m),(d+2^2)mod(m),(d-2^2)mod(m) \cdots$
以上两种方法又叫开放定址法(闭散列法)
链接法(开散列法)
$ASL_{unsucc}$要加到空,意思是每一个位置查找失败长至少是1。
最后更新于