站内链接:

搜索

分类

在一组记录集合中找到关键码值等于给定值的某个记录, 或者找到关键码值符合特定条件的某些记录的过程. 一般而言, 检索的数据对象都是大量的数据, 所以对检索的效率要求非常, 为了提高检索效率, 需要在数据存储时做一些特殊的存储预处理, 以便在之后检索时更加快速. 当然, 若预处理的性能损耗比较大, 则每次新插入数据都需要一定的时间进行重新预处理流程.

classify

基本概念

搜索算法中的一些基本概念:

  • 预排序: 在数据进行存储时, 进行一定的预处理, 以便检索更加快捷, 比如二分法查找就要求数据本身逻辑上是一棵树结构.
  • 建立索引: 以空间换时间, 充分利用索引来加快索引速度
  • 散列或搜索技术: 将数据组织到表中, 根据关键码来确定表中每一个记录的位置
  • ASL: 平均检索长度（Average Search Length，ASL）, 检索过程中对关键码需要执行的平均比较次数, 衡量检索算法优劣的时间标准

从数据存储考虑, 查找的方式有:

  • 基于线性表的查找
  • 基于索引或者散列的查找, 树遍历实际也是基于索引
  • 基于位图的查找

线性表的查找

分类

基于线性表的查找, 其中数据的存储都是连续的, 在此物理存储的基础上提出的查找算法, 所以某些顺序存储的树逻辑结构数据, 其搜索也是基于线性表.

  • 顺序查找: 针对线性表中的记录, 逐个的进行关键码和给定值的比较
  • 二分查找: 首先是预处理为有序的, 之后在逻辑上使用二分查找
  • 分块查找: 顺序查找和二分查找的折衷, 其中块和块之间是有序的, 类似分而治之的思路
  • 插值查找：根据目标元素与线性表中最小和最大元素的比例估算目标元素可能的位置，然后在估算位置附近进行搜索，以逐渐缩小搜索范围。
  • 斐波那契查找：类似于二分搜索，但采用斐波那契数列来确定分割点，以更均匀地划分搜索范围。

使用场景

  • 顺序搜索：适用于简单的线性表结构，元素数量较少，或者无序线性表的搜索。
  • 二分搜索：适用于有序线性表，并且支持随机访问，如数组，以及有序链表。
  • 插值搜索：适用于有序线性表，且元素分布较为均匀的情况，可以提高搜索效率。
  • 斐波那契搜索：适用于有序线性表，且元素分布较为均匀的情况，可以提高搜索效率。
  • 分块搜索：大规模数据集的查找、内数据有序，块间数据无序、数据分布不均匀、动态数据集，将数据分为几块，其中大量频繁的改动几种在某块内，此时进行 CURD 就非常低耗

散列表的查找

介绍

  1. 散列相关术语

何谓散列? 首先让我们看下散列表中的各个角色或者动作:

  • 一个确定的函数关系 h
  • 以节点的 key 为自变量
  • 将h(key)作为结点的存储地址

其中涉及的基本概念:

  • 负载因子: a = n/m, 散列表空间大小 m, 填入表中的结点数 n, 其中a越大则表示表中的元素个数越多, 产生冲突的可能性就越大, 当然若a越小则可能浪费的空间就越多
  • 冲突: 某些散列函数对于不等关键码计算出相同的散列地址.
  • 同义词: 发生冲突的两个关键码

散列技术的重要关注点:

  • 如何确保结点分布均匀?
  • 如何解决冲突?
  1. 散列函数和冲突解决办法

在真正开始进行散列表查找算法的分类介绍之前我们先简单介绍下上面提到的几个专业术语。散列函数，其可选项有：

  • 除余法: h(x) ＝ x mod M
  • 乘余取整法: hash ( key ) = ⎣ n * ( A * key % 1 ) ⎦
  • 平方取中法: 先通过求关键码的平方来扩大差别，再取其中的几位或其组合作为散列地址, 适合于不知道数据的分布情况但数字不是很大的情况
  • 数字分析法:
  • 基数转换法: 把关键码转换成原来进制上的数, 取其中若干位作为散列地址
  • 折叠法: 将关键码分割成位数相同的几部分, 取这几部分的叠加和作为散列地址

