当前位置：首页 > news >正文

C++哈希表

news 2025/5/13 11:45:34

一概念

C++ 中的哈希表（Hash Table）是一种通过哈希函数实现高效数据存储与查找的数据结构，其核心思想是将数据的键（Key）通过哈希函数映射到一个固定范围的索引（哈希值），从而直接定位数据的存储位置，实现平均 O(1) 时间复杂度的插入、查找和删除操作。

1）哈希函数（Hash Function）

哈希函数是哈希表的核心工具，它的作用是将任意类型的键（Key）转换为一个 整数（哈希值），通常是一个 size_t 类型的无符号整数。理想情况下，不同的键应映射到不同的哈希值，但实际中可能存在哈希冲突（不同键生成相同哈希值）。

2）哈希冲突与处理

当两个不同的键通过哈希函数生成相同的哈希值时，就会发生哈希冲突。C++ 哈希表（如 unordered_map）通常采用 链地址法（Separate Chaining）处理冲突：
每个哈希值对应一个 “桶”（Bucket，本质是一个链表或红黑树），冲突的元素会被存储在同一个桶的链中。当桶的长度过长时（如超过 8 个元素），为了保证性能，链会自动转换为红黑树（C++11 起）。

C++ 标准库（STL）提供了两种基于哈希表的容器：

unordered_map<Key, Value>：存储键值对（Key-Value），键唯一且无序。
unordered_set<Key>：仅存储键（Key），键唯一且无序（可视为 unordered_map<Key, void> 的简化版）。

二链地址法实现哈希表代码

1.链地址法概念

C++ 哈希表中处理哈希冲突的核心方法之一是链地址法（Separate Chaining，又称开链法）。它通过为每个哈希桶（Bucket）附加一个链表（或树结构）来存储冲突的元素，确保哈希表在冲突时仍能保持高效的插入、查找和删除操作。

链地址法的核心思想

哈希表的底层是一个哈希桶数组（每个桶对应一个索引）。当插入元素时，哈希函数将键映射到某个桶的索引：

若该桶为空，元素直接存入；
若该桶已存在元素（哈希冲突），则将新元素追加到该桶的链（链表或树）中。

2. 哈希表类(链表地址法)

//哈希表类(链表地址法)
template<typename KeyType, typename ValueType>
class HashTable {
private:struct HashNode { //哈希结点KeyType key; //哈希键ValueType value; //哈希值HashNode* next; //指向下一个哈希结点HashNode(const KeyType& key, const ValueType& value) { //哈希结点构造函数this->key = key;this->value = value;next = nullptr;}};size_t size; //哈希表大小HashNode** table; //指向哈希结点指针的指针数组，用来存储哈希表的结点KeyType hash(const KeyType& key) const { //哈希函数，将传入的键进行哈希处理int hashkey = key % size; //取模，将余数作为哈希键if (hashkey < 0) hashkey += size; //若哈希键为负值，将其加上哈希表大小，确保哈希值在有效范围内return hashkey;}public:HashTable(int size = 10000); //构造函数，默认哈希表大小为10000~HashTable(); //析构函数void insert(const KeyType& key, const ValueType& value); //插入键值对void remove(const KeyType& key); //删除键值对bool find(const KeyType& key, ValueType& value) const; //查找指定键的值
};

哈希表类包含哈希结点、哈希表大小、指向哈希结点指针的指针数组（用来存储哈希表的结点）和各个成员函数。哈希结点包含哈希键、哈希值和指向下一个哈希结点的next指针。哈希函数将传入的键进行哈希处理，首先对键进行取模，将余数作为哈希键，若哈希键为负值，将其加上哈希表大小，确保哈希键在有效范围内。

3.构造函数

template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::HashTable(int size) {this->size = size; //将传入的值赋给size，表示哈希表大小table = new HashNode * [size]; //为数组分配内存for (int i = 0; i < size; ++i) { //初始化数组每个元素指向空table[i] = nullptr;}
}

首先将传入的值赋给size，表示哈希表大小，接着为数组分配内存，然后初始化数组每个元素指向空。

4.析构函数

//析构函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {for (int i = 0; i < size; ++i) { //遍历哈希表if (table[i]) { //若table[i]不为空，则遍历删除链表HashNode* curr = table[i];while (curr) {HashNode* temp = curr;curr = curr->next;delete temp;}}}delete[] table; //释放哈希表数组内存
}

遍历哈希表，若table[i]不为空，则遍历删除链表，最后释放哈希表数组内存。

5.插入键值对

//插入键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {HashNode* newNode = new HashNode(key, value); //创建一个新的哈希表结点int index = hash(key); //获得哈希处理后的键if (table[index] == nullptr) { //若索引位置为空，直接插入哈希表中table[index] = newNode;}else { //若索引位置不为空，采用头插法插入哈希表中newNode->next = table[index];table[index] = newNode;}
}

