> For the complete documentation index, see [llms.txt](https://qmmms.gitbook.io/note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://qmmms.gitbook.io/note/algorithm/qms04-cha-zhao.md).

# 查找

## 顺序查找

## 二分查找

$$
查找成功的\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。