c++中的哈希查找（Hash Search）和B树查找（B-Tree Search）

前言

hello大家好啊，我是文宇，不是文字，是文宇哦，这期也是关于查找算法的。

哈希查找（Hash Search）

哈希查找（Hash Search）是一种基于哈希表的查找算法，它可以在常数时间复杂度（O(1)）内完成查找操作。在C++中，使用哈希查找可以快速地找到某个元素或判断某个元素是否存在于集合中。

哈希函数（Hash Function）哈希函数是哈希查找的核心，它将关键字映射到一个固定范围内的整数值，这个整数值被称为哈希值。哈希函数应该具有以下几个特点：

散列性：对于不同的关键字，哈希函数应该产生不同的哈希值，即使关键字只有微小的差异。
均匀性：哈希值应该均匀地分布在哈希表的所有位置上，减少冲突的发生。

哈希表（Hash Table）哈希表是由一个固定大小的数组和一个哈希函数组成的数据结构。哈希表的大小应该足够大，以便存储所有的关键字，并且能够提供较小的冲突率。每个数组位置称为一个槽（slot），每个槽可以存储一个或多个关键字。
哈希冲突（Hash Collision）哈希冲突是指不同的关键字经过哈希函数计算后得到相同的哈希值。由于哈希函数的输出范围是有限的，而关键字的数量往往是无限的，哈希冲突是不可避免的。为了解决哈希冲突，有多种方法可以选择，常见的方法有链地址法和开放地址法。
链地址法（Chaining）链地址法是最常用的解决哈希冲突的方法之一。在链地址法中，哈希表的每个槽存储一个链表，哈希冲突的关键字被插入到链表中。当需要查找某个关键字时，首先计算其哈希值，然后在对应的槽中遍历链表，直到找到目标关键字或链表结束。链地址法的优点是实现简单，适用于存储大量的关键字。
开放地址法（Open Addressing）开放地址法是另一种解决哈希冲突的方法。在开放地址法中，如果发生哈希冲突，就尝试在哈希表中的其他位置找到空槽来存储关键字。常见的开放地址法有线性探测法和二次探测法等。在开放地址法中，查找某个关键字时，首先计算其哈希值，然后依次检查哈希表中的位置，直到找到目标关键字或遇到空槽。开放地址法的优点是节省内存空间，不需要存储链表的额外空间。
哈希查找的实现在C++中，可以使用标准库提供的unordered_map来实现哈希查找。unordered_map是一个哈希表，可以存储键值对。在unordered_map中查找某个关键字的时间复杂度为O(1)。下面是使用unordered_map实现哈希查找的示例代码：

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> hash_map;// 添加元素hash_map.insert(std::make_pair(1, "apple"));hash_map.insert(std::make_pair(2, "banana"));hash_map.insert(std::make_pair(3, "orange"));// 查找元素auto iter = hash_map.find(2);if (iter != hash_map.end()) {std::cout << "Found: " << iter->second << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

在上面的代码中，我们首先创建了一个unordered_map对象hash_map，然后使用insert函数插入了三个键值对。接着使用find函数查找关键字为2的元素，如果找到了就输出对应的值，否则输出"Not found"。运行上面的代码，输出结果为"Found: banana"。

总结：哈希查找是一种高效的查找算法，它可以在常数时间内完成查找操作。在C++中，可以使用unordered_map来实现哈希查找。要实现哈希查找，需要定义好哈希函数和解决哈希冲突的方法。哈希查找适用于需要快速查找和判断某个元素是否存在的场景，但是需要注意选择合适的哈希函数和适当的哈希表大小，以保证较小的冲突率。

B树查找（B-Tree Search）

B树（B-Tree）是一种自平衡的搜索树数据结构，广泛应用于数据库和文件系统中。B树具有高效的查找、插入和删除操作，能够处理大量数据，并且能够保持树的平衡性。

B树是一颗多叉树，它的每个节点可以存储多个关键字，并且按照关键字的顺序排序。B树具有以下特点：

所有叶节点具有相同的深度，也就是树的高度。
除了根节点和叶节点，其他的节点都包含至少⌈m/2⌉个关键字，其中m是B树的阶数。
每个节点的关键字按照升序排列，并且节点之间存在前后关系。

B树的查找操作是通过比较节点的关键字进行的，具体步骤如下：

从根节点开始，比较待查找关键字与节点中的关键字。
如果找到了相等的关键字，则表示查找成功，返回对应的值。
如果待查找关键字小于当前节点的最小关键字，则继续在当前节点的左子树中查找。
如果待查找关键字大于当前节点的最大关键字，则继续在当前节点的右子树中查找。
如果待查找关键字在当前节点的关键字范围内，则继续在当前节点的子节点中查找。

为了提高B树的查找效率，B树的节点中通常会保存一些额外信息，比如子节点指针或者数据的指针，这样可以在查找过程中进行快速跳转。

具体的查找算法可以通过递归或者循环来实现。下面是一种基于递归的B树查找算法的伪代码：

Node* BTreeSearch(Node* root, KeyType key) {// 如果根节点为空，则表示查找失败if (root == nullptr) {return nullptr;}// 找到关键字对应的位置int i = 0;while (i < root->keyNum && key > root->key[i]) {i++;}// 如果找到了关键字，则返回对应的节点if (i < root->keyNum && key == root->key[i]) {return root;}// 否则，根据关键字的范围继续在子节点中查找if (root->isLeaf) {return nullptr;} else {return BTreeSearch(root->child[i], key);}
}

上述伪代码中的Node表示B树的节点，KeyType表示关键字的类型。该算法从根节点开始查找，如果根节点为空，则表示查找失败；如果找到了关键字，则返回对应的节点；否则，根据关键字的范围继续在子节点中查找。如果当前节点是叶节点，则查找失败；否则，递归地在相应的子节点中查找。

B树的查找算法的时间复杂度为O(logN)，其中N为树中的节点数。由于B树具有平衡性，每个节点平均具有⌈m/2⌉个关键字，树的高度为O(logN)，因此查找操作可以在O(logN)时间内完成。同时，由于B树的节点可以存储多个关键字，相较于二叉搜索树，B树的层次更少，磁盘IO的次数也更少，从而提高了查找的效率。

总结而言，B树是一种高效的自平衡搜索树数据结构，适用于处理大量数据的情况。B树的查找操作可以通过比较节点的关键字进行，具有O(logN)的时间复杂度。B树的查找算法可以通过递归或者循环来实现，具体的实现方式可以根据实际情况选择。