冲突解决办法：

  • 开散列：开放地址法，是一种冲突解决方法，当发生冲突时，尝试在散列表中的其他位置找到空槽来存储冲突的元素。冲突策略解决：使用线性探测、二次探测、双重散列等方法，依次尝试其他位置，直到找到空槽或遍历完整个散列表。
  • 闭散列：闭合地址法或链地址法，是一种冲突解决方法，当发生冲突时，将冲突的元素存储在散列表中的一个位置，并使用链表等数据结构将冲突的元素链接在一起。冲突策略解决：使用链表、红黑树等数据结构，在散列表的每个位置上维护一个链表或其他结构，将具有相同散列地址的元素链接在一起。

对于开地址法, 需要控制负载因子在0.7~0.8之内。对于闭散列，当冲突发生时，使用某种方法为关键码 K 生成一个散列地址序列: d0, d1, d2, ..., dm-1, 其中 d0 为基地址(h(K)), di 则为后继散列地址, 当然如果所有的后继散列地址都不空闲, 则说明闭散列表已满.

  • 二次探测法: 冲突时, 寻找下一个空闲位置, 位置加 1 平方, 无位置则位置加 2 的平方, 依次往下走
  1. 增删改查

散列表本身就是一个数据结构，此类结构够

  • 删除：删除一个记录一定不能影响后面的检索, 释放的存储位置应该能够为将来插入使用，只有开散列方法可以真正的删除, 闭散列方法都只能作标记(墓碑)
  • 插入: 避免插入两个相同的关键码，一旦碰到墓碑, 检索过程仍然需要沿着探查序列下去, 直到找到空位置

分类

上面简单的介绍了散列表查找的索引分类

  • 线性索引: 一级索引, 二级索引
  • 静态索引: 静态索引是一种用于静态数据集合的索引结构，其中数据集合在创建索引后不再发生变化或只有有限的更新操作。静态索引适用于不频繁变更的数据，例如静态数据库、归档数据或只读数据。例如： MWT, ISAM, 倒排
  • 动态索引: 动态索引是一种用于动态数据集合的索引结构，其中数据集合在创建索引后会频繁发生变化，包括插入、删除和更新操作。动态索引适用于需要实时维护和更新索引以支持数据变化的场景。例如： B 树, B++树, 红黑树, 其中 B 树其实也是 MWT 的一种

下面就简单介绍下静态索引和动态索引的说明，更加详细的分类见第五章。

  1. 静态索引
    • 建立索引一次：静态索引在数据集合创建后进行一次性建立，之后不再修改。这样可以在索引构建阶段投入更多的时间和计算资源，以获得更高的索引质量和性能。
    • 提供高效检索：静态索引通常针对数据的特点和查询需求进行优化，提供快速的检索操作。由于数据不发生变化，索引结构可以更好地利用数据的统计特性。
    • 减少维护成本：由于数据集合是静态的，不需要频繁更新索引，因此减少了维护索引的成本和开销。这使得静态索引适用于一次性查询或有限更新的场景
  2. 动态索引
    • a. 支持数据变化：动态索引能够实时响应数据的变化，包括插入、删除和更新操作。索引结构可以在数据变化时进行相应的调整和更新，保持索引与数据的一致性。
    • b. 提供高效检索和更新：动态索引旨在在数据变化的同时提供高效的检索和更新操作。索引结构的设计和优化可确保在插入、删除和更新操作时，尽量减少索引的调整开销，同时保持检索性能。
    • c. 灵活性和适应性：动态索引能够适应数据集合的变化，能够动态调整索引结构以适应新数据的插入和旧数据的删除。这使得索引能够适应数据集合的动态性和变化模式。

拉链法

