目录
哈希表（Hash Table），也称为散列表（思考：vs平衡二叉树），是一种数据结构，它提供了通过键（key）直接访问存储的值（value）的能力。哈希表的工作原理基于哈希函数（Hash Function），该函数将输入的键映射到表中的一个位置，使得查找、插入和删除操作都能在接近常数时间内完成（理想情况下为O(1)）。
一、基本组成部分
- 哈希函数（Hash Function）：这是一个转换函数，它接收一个键作为输入，并计算出一个索引值，这个索引值用来确定该键值对在表中的位置。
- 哈希表（HashTable）：这是一个数组，用于存储键值对。数组的索引由哈希函数生成的值决定。
- 解决冲突策略：由于不同的键可能映射到相同的索引（称为哈希碰撞或冲突），需要有策略来处理这种情况，常见的方法有开放地址法（线性探测、二次探测、双重散列）和链地址法（在一个位置上使用链表存储多个键值对）。
二、使用方法
-
插入（Insertion）：
- 计算键的哈希值。
- 使用哈希值找到在哈希表中的位置。
- 如果位置为空，直接插入键值对。
- 如果位置已占用（冲突发生），根据冲突解决策略处理，如在该位置链表中添加新节点或寻找下一个可用位置。
-
查找（Search）：
- 对查询的键计算哈希值。
- 使用哈希值定位到哈希表中的位置。
- 检查该位置是否有匹配的键值对，如果有则返回值；如果该位置是链表，则沿着链表查找直到找到或遍历完链表。
-
删除（Deletion）：
- 计算待删除键的哈希值。
- 定位到哈希表中的位置。
- 如果找到匹配的键值对，根据存储方式（直接存储或链表）执行删除操作。
- 如果是链表，可能需要调整链表结构。
三、代码实现
在C++中，我们可以使用STL中的unordered_map来直接实现哈希表的功能，它内部已经处理了哈希函数的选择、冲突解决（通常采用链地址法）等细节。但为了更直观地展示哈希表的基本操作及冲突解决过程，下面我将提供一个简化的哈希表实现示例，这里我们采用链地址法来解决冲突。
#include <iostream>
#include <list>
#include <utility>
class MyHashMap {
static const int SIZE = 10; // 哈希表的大小，实际应用中应根据数据量动态调整
std::list<std::pair<int, int>> table[SIZE]; // 使用链表来解决冲突
public:
// 插入操作
void insert(int key, int value) {
int index = key % SIZE;
for (auto& pair : table[index]) {
if (pair.first == key) { // 如果键已存在，更新其值
pair.second = value;
return;
}
}
table[index].emplace_back(key, value); // 否则，在链表末尾添加新的键值对
}
// 查找操作
int search(int key) {
int index = key % SIZE;
for (const auto& pair : table[index]) {
if (pair.first == key) {
return pair.second; // 找到对应的值并返回
}
}
return -1; // 如果没找到，返回一个特殊值表示（例如-1）
}
// 删除操作
void remove(int key) {
int index = key % SIZE;
table[index].remove_if([key](const std::pair<int, int>& pair) {
return pair.first == key;
});
}
};
int main() {
MyHashMap map;
// 插入操作
map.insert(5, 100);
map.insert(15, 200); // 这里15和5的哈希值相同，会产生冲突
// 查找操作
std::cout << "Value of key 5: " << map.search(5) << std::endl; // 应输出100
std::cout << "Value of key 15: " << map.search(15) << std::endl; // 应输出200
// 删除操作
map.remove(5);
std::cout << "Value of key 5 after deletion: " << map.search(5) << std::endl; // 应输出-1，表示未找到
return 0;
}如何使用链地址法（每个哈希表槽位对应一个链表）来实现一个简单的哈希表类MyHashMap，包括插入（insert）、查找（search）和删除（remove）操作。当两个不同的键经过哈希函数计算后指向同一个槽位（即冲突发生时），它们会被添加到该槽位对应的链表中。这样，即使哈希函数的结果相同，也能通过遍历链表来区分不同的键值对。
注：
删除操作详解：
void remove(int key) {
int index = key % SIZE; // 1. 计算键的哈希值
table[index].remove_if([key](const std::pair<int, int>& pair) { // 2. 在对应哈希槽的链表中删除匹配的键值对
return pair.first == key; // 3. 判断链表中的键是否与待删除的键相等
});
}-
计算键的哈希值：通过
key % SIZE计算得到键的哈希值，这里使用简单的模运算来确定键值对在哈希表中的位置。SIZE是哈希表的大小，之前定义为10。 -
在对应哈希槽的链表中删除匹配的键值对：使用
table[index]访问到目标哈希槽位上的链表，然后调用remove_if方法。remove_if是一个标准库函数，用于从容器中移除满足特定条件的所有元素。 -
判断链表中的键是否与待删除的键相等：
remove_if接受一个谓词（这里是一个lambda函数[key](const std::pair<int, int>& pair) { return pair.first == key; }），用于决定哪些元素需要被移除。这个lambda函数捕获了外部变量key，并在内部比较链表中的每个元素（pair）的第一个元素（即键）是否与key相等。如果相等，意味着找到了匹配的键值对，该元素将被标记为待移除。
remove函数首先通过计算键的哈希值定位到其在哈希表中的槽位，然后在该槽位的链表中查找匹配的键值对，并使用remove_if通过提供的谓词逻辑（键的比较）来移除匹配到的元素。这种方法有效地实现了在哈希表中根据键来删除元素的功能，同时处理了哈希冲突的情况，因为它是在链表中进行操作的。
删除操作中的lambda函数详解：
[key](const std::pair<int, int>& pair) {
return pair.first == key;
}-
**
[key]：这部分称为捕获列表（capture list），用于指定lambda函数体内可以访问的外部变量。这里[key]表示捕获变量key（按值捕获），即将外部的key变量的值复制一份到lambda函数内部使用。这意味着lambda函数内的修改不会影响外部的key变量值。 -
(const std::pair<int, int>& pair)：这是lambda函数的参数列表，定义了一个常量引用参数pair，类型为std::pair<int, int>。这意味着lambda函数会接收一个std::pair类型的对象作为输入，这个对象包含两个整数，分别代表键（first）和值（second）。注：为什么是这个参数，别的参数不可以吗？ （哈希表中的元素是以键值对的形式存储的，即std::pair<int, int>，其中第一个元素是键（first），第二个元素是值（second）。因此，lambda函数需要接收与哈希表中元素类型匹配的参数，以便能够正确地比较和处理这些元素。） -
{ return pair.first == key; }：这是lambda函数的函数体，非常简单，仅包含一个返回语句。它比较链表中元素（pair）的键（pair.first）与要删除的键（key）是否相等。如果相等，函数返回true，表明这个元素满足被移除的条件。
四、代码中如何遍历链表来避免冲突
在上述C++代码示例中，通过链地址法解决哈希冲突，每个哈希表的槽位实质上是一个链表（使用std::list实现）。当遍历链表以区分不同的键值对时，关键在于链表中的每个元素是一个std::pair<int, int>，它存储了一个键值对（键和对应的值）。遍历过程遵循以下逻辑：
1、插入操作中的遍历
在插入操作中，如果发现目标哈希槽位的链表中已有元素，代码实际上并没有真正进行遍历。插入操作是通过检查每个元素的键是否与待插入的键相等来判断是否已存在相同的键，如果找到了匹配的键，则更新其值。如果没有找到匹配项，则直接在链表的末尾添加新的键值对。因此，这里的“遍历”体现在新元素插入到链表的逻辑判断上，但实际上并未对已有元素进行遍历操作。
2、查找操作中的遍历
查找操作中，当到达目标哈希槽位时，确实需要遍历该链表。通过一个循环遍历链表中的每一个std::pair，检查每个对中的first（键）是否等于查找的键。如果找到匹配的键，就返回对应的值（pair.second）。这个过程就是通过逐个检查链表中的元素来区分不同的键值对，直到找到匹配的键或遍历完整个链表。
3、删除操作中的遍历
删除操作中，使用了std::list的remove_if成员函数，该函数接受一个谓词（这里是lambda表达式），用于判断哪些元素需要被移除。遍历链表并检查每个元素的键是否等于待删除的键，如果匹配则标记该元素以移除。remove_if实际上调整了链表中元素的顺序，移除了匹配的元素，并保持了剩余元素的连续性。因此，尽管这里没有显式写出循环遍历的逻辑，但remove_if内部完成了对链表的遍历和匹配项的定位与移除工作。