1.HashMap原理
参考我的博客：https://blog.csdn.net/Revendell/article/details/110009858
- 开链法：STL的hashtable便是采用开链法解决冲突。这种做法是在每一个表格元素中维护一个list：散列函数为我们分配某一个list，然后我们在那个list身上执行元素的插入、搜寻、删除等操作。虽然针对list而进行的搜寻只能是一种线性操作，但如果list够短，速度还是够快。使用开链法，表格的负载系数将大于1（元素个数除以表格大小）。
- 动态扩容：buckets聚合体以vector完成，以利动态扩充，vector<node*,Alloc> buckets。num_elements为hashtable中元素个数，bucket_count()返回bucket个数即buckets vector的大小。hashtable的计算元素位置赋予给了函数bkt_num()，通过它调用散列函数取得一个可以执行取模运算的值。开链法并不要求表格大小必须为质数，但STL仍然以质数来设计表格大小，并且先将28个质数计算好，逐渐呈现大约两倍的关系，以备随时访问，同时提供一个函数，用来查询在这28个质数之中最接近某数并大于某数的质数。
2.代码解析
- 数据结构：这个实现选择使用向量和链表来处理可能出现的哈希冲突。
std::vector<std::list<std::pair<K, V>>> table：底层容器是一个向量，其每个元素是一个链表，用于存储具有相同哈希值的键值对。 - 哈希函数：
std::hash<K>()(key)用于生成哈希值，这个哈希函数对许多内置类型都有定义，你也可以根据需要自定义。 - 插入操作：在插入时，首先通过计算哈希值确定需要插入的链表。如果键已经存在，就更新其值，否则在链表尾部插入新的键值对。
- 删除操作：删除时，找到对应的键，并将其从链表中移除。
- 查找操作：查找时，通过哈希和链表搜索来快速找到键对应的值。如果找到了键，则返回关联的值。
3.代码实现
#include <iostream>
#include <vector>
#include <list>
#include <utility>template <typename K, typename V>
class HashMap {
public:HashMap(size_t size = 101) : table(size) {}bool insert(const K& key, const V& value) {size_t idx = hash(key) % table.size();for (auto& kv : table[idx]) {if (kv.first == key) {kv.second = value; // 如果键已经存在，更新值return true;}}table[idx].emplace_back(key, value);return true;}bool erase(const K& key) {size_t idx = hash(key) % table.size();auto& chain = table[idx];for (auto it = chain.begin(); it != chain.end(); ++it) {if (it->first == key) {chain.erase(it);return true;}}return false; // 未找到键}bool find(const K& key, V& value) const {size_t idx = hash(key) % table.size();const auto& chain = table[idx];for (const auto& kv : chain) {if (kv.first == key) {value = kv.second;return true;}}return false; // 未找到键}private:std::vector<std::list<std::pair<K, V>>> table;size_t hash(const K& key) const {// 一个简单的哈希函数return std::hash<K>()(key);}
};int main() {HashMap<std::string, int> map;map.insert("apple", 3);map.insert("banana", 2);map.insert("orange", 5);int value;if (map.find("apple", value)) {std::cout << "Apple: " << value << std::endl;} else {std::cout << "Apple not found" << std::endl;}map.erase("banana");if (map.find("banana", value)) {std::cout << "Banana: " << value << std::endl;} else {std::cout << "Banana not found" << std::endl;}return 0;
}