这是开散列方法的一种, 将所有关键字为同义词的结点链接在同一个单链表中, 若选定的散列表长度为 m, 则可将散列表定义为一个由 m 个头指针组成的指针数组 t[0..m-1]. 凡是散列地址为 i 的结点, 均插入到以 t 为头指针的单链表中

open-zip

注意，这里的数据结构叫链表数组。

桶式散列

该方法类似基于线性表的分块查找算法, 适合于存储于磁盘的散列表, 其术语开散列方法, 整体流程:

  • 把一个文件的记录分为若干存储桶, 每个存储桶包含一个或多个页块
  • 每一个存储桶内的各页块用指针连接起来, 每个页块包含若干记录
  • 散列函数 h(K)表示具有关键码值 K 的记录所在的存储桶号

位图的查找

介绍

使用位向量, 为每一个可能的集合元素(0, n-1)分配一个 bit 位置, 根据 bit 来进行判断是 否存在. 其中在进行位运算的时候, 通常在遍历时并非一位位的进行操作, 而是按照基本数据类型长度的位数来进行操作, 其中类似的 C 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 对于存在41个元素的unsigned long数字集合
#define N = 41
typedef unsigned long ulong;
enum {
    NB = 8 * sizeof(ulong);  // 容器, 存储位标识
    LI = N == 0 ? 0 : (N-1) / NB;
}

ulong A[] = {35, 30, 9, 7}
ulong AB[LI + 1];

for (int i=0; i<N; i++) {
    value = A[i];
    // 右移 value % NB
    AB[value/NB] = (ulong)1 << (value % NB);
}

位图索引

使用位图表示的索引, 对列的每个键值建立一个位图, 用于 orcale 数据库中, 相比 B 树索引, 占用的空间更小, 查找极快. 例如, 对于表 test, 有一个 state 列, 总共 10 行数据:

1
2
3
4
5
6
7
数据: 10    20    30    20    10    30    10    30    20    30
此时会建立位图:
    BLOCK1    KEY=10  1    0    0    0    1    0    1    0    0    0
    BLOCK2    KEY=20  1    0    0    0    1    0    1    0    0    0
    BLOCK3    KEY=30  1    0    0    0    1    0    1    0    0    0
也就是, 对相同值按照位数来进行存储表示, 当然 Block1的长度跟随记录的增加也
要进行调整.
  • 优点: 决策支持系统
  • 缺点: 键值较多的列, 重复较少的列实际上效率不高; 对于 update, insert, delete 频繁的列, 代价大

Index

介绍

广义上的索引: 指针/链接, 实际上在线性查找(如二分), 散列查找(本身特质)都存在.
狭义上的索引: 一般指散列查找中的索引.

线性索引

在线性索引中, 索引文件并组织成一组简单的键值对(key, value)的序列, 一般来说该序列还是有序的. 线性索引中的这种结构, 能够实现高效的, 随机的访问, 就相当于对线性查找的一种优化措施, 想想函数的分装, 其实思想大体类似. 对某一块数据, 确定唯一的索引, 检索时确定首先能够快速的确定块位置, 之后进入块内部进行其他查找. 索引本身还存在一级索引, 二级索引, 多级索引，那么一二级索引有什么区别呢?

  • Primary Index：一级索引是对数据块（数据页或数据文件）的索引，每个数据块对应一个索引项。索引项中包含用于快速访问该数据块的信息，例如块的物理地址或指针。其特点：稀疏索引、直接映射、提供顺序访问
  • Secondary Index：二级索引是对一级索引的索引，每个一级索引对应一个二级索引，二级索引中包含一级索引的信息。二级索引可用于进一步加速数据的检索。其特点：密集索引、间接映射、提供更快的检索

互联网就是一个一层又一层的结构.

静态

  1. MWT

静态索引是线性索引的一种优化, 将索引本身构建成一棵树, 将数据构成一个个的子节点, 其中某一些子节点加上唯一的父节点, 就是线性索引中的某一个块数据集合. 这样子就能更加快速的找到索引(而并非顺序查找), 你看, 很多知识点都是一步步累积的提出, 并非一蹴而就的.