首先创建一个新的哈希表结点，接着获取哈希处理后的键，若索引位置为空，直接插入哈希表中，若索引位置不为空，采用头插法插入哈希表中。

6.删除键值对

//删除键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType& key) {int index = hash(key); //将传入的键进行哈希化if (table[index]) { //若哈希表索引位置不为空if (table[index]->key == key) { //首先判断哈希链表头结点的键是否与传入的键相等HashNode* next = table[index]->next; //若相等，采取头删法delete table[index];table[index] = next;}else { //若不相等，遍历寻找键值相等的哈希链表结点HashNode* curr = table[index];while (curr->next && curr->next->key != key) {curr = curr->next;}if (curr->next) { //若找到了键值相等的哈希链表结点HashNode* next = curr->next->next; //删去该哈希结点delete curr->next;curr = next;}}}
}

将传入的键进行哈希化。若哈希表索引位置不为空，首先判断哈希链表头结点的键是否与传入的键相等，若相等，采取头删法；若不相等，遍历寻找键值相等的哈希链表结点，若找到了键值相等的哈希链表结点，删去该哈希结点。

7.查找键值对

//查找键值对
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType& key, ValueType& value) const{int index = hash(key); //将传入的键进行哈希化if (table[index]) { //若哈希表索引位置不为空if (table[index]->key == key) { //首先判断哈希链表头结点的键是否与传入的键相等value = table[index]->value; //若相等，将结点的值赋给传入的valuereturn true; //返回true,表示找到}else { //若不相等HashNode* curr = table[index]; //遍历哈希链表寻找键相等的哈希结点while (curr->next && curr->next->key != key) {curr = curr->next;}if (curr->next) { //若找到键相等的哈希结点value = curr->next->value; //将该哈希结点的值赋给传入的valuereturn true; //返回true，表示找到}}}return false; //返回false，表示未找到
}

将传入的键进行哈希化。若哈希表索引位置不为空，首先判断哈希链表头结点的键是否与传入的键相等。若相等，将结点的值赋给传入的value，返回true,表示找到；若不相等，遍历哈希链表寻找键相等的哈希结点，若找到键相等的哈希结点，将该哈希结点的值赋给传入的value，返回true，表示找到。若未找到，则返回false。

8.完整源码

#include<iostream>
using namespace std;//哈希表类(链表地址法)
template<typename KeyType, typename ValueType>
class HashTable {
private:struct HashNode { //哈希结点KeyType key; //哈希键ValueType value; //哈希值HashNode* next; //指向下一个哈希结点HashNode(const KeyType& key, const ValueType& value) { //哈希结点构造函数this->key = key;this->value = value;next = nullptr;}};size_t size; //哈希表大小HashNode** table; //指向哈希结点指针的指针数组，用来存储哈希表的结点KeyType hash(const KeyType& key) const { //哈希函数，将传入的键进行哈希处理int hashkey = key % size; //取模，将余数作为哈希键if (hashkey < 0) hashkey += size; //若哈希键为负值，将其加上哈希表大小，确保哈希键在有效范围内return hashkey;}public:HashTable(int size = 10000); //构造函数，默认哈希表大小为10000~HashTable(); //析构函数void insert(const KeyType& key, const ValueType& value); //插入键值对void remove(const KeyType& key); //删除键值对bool find(const KeyType& key, ValueType& value) const; //查找指定键的值
};//构造函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::HashTable(int size) {this->size = size; //将传入的值赋给size，表示哈希表大小table = new HashNode * [size]; //为数组分配内存for (int i = 0; i < size; ++i) { //初始化数组每个元素指向空table[i] = nullptr;}
}//析构函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {for (int i = 0; i < size; ++i) { //遍历哈希表if (table[i]) { //若table[i]不为空，则遍历删除链表HashNode* curr = table[i];while (curr) {HashNode* temp = curr;curr = curr->next;delete temp;}}}delete[] table; //释放哈希表数组内存
}//插入键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {HashNode* newNode = new HashNode(key, value); //创建一个新的哈希表结点int index = hash(key); //获得哈希处理后的键if (table[index] == nullptr) { //若索引位置为空，直接插入哈希表中table[index] = newNode;}else { //若索引位置不为空，采用头插法插入哈希表中newNode->next = table[index];table[index] = newNode;}
}//删除键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType& key) {int index = hash(key); //将传入的键进行哈希化if (table[index]) { //若哈希表索引位置不为空if (table[index]->key == key) { //首先判断哈希链表头结点的键是否与传入的键相等HashNode* next = table[index]->next; //若相等，采取头删法delete table[index];table[index] = next;}else { //若不相等，遍历寻找键值相等的哈希链表结点HashNode* curr = table[index];while (curr->next && curr->next->key != key) {curr = curr->next;}if (curr->next) { //若找到了键值相等的哈希链表结点HashNode* next = curr->next->next; //删去该哈希结点delete curr->next;curr = next;}}}
}//查找键值对
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType& key, ValueType& value) const{int index = hash(key); //将传入的键进行哈希化if (table[index]) { //若哈希表索引位置不为空if (table[index]->key == key) { //首先判断哈希链表头结点的键是否与传入的键相等value = table[index]->value; //若相等，将结点的值赋给传入的valuereturn true; //返回true,表示找到}else { //若不相等HashNode* curr = table[index]; //遍历哈希链表寻找键相等的哈希结点while (curr->next && curr->next->key != key) {curr = curr->next;}if (curr->next) { //若找到键相等的哈希结点value = curr->next->value; //将该哈希结点的值赋给传入的valuereturn true; //返回true，表示找到}}}return false; //返回false，表示未找到
}

