温州网站设计联系亿企邦,wordpress 三合一,照片编辑软件,贵阳微网站建设公司哈希表(hash table)#xff0c;又称散列表#xff0c;其通过建立键 key 与值 value 之间的映射#xff0c;实现高效的元素查询。具体而言#xff0c;我们向哈希表输入一个键 key #xff0c;则可以在 \(O(1)\) 时间内获取对应的值 value 。
给定 n 个学生#xff0c;每个…哈希表(hash table)又称散列表其通过建立键 key 与值 value 之间的映射实现高效的元素查询。具体而言我们向哈希表输入一个键 key 则可以在 \(O(1)\) 时间内获取对应的值 value 。
给定 n 个学生每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号返回对应的姓名”的查询功能则可以采用下图所示的哈希表来实现。 除哈希表外数组和链表也可以实现查询功能它们的效率对比如下表所示。
添加元素仅需将元素添加至数组链表的尾部即可使用 \(O(1)\) 时间。查询元素由于数组链表是乱序的因此需要遍历其中的所有元素使用 \(O(n)\) 时间。删除元素需要先查询到元素再从数组链表中删除使用 \(O(n)\) 时间。 观察发现在哈希表中进行增删查改的时间复杂度都是 \(O(1)\) 非常高效。
10.1 哈希表常用操作
哈希表的常见操作包括初始化、查询操作、添加键值对和删除键值对等示例代码如下
/* 初始化哈希表 */
unordered_mapint, string map;/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] 小哈;
map[15937] 小啰;
map[16750] 小算;
map[13276] 小法;
map[10583] 小鸭;/* 查询操作 */
// 向哈希表输入键 key 得到值 value
string name map[15937];/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);哈希表有三种常用的遍历方式遍历键值对、遍历键和遍历值。示例代码如下
/* 遍历哈希表 */
// 遍历键值对 key-value
for (auto kv: map) {cout kv.first - kv.second endl;
}
// 使用迭代器遍历 key-value
for (auto iter map.begin(); iter ! map.end(); iter) {cout iter-first - iter-second endl;
}10.2 哈希表简单实现
我们先考虑最简单的情况仅用一个数组来实现哈希表。在哈希表中我们将数组中的每个空位称为桶(bucket)每个桶可存储一个键值对。因此查询操作就是找到 key 对应的桶并在桶中获取 value 。
那么如何基于 key 定位对应的桶呢这是通过哈希函数(hash function)实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中输入空间是所有 key 输出空间是所有桶数组索引。换句话说输入一个 key 我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。
输入一个 key 哈希函数的计算过程分为以下两步。
通过某种哈希算法 hash() 计算得到哈希值。将哈希值对桶数量数组长度capacity 取模从而获取该 key 对应的数组索引 index 。
index hash(key) % capacity随后我们就可以利用 index 在哈希表中访问对应的桶从而获取 value 。
设数组长度 capacity 100、哈希算法 hash(key) key 易得哈希函数为 key % 100 。图 6-2 以 key 学号和 value 姓名为例展示了哈希函数的工作原理。 以下代码实现了一个简单哈希表。其中我们将 key 和 value 封装成一个类 Pair 以表示键值对。
/* 键值对 */
struct Pair {public:int key;string val;Pair(int key, string val) {this-key key;this-val val;}
};/* 基于数组实现的哈希表 */
class ArrayHashMap {private:vectorPair * buckets;public:ArrayHashMap() {// 初始化数组包含 100 个桶buckets vectorPair *(100);}~ArrayHashMap() {// 释放内存for (const auto bucket : buckets) {delete bucket;}buckets.clear();}/* 哈希函数 */int hashFunc(int key) {int index key % 100;return index;}/* 查询操作 */string get(int 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);// 释放内存并置为 nullptrdelete buckets[index];buckets[index] nullptr;}/* 获取所有键值对 */vectorPair * pairSet() {vectorPair * pairSet;for (Pair *pair : buckets) {if (pair ! nullptr) {pairSet.push_back(pair);}}return pairSet;}/* 获取所有键 */vectorint keySet() {vectorint keySet;for (Pair *pair : buckets) {if (pair ! nullptr) {keySet.push_back(pair-key);}}return keySet;}/* 获取所有值 */vectorstring valueSet() {vectorstring valueSet;for (Pair *pair : buckets) {if (pair ! nullptr) {valueSet.push_back(pair-val);}}return valueSet;}/* 打印哈希表 */void print() {for (Pair *kv : pairSet()) {cout kv-key - kv-val endl;}}
};10.3 哈希冲突与扩容
从本质上看哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间而输入空间往往远大于输出空间。因此理论上一定存在“多个输入对应相同输出”的情况。
对于上述示例中的哈希函数当输入的 key 后两位相同时哈希函数的输出结果也相同。例如查询学号为 12836 和 20336 的两个学生时我们得到
12836 % 100 36
20336 % 100 36如下图所示两个学号指向了同一个姓名这显然是不对的。我们将这种多个输入对应同一输出的情况称为哈希冲突(hash collision)。 容易想到哈希表容量 \(n\) 越大多个 key 被分配到同一个桶中的概率就越低冲突就越少。因此我们可以通过扩容哈希表来减少哈希冲突。
如下图所示扩容前键值对 (136, A) 和 (236, D) 发生冲突扩容后冲突消失。 类似于数组扩容哈希表扩容需将所有键值对从原哈希表迁移至新哈希表非常耗时并且由于哈希表容量 capacity 改变我们需要通过哈希函数来重新计算所有键值对的存储位置这进一步提高了扩容过程的计算开销。为此编程语言通常会预留足够大的哈希表容量防止频繁扩容。
「负载因子 load factor」是哈希表的一个重要概念其定义为哈希表的元素数量除以桶数量用于衡量哈希冲突的严重程度也常作为哈希表扩容的触发条件。例如在 Java 中当负载因子超过 \(0.75\) 时系统会将哈希表扩容至原先的2倍。
