# 哈希表哈希表通过建立key和value之间的映射，实现高效的元素查询。哈希表的查询、添加、删除效率都比数组和链表快，时间复杂度为O(1)。 | 操作 | 数组 | 链表 | 哈希表 | | -------- | ---- | ---- | ------ | | 查找元素 | O(n) | O(n) | O(1) | | 添加元素 | O(1) | O(1) | O(1) | | 删除元素 | O(n) | O(n) | O(1) | 哈希表常用操作 ```cpp unordered_map map; map[12836] = "小哈" map[15937] = "小啰" map[16750] = "小算" map[13276] = "小法" map[10583] = "小鸭" string name = map[15937]; map.erase(10583); ``` 遍历方式 ```cpp for(auto kv : map) { cout << kv.first << "->" << kv.second << endl; } for(auto iter = map.begin(); iter != map.end(); iter++){ cout << iter->first << "->" << iter->second << endl; } ``` ## 哈希表的实现 ```cpp struct Pair { public: int key; string val; Pair(int key, string val) { this->key = key; this->val = val; } }; class ArrayHashMap { private: vector buckets; public: ArrayHashMap() { buckets = vector(100); } ~ArrayHashMap(){ for(const auto &bucket : buckets) { delete bucket; } buckets.clear(); } int hashFunc(int key){ int index = key % 100; return index; } string get(index key){ int index = hashFunc(key); Pair *pair = buckets[index]; if(pair == nullptr) return ""; return pair->val; } void put(int key, string val) { Pair *pair = new Pair(key, val); int index = hashFunc(key); buckets[index] = pair; } void remove(int key){ int index = hashFunc(key); delete buckets[index]; buckets[index] = nullptr; } vector pairSet(){ vector pairSet; for(Pair *pair : buckets) { if(pair != nullptr) { pairSet.push_back(pair); } } return pairSet; } vector keySet() { vector keySet; for(Pair *pair : buckets) { if(pair != nullptr){ keySet.push_back(pair->key); } } return keySet; } vector valueSet(){ vector valueSet; for(Pair *pair : buckets) { if(pair != nullptr) { valueSet.push_back(pair->val); } } return valueSet; } void print() { for(Pair *kv : pairSet()) { cout << kv->key << "->" << key->val << endl; } } } ``` ## 哈希冲突通常哈希冲突时不可避免的，因为输入的空间随时大于输出的空间。所以每当遇到哈希冲突时，我们都需要进行哈希扩容。为了提升效率，一般才用下面的策略。 1.改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。 2.仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。 ### 链式地址在原始哈希表中，每个桶仅能存储一个键值对。链式地址将单个元素转换成为链表，将键值对作为链表节点。基于链式地址实现的哈希表的操作方法发生了以下变化。 - 查询元素：输入`key`，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比`key`以查找目标键值对。 - 添加元素：首先通过哈希函数访问链表头节点，然后将节点添加到链表中 - 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查询目标节点并将其删除。链式地址存在以下局限性。 - 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。 - 查询效率降低：因为需要线性遍历链表来查找对应元素。以下代码给出了链式地址哈希表的简单实现，需要注意两点。 - 使用列表（动态数组）代替链表，从而简化代码。在这种设定下，哈希表（数组）包含多个桶，每个桶都是一个列表。 - 以下实现包含哈希表扩容方法。当负载因子超过2/3时，我们将哈希表扩容至原先的2倍。 ```cpp class HashMapChaining { private: int size; int capacity; double loadThres; int extendRatio; vector> buckets; public: HashMapChaining(): size(0), capacity(4), loadThres(2.0 / 3.0), extendRatio(2) { buckets.resize(capacity); } ~HashMapChaining() { for(auto &bucket : buckets) { for(Pair *pair : bucket) { delete pair; } } } int hashFunc(int key) { return key % capacity; } double loadFactor(){ return (double)size / (double)capacity; } string get(int key) { int index = hashFunc(key); for(Pair *pair : buckets[index]) { if(pair->key == key) { return pair->val; } } return ""; } void put(int key, string val) { if(loadFactor() > loadThres) { extend(); } int index = hashFunc(key); for (Pair *pair : buckets[index]){ if(pair->key == key) { pair->val = val; return; } } buckets[index].push_back(new Pair(key, val)); size++; } void remove(int key) { int index = hashFunc(key); auto &bucket = buckets[index]; for(int i = 0; i < bucket.size(); i++){ if(bucket[i]->key == key) { Pair *tmp = bucket[i]; bucket.erase(bucket.begin() + i); delete tmp; size--; return; } } } void extend() { vector> bucketsTmp = buckets; capacity *= extendRatio; buckets.clear(); buckets.resize(capacity); size = 0; for (auto &bucket : bucketsTmp) { for(Pair *pair : bucket) { put(pair->key : bucket); delete pair; } } } void print() { for(auto &bucket : buckets) { cout << "["; for (Pair *pair : bucket){ cout << pair->key << " -> " << pair->val << ", "; } cout << "]\n"; } } } ``` ### 开放寻址开放寻址不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。 #### 1.线性探测线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。 - 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为1），直至找到空桶，将元素插入其中。 - 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回value;如果遇到空桶，说明目标元素不在哈希表中，返回None。 ```cpp class HashMapOpenAddressing { private: int size; int capacity = 4; const double loadThres = 2.0 / 3.0; const int extendRatio = 2; vector buckets; Pair *TOMBSTONE = new Pair(-1, "-1"); public: HashMapOpenAddressing() : size(0), buckets(capacity, nullptr) {} ~HashMapOpenAddressing() { for (Pair *pair : buckets) { if(pair != nullptr && pair != TOMBSTONE) { delete pair; } } delete TOMBSTONE; } int hashFunc(int key) { return key % capacity; } double loadFactor() { return (double)size / capacity; } int findBucket(int key) { int index = hashFunc(key); int firstTombstone = -1; while(buckets[index] != nullptr) { if(buckets[index]->key == key) { if(firstTombstone != -1) { buckets[firstTombstone] = buckets[index]; buckets[index] = TOMBSTONE; return firstTombstone; } return index; } if(firstTombstone == -1 && buckets[index] == TOMBSTONE) { firstTombstone = index; } index = (index + 1) % capacity; } return firstTombstone == -1 ? index : firstTombstone; } string get(int key) { int index = findBucket(key); if(buckets[index] != nullptr && buckets[index] != TOMBSTONE) { return buckets[index]->val; } return ""; } void put(int key, string val) { if(loadFactor() > loadThres) { extend(); } int index = findBucket(key); if(buckets[index] != nullptr && buckets[index] != TOMBSTONE) { buckets[index]->val = val; return; } buckets[index] = new Pair(key, val); size++; } void remove(int key) { int index = findBucket(key); if(buckets[index] != nullptr && buckets[index] != TOMBSTONE) { delete buckets[index]; buckets[index] = TOMBSTONE; size--; } } void extend() { vector bucketsTmp = buckets; capacity *= extendRatio; buckets = vector(capacity, nullptr); size = 0; for(Pair *pair : bucketsTmp) { if(pair != nullptr && pair != TOMBSTONE) { put(pair->key, pair->val); delete pair; } } } void print(){ for(Pair *pair : buckets) { if(pair == nullptr) { cout << "nullptr" << endl; } else if (pair == TOMBSTONE) { cout << "TOMBSTONE" << endl; } else { cout << pair->key << " -> " << pair->val << endl; } } } } ``` #### 2.平方探测平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步速，而是跳过“探测次数的平方”的步数，即1,4,9，...步。平方探测主要具有以下优势。 - 平方探测通过跳过探测次数平方的距离，试图缓解线性探测到聚焦效应。 - 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。然而，平方探测并不是完美的。 - 仍然存在聚焦现象，即某个位置比其他位置更容易被占用。 - 由于平方的增长，平方探测可能不会探测整个哈希表，意味着即使哈希表中有空桶，平方探测也可能无法访问到它。 #### 3.多次哈希顾名思义，多次哈希方法使用多个哈希函数进行探测。 - 插入元素：若哈希函数f1(x)出现冲突，则尝试f2(x)，以此类推，直到空位后插入元素。 - 查找元素：在相同的哈希函数顺序下进行查找，直到返回目标元素时返回;若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回None. ## 哈希算法为了实现“即快又稳”的哈希表数据结构，哈希算法应具备以下特点。 - 确定性：对于相同的输入，哈希算法应当产生相同的输出。这样才能保证哈希表的可靠性 - 效率高：计算哈希值的过程应当足够快。计算开销越小，哈希表的实用性越高。 - 均匀分布：哈希算法应当使键值对均匀分布在哈希表中。分布越均匀，哈希冲突的概率就越低。实际上，哈希算法除了可以用于实现哈希表，还广泛用于其他领域中。 - 密码存储 - 数据完整性检查对于密码学的相关应用，为了防止从哈希值推导出原始密码等逆向工程，哈希算法需要具备更高级的安全特性。 - 单向性：无法通过哈希值推出关于输入的任何数据。 - 抗碰撞性：应当极难的找到两个不同输入，使得它们的哈希值相同。 - 雪崩效应：输入的微小变化应当导致输出的显著不可预测的变化。值得注意的是“均匀分布”与“抗碰撞性”是两个独立的概念，满足均匀分布不一定满足抗碰撞性。比如之前的案例用使用`key%100`可以产生均匀分布的输出。但是该哈希算法过于简单，所有后两位相等的key的输出都相同，因此可以很轻易的从哈希值中反推出可用的key,从而破解密码。 ### 哈希算法的设计哈希算法的设计上一个需要考虑许多因素的复杂问题，然而对于要求不高的场景中，我们也能设计一些简单的哈希算法。 - 加法哈希：对于输入的每个字符ASCII码进行相加，将得到总和作为哈希值。 - 乘法哈希：利用乘法的不相关信，每轮乘一个常数，将各个字符的ASCII码累积到哈希值中。 - 异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。 - 旋转哈希：将每个字符的ASCII码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作。 ```cpp /* 加法哈希 */ int addHash(string key) { long long hash = 0; const int MODULUS = 1000000007; for(unsigned char c : key) { hash = (hash + (int)c) % MODULUS; } return (int)hash; } /* 乘法哈希 */ int mulHash(string key) { long long hash = 0; const int MODULUS = 1000000007; for(unsigned char c : key) { hash = (31 * hash + (int)c) % MODULUS; } return (int) hash; } /* 异或哈希 */ int xorHash(string key) { int hash = 0; const int MODULUS = 1000000007; for(unsigned char c : key) { hash ^= (int)c; } return hash & MODULUS; } /* 旋转哈希 */ int rotHash(string key) { long long hash = 0; const int MODULUS = 1000000007; for(unsigned char c : key) { hash = ((hash << 4) ^ (hash >> 28) ^ (int)c) % MODULUS; } return (int)hash; } ``` 在上面的哈希算法中可以看到算法的最后一步都是对最大质数`1000000007`取模，以确保哈希值在合适的范围内。值得思考的是，为什么要强调对质数取模，或者说对合数取模的弊端是什么？这是一个有趣的问题。先给出结论：使用最大质数作为模数，可以最大化地保证哈希值的均匀分布。因为质数不与其他数字存在公约数，可以减少取模操作产生的周期性模式，从而避免哈希冲突。举个例子，假设我们选择合数9作为模数，它可以被3整除，那么所有可以被3整除的key都会映射到0、3、6这三个哈希值。如果输入`key`恰好满足这种等差数列的数据分布情况，那么哈希值就会出现聚堆，从而加重哈希冲突。现在假设将`modulus`替换成13，由于`key`和`modulus`之间不存在公约数，因此输出的哈希值均匀性会明显提升。