MWT 可以指代 “Multiway Trie”，也称为 “Radix Tree” 或 “Patricia Tree”。MWT 是一种高效的数据结构，用于存储和管理字符串键值的静态索引。

MWT 的主要特点是基于前缀的键值存储和搜索。它通过将键值按照共同的前缀进行组织，以节省存储空间并提高搜索效率。MWT 在内部使用了一个多叉树结构，其中每个节点代表一个字符串的字符，路径上的字符拼接形成键值。

MWT 的一些关键特性和优势包括：

  1. 节省空间：MWT 只存储键值的前缀和不同的字符，而不重复存储相同前缀的字符。这种前缀压缩的方式可以大大减少索引的存储空间。
  2. 高效的搜索：由于共享前缀的存储方式，MWT 可以通过跳过相同的前缀来快速定位到目标键值。这使得搜索操作的时间复杂度为 O(k)，其中 k 是键值的长度。
  3. 支持范围查询：MWT 可以方便地支持范围查询，即检索具有特定前缀的所有键值。
  4. 适用于静态数据集合：MWT 适用于静态数据集合，因为它在索引构建后不支持动态的插入和删除操作。

MWT 在许多应用中被广泛使用，例如网络路由表、编译器符号表、字符串字典等。它为存储和检索字符串键值提供了高效的解决方案，并在静态索引中展现出良好的性能。

  1. 倒排

上述所有索引都是(key, value)的结构, 但是倒排索引却是将某一个 value 作为键值, 实现这样的效果: (value, key), 类似 SQL 中 Where 命令效果:

1
select id, nickname from account where nickname like '%bamboo%';

这样就能快速的基于属性进行检索, 得到所有主键值(id). 倒排索引的存储代价太大, 如果数据的重复度不高的, value 又很长的化, 相当于存储两倍的(len(value) + len(id))的空间, 另外维护工作量也过于巨大.

  1. ISAM

在静态索引中，ISAM 是一种常见的数据结构，它代表 “Indexed Sequential Access Method”，也称为 “Indexed Sequential Access Memory”。ISAM 是一种用于存储和检索静态数据集合的索引方法。

ISAM 数据结构由两个主要组件组成：索引文件和数据文件。索引文件包含键值和指向数据文件中相应记录的指针。数据文件存储实际的数据记录。ISAM 使用索引文件来加速数据的检索过程，以提供高效的查找和范围查询操作。ISAM 数据结构的一些关键特点和优势包括：

  1. 有序存储：ISAM 数据文件中的记录按照键值的顺序进行有序存储，这使得范围查询变得更加高效。
  2. 索引加速：通过在索引文件中存储键值和对应数据记录的指针，ISAM 可以快速定位和访问目标数据，避免了全表扫描的开销。
  3. 支持范围查询：由于数据记录的有序存储和索引的支持，ISAM 提供了方便的范围查询功能，可以检索满足特定条件的一系列记录。
  4. 适用于静态数据集合：ISAM 适用于静态数据集合，即在索引构建后不发生频繁的插入、删除和更新操作。

ISAM 在许多应用中被广泛使用，特别是在数据库管理系统中。它提供了一种有效的方法来组织和管理静态数据，以提供高效的检索功能和范围查询操作。ISAM 的性能受到索引文件的大小和维护成本的影响，因此需要仔细权衡和优化索引设计，以满足具体应用的需求。

动态

  1. B 树

B-树(平衡多路查找树)的提出, 主要用以确保在外存索引结构中树的平衡性, 从而减少外存访问开销. 保证查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成. 简单定义如下, 对于 m 阶的 B-树, 其中 M 表示分叉:

  • 根节点至少包含两个子节点, 除非仅仅存在一个根节点
  • 每个节点至多有 m 个子结点, 每一个内结点至多有[ceil(m/2)]个孩子(向上取整).
  • 所有的叶子结点都处于相同的深度
  • 如果某一个内结点(非 root, 非叶子), 若该结点含有 s 个键值, 那么该结点一定存在 s+1 个子节点

search-btree1

