查找

顺序查找

二分查找

$$查找成功的\LARGE{最大}\normalsize检索长度=\lceil log_2(n+1) \rceil$$

$$查找失败的检索长度=\lceil log_2(n+1) \rceil 或\lfloor log_2(n+1) \rfloor$$

$$平均查找长度_{(n>50)}=log_2(n+1)-1$$

分块查找

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。