- duanjiajun's blog
【五一节培训】哈希表的基本操作
- 2024-5-2 16:26:43 @
伟大的理论
哈希表(Hash Table):通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value ,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 哈希函数(Hash Function):将哈希表中元素的关键键值映射为元素存储位置的函数。 哈希冲突(Hash Collision):不同的关键字通过同一个哈希函数可能得到同一哈希地址。 哈希表的两个核心问题是:「哈希函数的构建」 和 「哈希冲突的解决方法」。
常用的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。 常用的哈希冲突的解决方法有两种:开放地址法和链地址法。
伟大的用法
常用的哈希冲突解决方法主要是两类:「开放地址法(Open Addressing)」 和 「链地址法(Chaining)」。
开放地址法(Open Addressing):指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止。
链地址法(Chaining):将具有相同哈希地址的元素(或记录)存储在同一个线性链表中。
最伟大的代码
// STL 容器 映射 map 的基本用法 dict
// 映射 key-value : 理解为 数组的 index-value 随机访问 O(1)
int arr[100]; // 常规数组 定义
arr[1] = 10; // 常规数组 元素赋值
cout << arr[1] << endl; // 常规数组 元素访问
map<string, int> mp; //单重有序映射: 按 key 排序, key 不可重复 (nlogn)
multimap<string, int> mmp; //多重有序映射: 按 key 排序, key 可重复 (nlogn)
unordered_map<string, int> ump; // 单重无序映射,key 不可重复 O(1) ,此类型最为常用
unordered_multimap<string, int> ummp; // 多重无序映射:key 可重复 O(1)
hash["zhujiayi"] = 192; // map 和 unordered_map 可用
hash["zhujiayi"] = 692; // map 和 unordered_map 可用
hash["xianghuiquan"] = 685; // map 和 unordered_map 可用
cout << hash["shuxin"] << endl; // map 和 unordered_map 可用
cout << hash["xianghuiquan"] << endl; // map 和 unordered_map 可用
cout << hash["zhujiayi"] << endl; // map 和 unordered_map 可用
pair<string, int> pr("shuxin", 675); // 对组
hash.insert(pr); // 插入
hash.insert(make_pair("zhujiayi", 692));
hash.insert(make_pair("zhujiayi", 192));
hash.insert(make_pair("xiahuiquan", 685));
hash.insert(make_pair("zhuzhu", 705));
hash.erase("shuxin"); // 删除
cout << hash.size() << endl; // 返回元素总数
for (pair<string, int> pr : hash) { // 哈希的遍历和访问
cout << pr.first << " " << pr.second << endl; // first 对应 键 key, second 对应 值 value
}
cout << "=======" << endl;