详细信息见B-tree

  1. 红黑树

红黑树(二叉查找树), 在二叉查找树的基础上增加了着色和相关性质, 使得红黑树相对平衡, 确保红黑树的查找, 插入, 删除的时间复杂度最坏为 O(logn). 红黑树的定义如下, 对于有 n 个结点的红黑树, 其高度使用在 logn 下:

  • 每一个结点要么红, 要么黑
  • 根节点是黑的
  • 每一个叶节点是黑的
  • 如果一个节点是红的, 那么他们的子节点是黑的
  • 对于任意结点, 其到叶子结点的每一条路径都包含相同的黑结点

rbtree

详细信息见rbtree.

七大算法

顺序查找

顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于 k 的结点，表示查找失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 返回目标值在列表中的索引位置
    return -1  # 如果未找到目标值，则返回 -1

# 示例用法
data = [5, 2, 8, 10, 3, 1, 6]
target = 10
result = sequential_search(data, target)
if result != -1:
    print("目标值 {} 在索引位置 {} 上找到了。".format(target, result))
else:
    print("目标值 {} 未找到。".format(target))

二分查找

  1. 二分查找

二分查找也称为折半查找，是一种高效的查找算法，但前提是数据集合必须是有序的。它的原理是通过将待查找的数据集合分成两部分，并根据目标值与中间元素的比较结果，决定继续在左半部分还是右半部分进行查找，直到找到匹配的元素或确定不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 返回目标值在列表中的索引位置
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 如果未找到目标值，则返回 -1

# 示例用法
data = [1, 2, 3, 5, 6, 8, 10]
target = 6
result = binary_search(data, target)
if result != -1:
    print("目标值 {} 在索引位置 {} 上找到了。".format(target, result))
else:
    print("目标值 {} 未找到。".format(target))

  1. 插值查找

折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的），比如1~10000之间的大部分数值都分布在 100 以内，此时二分法的很多步骤都是无用的，为了解决该问题提出了插值查找算法。

插值查找的关键在于计算插值位置 pos，该位置不是简单地取中间值，而是根据目标值与数组元素之间的关系进行估计。这使得插值查找在数据分布均匀的情况下能够更快地定位到目标值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def interpolation_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right and arr[left] <= target <= arr[right]:
        # 计算插值位置
        pos = left + ((target - arr[left]) * (right - left)) // (arr[right] - arr[left])

        if arr[pos] == target:
            return pos  # 返回目标值在列表中的索引位置
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1

    return -1  # 如果未找到目标值，则返回 -1

# 示例用法
data = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = interpolation_search(data, target)
if result != -1:
    print("目标值 {} 在索引位置 {} 上找到了。".format(target, result))
else:
    print("目标值 {} 未找到。".format(target))

其中插值查找和二分查找的基本逻辑是一样的，唯一的不同点就是 pos 的计算方式有问题。

  1. 斐波那契查找

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 1:0.618 或 1.618:1。随着斐波那契数列的递增，前后两个数的比值会越来越接近 0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中，结合了二分查找和黄金分割原理，具有较好的查找效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def fibonacci_search(arr, target):
    fib_m_minus_2 = 0  # (m-2)th Fibonacci number
    fib_m_minus_1 = 1  # (m-1)th Fibonacci number
    fib_m = fib_m_minus_2 + fib_m_minus_1  # mth Fibonacci number

    # 计算最小的大于等于数组大小的斐波那契数
    while fib_m < len(arr):
        fib_m_minus_2 = fib_m_minus_1
        fib_m_minus_1 = fib_m
        fib_m = fib_m_minus_2 + fib_m_minus_1

    offset = -1  # 偏移量

    while fib_m > 1:
        i = min(offset + fib_m_minus_2, len(arr) - 1)

        if arr[i] < target:
            fib_m, fib_m_minus_1, fib_m_minus_2 = fib_m_minus_1, fib_m_minus_2, fib_m_minus_1 - fib_m_minus_2
            offset = i
        elif arr[i] > target:
            fib_m, fib_m_minus_1, fib_m_minus_2 = fib_m_minus_2, fib_m_minus_1 - fib_m_minus_2, fib_m_minus_2 - (fib_m_minus_1 - fib_m_minus_2)
        else:
            return i  # 返回目标值在列表中的索引位置

    if fib_m_minus_1 == 1 and arr[offset + 1] == target:
        return offset + 1  # 处理最后一个元素的情况

    return -1  # 如果未找到目标值，则返回 -1

