算法与数据结构——哈希表

news/2024/10/11 20:26:35

哈希表

哈希表（hash table），又称散列表，它通过建立键key与值value之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键key，则可以在O(1)时间内获取对应的值value。

除哈希表外，数组和链表也可以实现查询功能，他们的效率对比如下表：

添加元素：仅需将元素添加至数组（链表）的尾部即可，使用O(1)时间。
查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用O(n)时间。
删除元素：需要先查询到元素，再从数组（链表）中删除，使用O(n)时间。

	数组	链表	哈希表
查找元素	O(n)	O(n)	O(1)
添加元素	O(1)	O(1)	O(1)
删除元素	O(n)	O(n)	O(1)

观察发现，在哈希表中进行增删改查操作的时间复杂度都是O(1)，非常高效。

哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等，C++中提供了现成的哈希表类：

/*初始化哈希表*/unordered_map<int, string> map;/*添加操作*/// 在哈希表中添加键值对（key，value）map[123] = "张三";map[110] = "李四";map[188] = "王五";/*查询操作*/// 向哈希表中输入键 key 得到值 valuestring name = map[188];cout << "姓名：" << name << endl;/*删除操作*/// 在哈希表中根据键key删除键值对map.erase(188);
}

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。

	/*遍历哈希表*/// 遍历键值对 kay -> valuefor (auto kv : map){cout << kv.first << " -> " << kv.second << endl;}// 使用迭代器遍历key -> valuefor (auto iter = map.begin(); iter != map.end(); iter++){cout << iter->first << " -> " << iter->second << endl;}

哈希表简单实现

先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶（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。下图以key学号和value姓名为例，展示了哈希函数的工作原理。

以下代码实现了一个简单的哈希表。其中，我们将key和value封装成一个Pair类，以表示键值对。

/*键值对*/
struct Pair{int key;string val;Pair(int key, string val){this->key = key;this->val = val;}
};
/*基于数组实现的哈希表*/
class ArrayHashMap{
private:vector<Pair*> buckets;
public:ArrayHashMap(){// 初始化数组，包含100个桶buckets = vector<Pair*>(100);}~ArrayHashMap(){// 释放内存for (const auto &bucket : buckets){delete bucket;}buckets.clear();}/*哈希函数*/int hashFunc(int key){return key % 100;}/*查询操作*/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);/*迭代器方式删除auto iter = buckets.begin();iter += index;buckets.erase(iter);*/// 置空方式删除delete buckets[index];buckets[index] = nullptr;}/*获取所有键值对*/vector<Pair*> pairSet(){vector<Pair*> pair_set;for (Pair* pair:buckets){if (pair)pair_set.push_back(pair);}return pair_set;}/*获取所有键*/vector<int> keySet(){vector<int> key_set;for (Pair* pair : buckets){if (pair)key_set.push_back(pair->key);}return key_set;}/*获取所有值*/vector<string> valueSet(){vector<string> val_set;for (Pair* pair : buckets){if (pair)val_set.push_back(pair->val);}return val_set;}/*打印哈希表*/void print(){for (Pair* pair : pairSet()){cout << pair->key << "->" << pair->val << endl;}}
};