数据结构——哈希

哈希表 是一种使用哈希函数组织数据的数据结构，它支持快速插入和搜索。

哈希表（又称散列表）的原理为：借助 哈希函数，将键映射到存储桶地址。更确切地说，
1.首先开辟一定长度的，具有连续物理地址的桶数组；
2.当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
3.当我们想要搜索一个键时，哈希表将使用哈希函数来找到对应的桶，并在该桶中进行搜索。

负载因子 又叫装填因子，是哈希表的一个重要参数，它反映了哈希表的装满程度。
实际利用桶的个数 与 桶的总数 的比值，称为负载因子。

哈希函数

哈希函数是哈希表中最重要的组件，用于将键映射到特定的桶。我们使用 y = x % 5 作为散列函数，其中 x 是键值，y 是映射之后对应的桶的索引。

冲突解决

一般情况下，哈希函数会起到压缩键的地址空间的作用，设键的地址空间为 S，桶的地址空间为 T，则有 S≫T。
因此，经过映射之后，不同的数据会不可避免地分配到同一个桶中，这时便产生了冲突。

线性试探法

线性试探法属于开放定址法的一种，所谓线性试探法，就是当插入键 key 时，如果发现桶单元 bucket[hash(key)] 已经被占用，则向下线性寻找，直到找到可以使用的空桶。具体说来，经过第 i 次试探之后，桶单元应为：bucket[(hash(key)+i) mod M], i=1,2,3…

链地址法

解决冲突的另一种办法是将桶内产生冲突的键串联成一个链表。

再哈希法

再哈希法比较典型的应用是双重哈希法，即发生冲突时，通过使用另一个哈希函数来避免冲突。
然而，双重哈希法同样存在一些问题：
1.与线性试探法相比，双重哈希法会消耗较多的时间。
2.在双重哈希法中，删除会使问题变复杂，如果逻辑删除数量太多，则应重新构造哈希表。

公共溢出区法

顾名思义，公共溢出区法就是建立另一个哈希表 dict_overflow 作为公共溢出区，当发成冲突时则将该键保存在该哈希表中。

简单哈希集合

#define MAX_LEN 100000          // 初始化桶的数量class MyHashSet {
private:vector<int> set[MAX_LEN];   // 使用数组实现哈希集合/** 返回对应的桶的索引 */int getIndex(int key) {return key % MAX_LEN;}/** 在特定的桶中搜索键，如果该键不存在则返回 -1 */int getPos(int key, int index) {// 每个桶中包含一个列表，遍历所有桶中的元素来寻找特定的键for (int i = 0; i < set[index].size(); ++i) {if (set[index][i] == key) {return i;}}return -1;}
public:MyHashSet() {}void add(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {// 如果键不存在，则添加set[index].push_back(key);}}void remove(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos >= 0) {// 如果键存在，则删除set[index].erase(set[index].begin() + pos);}}bool contains(int key) {int index = getIndex(key);int pos = getPos(key, index);return pos >= 0;}
};

简单哈希映射

#define MAX_LEN 100000            // 初始化桶的数量class MyHashMap {
private:vector<pair<int, int>> map[MAX_LEN];       // 使用数组实现哈希集合/** 返回指定桶的索引 */int getIndex(int key) {return key % MAX_LEN;}/** 在桶中搜索键，如果不存在则返回 -1 */int getPos(int key, int index) {// 每个桶包含一个数组，遍历桶中的所有元素来查找指定的 keyfor (int i = 0; i < map[index].size(); ++i) {if (map[index][i].first == key) {return i;}}return -1;}public:MyHashMap() {}/** value 始终为正 */void put(int key, int value) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {map[index].push_back(make_pair(key, value));} else {map[index][pos].second = value;}}/** 如果存在映射关系，则返回 value，否则返回 -1 */int get(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {return -1;} else {return map[index][pos].second;}}/** 如果存在 key 的映射，则删除该映射关系 */void remove(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos >= 0) {map[index].erase(map[index].begin() + pos);}}
};