# 示例用法
data = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = fibonacci_search(data, target)
if result != -1:
    print("目标值 {} 在索引位置 {} 上找到了。".format(target, result))
else:
    print("目标值 {} 未找到。".format(target))

树表查找

树查找算法一直在不断地演化中，从二叉树被提出来之后，后续的很多树查找算法都是基于此进行的改进和优化，下面是常见的几个数查找算法：

  • 树表查找-二叉树:
  • 树表查找-AVL 树（平衡二叉树）: 在每个节点上维护一个平衡因子来确保树的平衡性，后面的四个都是 AVL 的变种和优化
  • 树表查找-2-3 查找树：
  • 树表查找-红黑树
  • 树表查找-B 树
  • 树表查找-B+树

它们的发展历史如下：

算法名 提出时间 解决问题
二叉树（Binary Tree） 1960 年 提供基本的有序存储结构，支持快速查找和插入操作
二叉平衡查找树（Balanced Binary Search Tree） 1962 年 解决二叉查找树可能出现的不平衡问题，保持树的平衡性
2-3 查找树（2-3 Search Tree） 1962 年 支持更高的查找和插入效率，处理大量动态数据
红黑树（Red-Black Tree） 1972 年 解决平衡二叉查找树的性能问题，提供快速的查找、插入和删除操作
B 树（B-Tree） 1972 年 优化磁盘存储和访问的效率，适用于大规模数据存储和高效查找
B+树（B+ Tree） 1972 年 提供更高的范围查询和顺序访问性能，适用于数据库索引和文件系统索引

上述各个树查找算法更详细的信息见检索-树检索说明。

分块查找

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。将 n 个数据元素”按块有序”划分为 m 块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第 1 块中任一元素的关键字都必须小于第 2 块中任一元素的关键字；而第 2 块中任一元素又都必须小于第 3 块中的任一元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def block_search(blocks, indexes, target):
    # 在索引块中查找目标块
    block_index = 0
    while block_index < len(indexes) - 1 and indexes[block_index + 1] <= target:
        block_index += 1

    # 在目标块中顺序查找目标值
    block = blocks[block_index]
    for i in range(len(block)):
        if block[i] == target:
            return block_index * len(block) + i  # 返回目标值在列表中的索引位置

    return -1  # 如果未找到目标值，则返回 -1

# 示例用法
blocks = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
indexes = [3, 6, 9]
target = 5
result = block_search(blocks, indexes, target)
if result != -1:
    print("目标值 {} 在索引位置 {} 上找到了。".format(target, result))
else:
    print("目标值 {} 未找到。".format(target))

哈希查找

哈希查找又称为散列表查找， 具体见第三章的介绍，Hash 是一种典型以空间换时间的算法，比如原来一个长度为 100 的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是 byte 类型数据，那么该数组占用 100byte 空间。现在我们采用 Hash 算法，我们前面说的 Hash 必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的 hash 表，此时，仍然是 100byte 的数组，假设我们需要的 100byte 用来记录键与位置的关系，那么总的空间为 200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def hash_search(dictionary, key):
    if key in dictionary:
        return dictionary[key]  # 返回键对应的值
    else:
        return None  # 如果键不存在，则返回None或其他指定的值

# 示例用法
data = {"apple": 3, "banana": 2, "orange": 5}
key = "banana"
result = hash_search(data, key)
if result is not None:
    print("键 {} 对应的值为 {}。".format(key, result))
else:
    print("键 {} 不存在。".format(key))

下面是哈希查找和其他查找算法的性能比较：

search-hash-compare

参考