一、哈希表基础
哈希表是一种不同于常规数组或链表的数据结构，通过哈希函数将数据映射到不同的槽位上，使得数据的查找、插入和删除操作时间复杂度为O(1)。C++ STL中提供了unordered_map和unordered_set两个哈希表的实现，它们的底层实现都是使用哈希表。
使用哈希表时，我们通常需要关注哈希函数的设计和冲突解决方法。哈希函数应当将数据均匀地分散在不同的槽位上，并且能够处理不同类型的数据；而冲突解决方法则需要保证数据不会重复，并且插入、删除时不会影响其他数据。
二、unordered_map用法
unordered_map是C++ STL中实现的哈希表，其使用方法与map基本相同，但相比于map，其查找、插入、删除的时间复杂度更低且不需要数据排序。以下是unordered_map的简单示例：
#include
#include
#include
using namespace std;
int main() {
unordered_map m;
m[1] = "hello";
m[2] = "world";
m[3] = "!";
cout << m[2] << endl; // 输出 world
return 0;
}
在上述代码中，我们使用了unordered_map来存储int和string类型的键值对，通过下标访问map中的元素，并输出了键为2的元素的值。
三、哈希函数设计
哈希函数是哈希表的核心，一个好的哈希函数能够有效地减少数据冲突。以下是一个简单的哈希函数设计：
size_t hash_func(const string& str) {
size_t hash_value = 0;
for (const auto& c : str) {
hash_value = 31 * hash_value + c;
}
return hash_value;
}
在上述代码中，我们采用了djb2哈希算法，将每个字符的ASCII码乘以一个质数31，并加上前面字符的哈希值，最终得到一个哈希值。
四、哈希冲突解决
当两个不同的数据被哈希函数映射到同一个槽位时，就会发生哈希冲突。为了解决哈希冲突，我们通常需要使用链表、开放寻址等技术。以下是开放寻址法的示例代码：
template
class OpenAddrHashTable {
public:
explicit OpenAddrHashTable(size_t size = 1000) : size_(size) {
table_ = new std::pair[size];
++size_;
}
~OpenAddrHashTable() {
delete[] table_;
}
OpenAddrHashTable(const OpenAddrHashTable&) = delete;
OpenAddrHashTable& operator=(const OpenAddrHashTable&) = delete;
void insert(const Key& key, const Value& value) {
size_t hash_value = hash_func(key);
size_t i = hash_value % size_;
size_t j = i;
while (table_[j].first != key && table_[j].first != Key()) {
++j;
if (j == size_)
j = 0;
if (j == i)
throw std::runtime_error("hash table full");
}
table_[j] = std::make_pair(key, value);
}
Value& search(const Key& key) const {
size_t i = hash_func(key) % size_;
size_t j = i;
while (table_[j].first != key && table_[j].first != Key()) {
++j;
if (j == size_)
j = 0;
if (j == i)
throw std::runtime_error("key not found");
}
return table_[j].second;
}
private:
size_t size_;
std::pair* table_;
size_t hash_func(const Key& key) const {
// 哈希函数的实现
}
};
在OpenAddrHashTable中，我们使用了开放寻址法来解决哈希冲突。当数据插入时，如果对应的槽位已经被占用，就从下一个槽位开始往后查找，直到找到空槽位为止；当数据查找时，如果对应的槽位不是要查找的数据，就继续从下一个槽位开始往后查找，直到找到要查找的数据或者槽位为空为止。
五、总结
哈希表是一种高效的数据结构，适用于需要快速查找、插入和删除的场景。C++ STL中通过unordered_map和unordered_set提供了哈希表的实现，我们可以根据业务需求选择不同的实现方式。同时，针对特定的问题场景，我们也可以自己实现哈希表来达到更好的效果。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/183555.html
微信扫一扫 
支付宝扫一扫 