三开放地址法实现哈希表代码

1. 开放地址法概念

C++ 哈希表中处理哈希冲突的另一种核心方法是开放地址法（Open Addressing，又称闭散列法）。与链地址法不同，它无需额外的链表或树结构，所有元素直接存储在哈希表的底层桶数组中。当冲突发生时（即两个键映射到同一桶），通过探测序列（Probing Sequence）在数组中寻找下一个可用位置存储冲突元素。

开放地址法的核心思想

开放地址法的底层是一个连续的桶数组（如长度为 n 的数组）。插入元素时，若目标桶已被占用（冲突），则按特定规则（探测序列）在数组中寻找下一个空闲桶；查找或删除时，需沿相同的探测序列遍历，直到找到目标元素或确认不存在。

2.哈希表类（开放地址法）

//哈希表类（开放地址法）
#define inf -100000 //哈希无效值
template<typename KeyType, typename ValueType>
class HashTable {
private:size_t size; //哈希表大小KeyType* keyTable; //哈希表键数组，用来存储哈希键ValueType* valueTable; //哈希表值数组，用来存储哈希值int hash(const KeyType& key) const{ //哈希函数，将传入的键进行哈希处理int hashkey = key % size; //取模，将余数作为哈希键if (hashkey < 0) hashkey += size; //若哈希键为负值，将其加上哈希表大小，确保哈希值在有效范围内return hashkey;}public:HashTable(int size = 10000); //构造函数，默认哈希表大小为10000~HashTable(); //析构函数void insert(const KeyType& key, const ValueType& value); //插入键值对void remove(const KeyType& key); //删除键值对bool find(const KeyType& key, ValueType& value) const; //查找键值对
};

定义哈希无效值。哈希表类包含哈希表大小、哈希表键数组（用来存储哈希键）、哈希表值数组（用来存储哈希值）和各个成员函数。

3.构造函数

//构造函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::HashTable(int size) {this->size = size; //将传入的值作为哈希表大小keyTable = new KeyType[size]; //为键数组分配内存valueTable = new ValueType[size]; //为值数组分配内存for (int i = 0; i < size; ++i) {keyTable[i] = -1;valueTable[i] = inf;}
}

首先将传入的值作为哈希表大小，接着为键数组和值数组分配内存，然后对两个数组进行初始化。

4.析构函数

//析构函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {delete[] keyTable; //释放数组内存delete[] valueTable;
}

析构函数中释放数组内存。

5.插入键值对

//插入键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {int index = hash(key); //将传入的键进行哈希化if (keyTable[index] == -1) { //若键数组索引位置为空，直接将键值对插入两个数组索引位置keyTable[index] = key;valueTable[index] = value;}else { //若键数组索引位置不为空while (keyTable[index] != -1) { //往后寻找空的位置index++;if (index >= size) index = 0; //若索引超出哈希表大小，则从0开始找}keyTable[index] = key; //循环结束表示找到空的位置，将键值对插入两个数组索引位置valueTable[index] = value;}
}

将传入的键进行哈希化。若键数组索引位置为空，直接将键值对插入两个数组索引位置；若键数组索引位置不为空，往后寻找空的位置，若索引超出哈希表大小，则从0开始找，循环结束表示找到空的位置，将键值对插入两个数组索引位置。

6.删除键值对

//删除键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType& key) {int index = hash(key); //将传入的键进行哈希化if (keyTable[index] == key) { //若键数组索引位置元素与传入键相等，直接删除两个数组索引位置元素keyTable[index] = -1;valueTable[index] = inf;}else { //若键数组索引位置元素与传入键不相等while (keyTable[index] != key) { //往后寻找键相等的位置index++;if (index >= size) index = 0; //若索引超出哈希表大小，则从0开始找}keyTable[index] = -1; //循环结束表示找到键相等的位置，进行删除操作valueTable[index] = inf;}
}

