哈希表

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

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

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

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

哈希表常用操作

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

/*初始化哈希表*/
	unordered_map<int, string> map;

	/*添加操作*/
	// 在哈希表中添加键值对（key，value）
	map[123] = "张三";
	map[110] = "李四";
	map[188] = "王五";

	/*查询操作*/
	// 向哈希表中输入键 key 得到值 value
	string name = map[188];
	cout << "姓名：" << name << endl;

	/*删除操作*/
	// 在哈希表中根据键key删除键值对
	map.erase(188);
}

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

	/*遍历哈希表*/
	// 遍历键值对 kay -> 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;
	}

哈希表简单实现

先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此查询操作就是找到key对应的桶，并在桶中获取value。

那么，如何基于key定位到对应的桶呢？ 这是通过哈希函数（hash function）实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有的key，输出空间是所有的桶（数组索引）。换句话说，输入一个key，我们可以通过哈希函数得到该key对应的键值对在数组中的存储位置。

输入一个key，哈希函数的计算过程分为以下两步。

1. 通过某种哈希算法hash()计算得到哈希值。
2. 将哈希值对桶数量（数组长度）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;
		}
	}
};

哈希冲突与扩容

从本质上看，哈希函数的作用是将所有key构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

对于上述示例中的哈希函数，当输入的key后两位相同时，哈希函数的输出结果也相同。例如，查询学号为12836和20336的两个学生时，我们经哈希函数得到的结果均为36。

如图所示，两个学号指向了同一个姓名，这显然是不对的。这样多个输入对应同一输出的情况称为哈希冲突（hash collision）。

容易想到，哈希表容量n越大，多个key被分配到同一个桶中的概率越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

如图所示，扩容前键值对（136，A）和（236，D）发生冲突，扩容后冲突消失。

类似于数组扩容，哈希表扩容需要将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量capacity改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

负载因子（load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在java中，当负载因子超过0.75时，系统会将哈希表扩容至原先的2倍。