一、哈希表基础
哈希表是一种不同于常规数组或链表的数据结构,通过哈希函数将数据映射到不同的槽位上,使得数据的查找、插入和删除操作时间复杂度为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,并加上前面字符的哈希值,最终得到一个哈希值。
四、哈希冲突解决
当两个不同的数据被哈希函数映射到同一个槽位时,就会发生哈希冲突。为了解决哈希冲突,我们通常需要使用链表、开放寻址等技术。以下是开放寻址法的示例代码:
templateclass 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提供了哈希表的实现,我们可以根据业务需求选择不同的实现方式。同时,针对特定的问题场景,我们也可以自己实现哈希表来达到更好的效果。