将传入的键进行哈希化。若键数组索引位置元素与传入键相等，直接删除两个数组索引位置元素；

若键数组索引位置元素与传入键不相等，往后寻找键相等的位置，若索引超出哈希表大小，则从0开始找，循环结束表示找到键相等的位置，进行删除操作。

7.查找键值对

//查找键值对
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType& key, ValueType& value) const{int index = hash(key); //将传入的键进行哈希化if (keyTable[index] == key) { //若键数组索引位置元素与传入键相等value = valueTable[index];//将值数组索引位置元素赋给传入的valuereturn true; //返回true，表示找到}else { //若键数组索引位置元素与传入键不相等while (keyTable[index] != key) { //往后寻找键相等的位置index++;if (index >= size) index = 0; //若索引超出哈希表大小，则从0开始找}value = valueTable[index]; //循环结束表示找到键相等的位置，将值数组索引位置赋给传入的valuereturn true; //返回true，表示找到}return false; //返回false，表示未找到
}

将传入的键进行哈希化。若键数组索引位置元素与传入键相等，将值数组索引位置元素赋给传入的value，返回true，表示找到；若键数组索引位置元素与传入键不相等，往后寻找键相等的位置，若索引超出哈希表大小，则从0开始找，循环结束表示找到键相等的位置，将值数组索引位置赋给传入的value，返回true，表示找到。若未找到，则返回false。

8.完整源码

#include<iostream>
using namespace std;//哈希表类（开放地址法）
#define inf -100000 //哈希无效值
template<typename KeyType, typename ValueType>
class HashTable {
private:size_t size; //哈希表大小KeyType* keyTable; //哈希表键数组，用来存储哈希键ValueType* valueTable; //哈希表值数组，用来存储哈希值int hash(const KeyType& key) const{ //哈希函数，将传入的键进行哈希处理int hashkey = key % size; //取模，将余数作为哈希键if (hashkey < 0) hashkey += size; //若哈希键为负值，将其加上哈希表大小，确保哈希值在有效范围内return hashkey;}public:HashTable(int size = 10000); //构造函数，默认哈希表大小为10000~HashTable(); //析构函数void insert(const KeyType& key, const ValueType& value); //插入键值对void remove(const KeyType& key); //删除键值对bool find(const KeyType& key, ValueType& value) const; //查找键值对
};//构造函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::HashTable(int size) {this->size = size; //将传入的值作为哈希表大小keyTable = new KeyType[size]; //为键数组分配内存valueTable = new ValueType[size]; //为值数组分配内存for (int i = 0; i < size; ++i) {keyTable[i] = -1;valueTable[i] = inf;}
}//析构函数
template<typename KeyType, typename ValueType>
HashTable<KeyType, ValueType>::~HashTable() {delete[] keyTable; //释放数组内存delete[] valueTable;
}//插入键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {int index = hash(key); //将传入的键进行哈希化if (keyTable[index] == -1) { //若键数组索引位置为空，直接将键值对插入两个数组索引位置keyTable[index] = key;valueTable[index] = value;}else { //若键数组索引位置不为空while (keyTable[index] != -1) { //往后寻找空的位置index++;if (index >= size) index = 0; //若索引超出哈希表大小，则从0开始找}keyTable[index] = key; //循环结束表示找到空的位置，将键值对插入两个数组索引位置valueTable[index] = value;}
}//删除键值对
template<typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::remove(const KeyType& key) {int index = hash(key); //将传入的键进行哈希化if (keyTable[index] == key) { //若键数组索引位置元素与传入键相等，直接删除两个数组索引位置元素keyTable[index] = -1;valueTable[index] = inf;}else { //若键数组索引位置元素与传入键不相等while (keyTable[index] != key) { //往后寻找键相等的位置index++;if (index >= size) index = 0; //若索引超出哈希表大小，则从0开始找}keyTable[index] = -1; //循环结束表示找到键相等的位置，进行删除操作valueTable[index] = inf;}
}//查找键值对
template<typename KeyType, typename ValueType>
bool HashTable<KeyType, ValueType>::find(const KeyType& key, ValueType& value) const{int index = hash(key); //将传入的键进行哈希化if (keyTable[index] == key) { //若键数组索引位置元素与传入键相等value = valueTable[index];//将值数组索引位置元素赋给传入的valuereturn true; //返回true，表示找到}else { //若键数组索引位置元素与传入键不相等while (keyTable[index] != key) { //往后寻找键相等的位置index++;if (index >= size) index = 0; //若索引超出哈希表大小，则从0开始找}value = valueTable[index]; //循环结束表示找到键相等的位置，将值数组索引位置赋给传入的valuereturn true; //返回true，表示找到}return false; //返回false，表示未找到
}