网站设计协议,网站内部链接怎么做的,怎么制作游戏辅助,网站快速建设软件下载散列表#xff08;Hash Table#xff09;是一种高效的数据结构#xff0c;广泛用于实现快速的键值对存储。
基本概念
散列表使用哈希函数将键映射到数组的索引。其主要优点在于平均情况下提供常数时间复杂度的查找、插入和删除操作。
哈希函数: 将键映射到一个固定大小的…散列表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::vectorstd::liststd::pairKey, Value table; // 哈希表的数组size_t current_size; // 当前存储的元素数量const float load_factor 0.7; // 负载因子size_t Hash_(const Key key) const {return std::hashKey()(key); // 使用标准哈希函数}void Resize_() {std::vectorstd::liststd::pairKey, 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() {HashTablestd::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;
}代码解析
数据结构: 使用 std::vector 存储链表链表用于处理冲突。每个链表中的元素是 std::pairKey, Value用于存储键值对。 插入操作: 计算哈希值并确定索引。检查索引处是否存在相同的键如果存在则更新值否则插入新键值对。如果当前元素个数超过负载因子则调用 Resize 扩容。 查找操作: 计算索引遍历链表查找对应的键。 删除操作: 计算索引并在链表中查找键找到后删除。 扩容: 创建新的、更大的表重新插入旧表中的元素以保证均匀分布。
开放寻址法
#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::vectorstd::pairKey, Value table; // 散列表的数组size_t current_size; // 当前存储的元素数量const float load_factor; // 负载因子size_t Hash_(const Key key) const {return std::hashKey()(key); // 使用标准哈希函数}void Resize_() {std::vectorstd::pairKey, 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() {HashTablestd::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;
}代码解析
数据结构: 使用 std::vectorstd::pairKey, Value 存储键值对。未使用的槽位初始化为 Key() 和 Value()用于标记空槽。 插入操作: 计算哈希值并确定初始索引。如果发生冲突使用线性探测法查找下一个可用的索引。如果当前元素数量超过负载因子则调用 Resize 方法进行扩容。 查找操作: 计算索引并线性探测直到找到对应的键或到达空槽。 删除操作: 在查找过程中如果找到目标键则标记该位置为已删除。 扩容: 创建一个更大的数组并重新插入旧表中的元素以保持均匀分布。
总结
散列表是一种高效且灵活的数据结构适合用于需要快速查找和存储的场景。通过合理设计哈希函数和冲突处理策略可以实现良好的性能。
