c++ 散列表

散列表（Hash Table）是一种高效的数据结构，广泛用于实现快速的键值对存储。

基本概念

散列表使用哈希函数将键映射到数组的索引。其主要优点在于平均情况下提供常数时间复杂度的查找、插入和删除操作。

• 哈希函数: 将键映射到一个固定大小的数组索引。一个好的哈希函数应该具备：
  • 散列均匀性：不同的键应该尽量映射到不同的索引。
  • 计算简单：哈希值的计算应该高效。

冲突处理

由于多个键可能映射到同一个索引，必须采取措施处理冲突。常见的冲突解决方法包括：

• 链地址法: 在每个数组索引处使用链表存储所有映射到该索引的键值对。
• 开放寻址法: 在数组中查找下一个可用位置，例如线性探测、二次探测和双重散列等方法。

性能分析

时间复杂度:

• 查找：O(1)（平均情况），O(n)（最坏情况，发生冲突时）
• 插入：O(1)（平均情况），O(n)（最坏情况）
• 删除：O(1)（平均情况），O(n)（最坏情况）

空间复杂度: O(n)，即存储元素的数量。

负载因子（Load Factor）: 定义为元素数量与表大小的比率。一般在负载因子超过一定阈值（如0.7）时进行扩容，以保持性能。

代码实现

链地址法

#include <iostream>
#include <vector>
#include <list>
#include <utility> // for std::pair
#include <functional> // for std::hashtemplate <typename Key, typename Value>
class HashTable {
public:HashTable(size_t size = 10) : table(size), current_size(0) {}void Insert(const Key& key, const Value& value) {size_t index = Hash_(key) % table.size();for (auto& pair : table[index]) {if (pair.first == key) {pair.second = value; // 更新值return;}}table[index].emplace_back(key, value); // 插入新键值对current_size++;if (current_size > table.size() * load_factor) {Resize_();}}bool Get(const Key& key, Value& value) const {size_t index = Hash_(key) % table.size();for (const auto& pair : table[index]) {if (pair.first == key) {value = pair.second;return true;}}return false; // 未找到}bool Remove(const Key& key) {size_t index = Hash_(key) % table.size();auto& cell = table[index];for (auto it = cell.begin(); it != cell.end(); ++it) {if (it->first == key) {cell.erase(it); // 删除current_size--;return true;}}return false; // 未找到}private:std::vector<std::list<std::pair<Key, Value>>> table; // 哈希表的数组size_t current_size; // 当前存储的元素数量const float load_factor = 0.7; // 负载因子size_t Hash_(const Key& key) const {return std::hash<Key>()(key); // 使用标准哈希函数}void Resize_() {std::vector<std::list<std::pair<Key, Value>>> old_table = table;table.resize(old_table.size() * 2); // 扩容current_size = 0;for (const auto& cell : old_table) {for (const auto& pair : cell) {Insert(pair.first, pair.second); // 重新插入}}}
};int main() {HashTable<std::string, int> hash_table;hash_table.Insert("apple", 1);hash_table.Insert("banana", 2);int value;if (hash_table.Get("apple", value)) {std::cout << "apple: " << value << std::endl; // 输出: apple: 1}hash_table.Remove("apple");if (!hash_table.Get("apple", value)) {std::cout << "apple not found" << std::endl; // 输出: apple not found}return 0;
}

代码解析

1. 数据结构:
   • 使用 std::vector 存储链表，链表用于处理冲突。
   • 每个链表中的元素是 std::pair<Key, Value>，用于存储键值对。
2. 插入操作:
   • 计算哈希值并确定索引。
   • 检查索引处是否存在相同的键，如果存在则更新值，否则插入新键值对。
   • 如果当前元素个数超过负载因子，则调用 Resize 扩容。
3. 查找操作:
   • 计算索引，遍历链表查找对应的键。
4. 删除操作:
   • 计算索引并在链表中查找键，找到后删除。
5. 扩容:
   • 创建新的、更大的表，重新插入旧表中的元素以保证均匀分布。

开放寻址法

#include <iostream>
#include <vector>
#include <utility> // for std::pair
#include <stdexcept> // for std::out_of_rangetemplate <typename Key, typename Value>
class HashTable {
public:HashTable(size_t size = 10) : table(size), current_size(0), load_factor(0.7) {}void Insert(const Key& key, const Value& value) {if (current_size >= table.size() * load_factor) {Resize_();}size_t index = Hash_(key) % table.size();while (table[index].first != Key() && table[index].first != key) {index = (index + 1) % table.size(); // 线性探测}table[index] = { key, value };current_size++;}bool Get(const Key& key, Value& value) const {size_t index = Hash_(key) % table.size();while (table[index].first != Key()) {if (table[index].first == key) {value = table[index].second;return true;}index = (index + 1) % table.size(); // 线性探测}return false; // 未找到}bool Remove(const Key& key) {size_t index = Hash_(key) % table.size();while (table[index].first != Key()) {if (table[index].first == key) {table[index] = { Key(), Value() }; // 标记为删除current_size--;return true;}index = (index + 1) % table.size(); // 线性探测}return false; // 未找到}private:std::vector<std::pair<Key, Value>> table; // 散列表的数组size_t current_size; // 当前存储的元素数量const float load_factor; // 负载因子size_t Hash_(const Key& key) const {return std::hash<Key>()(key); // 使用标准哈希函数}void Resize_() {std::vector<std::pair<Key, Value>> old_table = table;table.resize(old_table.size() * 2, { Key(), Value() }); // 扩容current_size = 0;for (const auto& pair : old_table) {if (pair.first != Key()) {Insert(pair.first, pair.second); // 重新插入}}}
};int main() {HashTable<std::string, int> hash_table;hash_table.Insert("apple", 1);hash_table.Insert("banana", 2);int value;if (hash_table.Get("apple", value)) {std::cout << "apple: " << value << std::endl; // 输出: apple: 1}hash_table.Remove("apple");if (!hash_table.Get("apple", value)) {std::cout << "apple not found" << std::endl; // 输出: apple not found}return 0;
}

代码解析

1. 数据结构:
   • 使用 std::vector<std::pair<Key, Value>> 存储键值对。未使用的槽位初始化为 Key() 和 Value()，用于标记空槽。
2. 插入操作:
   • 计算哈希值并确定初始索引。
   • 如果发生冲突，使用线性探测法查找下一个可用的索引。
   • 如果当前元素数量超过负载因子，则调用 Resize 方法进行扩容。
3. 查找操作:
   • 计算索引并线性探测，直到找到对应的键或到达空槽。
4. 删除操作:
   • 在查找过程中，如果找到目标键，则标记该位置为已删除。
5. 扩容:
   • 创建一个更大的数组并重新插入旧表中的元素，以保持均匀分布。

总结

散列表是一种高效且灵活的数据结构，适合用于需要快速查找和存储的场景。通过合理设计哈希函数和冲突处理策略，可以实现良好的性能。