您现在的位置是：首页 >学无止境 >哈希表详解与实现网站首页学无止境

目录

一、哈希概念剖析

1.1哈希冲突

1.2负载因子

1.3哈希函数

1.3.1除法散列法/除留余数法

1.3.2乘法散列法

1.3.3全域散列法

二、处理哈希冲突

1.1开放定址法

1.1.1线性探测法

1.1.2二次探测法

1.1.3双重散列法

1.2链地址法 

---

一、哈希概念剖析

哈希（Hash）是一种通过哈希函数将关键字与存储位置建立映射关系的数据组织方式，其核心在于利用哈希函数快速计算关键字的位置，从而实现高效查找。

以下将举出最简单的哈希方法：直接定址法。这是一种非常简单高效的哈希方法，特别适合关键字范围比较集中的情况。它的核心思想是：直接用关键字的值或者通过简单的计算，确定数据在数组中的存储位置。

举个例子：
1. 如果关键字的值都在 [0, 99]之间，那我们可以直接开一个长度为100的数组，关键字的值就是数组的下标。比如关键字是5，就存到数组的第5个位置。
2. 如果关键字是 [a, z]的小写字母，我们可以开一个长度为26的数组，用字母的ASCII码减去字母'a'的ASCII码，得到的结果就是数组的下标。比如关键字是'c'，计算方法是 `'c' - 'a' = 2`，所以存到数组的第2个位置。

简单来说，直接定址法就是通过关键字直接算出存储位置，不需要复杂的哈希函数，特别适合关键字范围小且集中的场景。它的本质就是用关键字的值（或者稍微计算一下）作为数组的下标，简单直接！

例题：字符串的第一个唯一字符-力扣（LeedCode）

对于该题我们就可以运用哈希直接定址法的思想解决。建立一个字母数组及其映射关系，通过统计每个位置的数量来找出唯一字符。代码如下：

class Solution {
public:
    int firstUniqChar(string s) {
        // 每个字⺟的ascii码-'a'的ascii码作为下标映射到count数组，数组中存储出现的次数
        int count[26] = {0};
        // 统计次数
        for(auto ch : s)
        {
            count[ch-'a']++;
        } 
        for(size_t i = 0; i < s.size(); ++i)
        {
            if(count[s[i]-'a'] == 1)
            return i;
        } 
        return -1;
    }
}

1.1哈希冲突

不同的关键字（key）通过一系列操作之后映射到同一个位置上的情况被称为哈希冲突或哈希碰撞。那么如何去避免哈希冲突呢？理想情况就是要找出一个好的哈希函数避免冲突（此处的哈希函数将在后文进行介绍），但是实际上冲突是不可避免的，我们只能尽可能设计出优秀的哈希函数，从而减少冲突次数，另外设计解决冲突的方案也是必不可少的。

1.2负载因子

假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子=N / M。在某些场景下，负载因子也被称为载荷因子或者装载因子等。负载因子越大，哈希冲突概率也越高，空间利用率高；相反负载因子越小，哈希冲突的概率就越低，空间利用率越低。

1.3哈希函数

⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，而常见的几种构建哈希函数的方法如下。

1.3.1除法散列法/除留余数法

除法散列法也叫做除留余数法，是目前较为常用的一种设置哈希函数的方法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

tips：

• 当使用除法散列法时，应避免使用某些值作为M，例如2的幂、10的幂等。因为如果M等于2的幂，那么key%M本质上就是保留key的后x位，那么后x位相同的值所得的哈希值也相等。如：{63，31}看起来没有关联的值，如果M是如果M是16，也就是 2^4，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111，他们的后几位都一样。

• 当使⽤除法散列法时，建议M取不太接近2的整数次冥的⼀个质数(素数)。

1.3.2乘法散列法

乘法散列法相较于除法散列法不这么常用。乘法散列法是一种用于哈希表的技巧，它的好处是不用特别在意哈希表的大小M。这个方法主要分两步走：

1. 首先，拿你的关键字K去乘以一个小于1的正数A，然后只取这个乘积的小数部分。
2. 接着，用哈希表的大小M去乘刚才得到的小数部分，最后把结果向下取整，得到一个整数。

这个过程的目的就是把关键字K转换成一个哈希表中的位置，而且这个转换方法比较灵活，不受哈希表大小M的限制。简单来说，就是通过一些数学运算，把任意的关键字K变成一个适合放在哈希表里的位置。

通常h(key) = floor(M × ((A × key)%1.0))，其中floor表示对表达式向下取整，(0 ＜ A ＜ 1。一般来说 A = (√5 - 1) / 2 = 0.6180339887....(⻩⾦分割点)⽐较好。

示例：假设M为1024，key为1234，A = 0.6180339887, A*key = 762.6539420558，取⼩数部分为0.6539420558,  M×((A×key)%1.0) = 0.6539420558*1024 = 669.6366651392，那么h(1234) = 669。

1.3.3全域散列法

如果有人故意使坏，他们可以研究我们公开的哈希函数，然后故意制造一堆数据，这些数据通过哈希函数后都会指向哈希表中的同一个位置，这就会导致严重的冲突，影响哈希表的性能。

为了避免这种情况，我们可以给哈希函数加点“随机调料”，这样即使有人知道哈希函数的基本做法，他们也没法预测或制造出一定会导致冲突的数据。这种通过引入随机性来增强哈希函数安全性的方法，就叫做全域散列。简单来说，就是让哈希函数变得不可预测，以此来防止恶意攻击。

 hab(key) = ((a × key + b)%P )%M，P需要选⼀个足够大的质数，a可以随机选[1,P-1]之间的
任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。
假设P=17，M=6，a = 3， b = 4, 则 h34(8) = ((a × key + b)%P )%M = ((3 × 8 + 4)%17)%6 = 5

当我们使用全域散列（一种增强哈希表安全性的方法）时，需要注意一个关键点。在初始化哈希表的时候，我们需要从一组哈希函数中随机选择一个来使用。一旦选定了这个哈希函数，后续的所有操作（比如插入、删除、查找等）都必须固定使用这个函数，不能随意更换。

如果每次操作都随机选择一个不同的哈希函数，就会导致问题。比如，插入数据时用的是哈希函数A，而查找时却用了哈希函数B，这样就会找不到之前插入的数据，因为两个函数计算的结果可能完全不同。

简单来说，就是选好一个哈希函数后，从头到尾都要用它，不能换来换去，否则数据就乱套了！

二、处理哈希冲突

1.1开放定址法

这是一种解决哈希表冲突的方法。它的核心思想是：所有的数据都直接存放在哈希表里，如果某个关键字key通过哈希函数计算出的位置已经被占用了（发生冲突），就按照一定的规则去找下一个空闲的位置来存放这个key。

在开放定址法中，哈希表的负载因子（即已存放数据占整个表的比例）必须小于1，也就是说，表不能完全被填满，否则就找不到空闲位置了。

具体的规则有三种：

1. 线性探测：如果冲突了，就依次往后找一个空闲的位置。

2. 二次探测：如果冲突了，按照一定的平方规律（比如1, 4, 9, 16...）去找下一个位置。

3. 双重探测：用另一个哈希函数来计算下一个位置，相当于双重保险。

1.1.1线性探测法

规则：先计算key对应的位置，若该位置没有被占用则将key存放入该位置，否则从发生冲突的位置开始，依次线性向后探测，直到找到下一个没有被占用的位置。如果走到了哈希表尾，则回到哈希表头继续开始往后走。

h(key) = hash0 = key % M,  hash0位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M， i = {1, 2, 3, ..., M - 1}，因为负载因子小于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。

对于{19，30，5，36，13，20，21，12}映射到M=11的表中如下图所示：

具体实现过程如下：首先先插入19，19 % 11 = 8，一开始8位置没有被占据，则19可以直接放在位置8中。第二个要插入的数尾30，30 % 11 = 8，这时候我们发现求余的结果也是8而位置8上已经放有19了，那么我们就将30往8位置的下一个9位置存放。第三个要插入的是5，5 % 11 = 5，位置5没有被占用直接放入。第四个要插入的是36，36 % 11 = 3，3没有被占用直接插入。第五个要插入的是13，13 % 11 = 2，2没有被占用直接插入。第六个要插入的是20，20 % 11 = 9，但是此时位置9已经有30在占着了，因此把20往位置9后面找空余的位置，此时10号位为空，将20放入10号位。第七个要插入的是21，21 % 11 = 10，此时20占据了10号位，那么就重新回到表头，此时表头为空，那么就将21插入在0号位。最后要插入的是12，12 % 11 = 1，1号位为空直接插入。

下面就给出线性探测法的具体代码实现。

首先对于每个线性表位置节点来说一共存在三种状态：存在数据、曾经存有数据但已被删除、没有存过数据。另外还需存取数据。因此我们设置两个变量。其中的pair是用来存储key和value的连接关系的。

//用枚举的方法枚举三种状态
enum State {
	EXIST,
	DELETE,
	EMPTY
};

//为了让哈希表适用与所有数据类型这里适用模板
template <class K, class V>
struct HashNode {
	pair<K, V> _kv;
	State _state;

	HashNode():_state(EMPTY){}
	HashNode(pair<K, V>& kv): _kv(kv), _state(EMPTY){}
};

插入数据

1、如果哈希表里本来就存在一个与需要插入的数相同的数，那么就没有新插入的必要了。因此为了避免重复插入，我们可以先查找一下插入的数是否已经存在，存在就直接返回即可无需走插入逻辑。（查找方法在后文实现）

2、先获取hash0作为初步映射位置，只要_table[(hash0 + i) % size]位置的状态为被占用，则一直向后探测。探测结束后令hashi =  (hash0 + i) % size，并对_table[hashi]位置进行赋值并修改其状态为占用，记录哈希表的元素个数的_n++。

3、对于负载因子大于0.7的情况我们就认为需要扩容了，由于_n / _table.size()得出的结果会被向下取整为0，那么我们想要判断负载因子是否大于0.7则可参考下面代码让分子×10和0.7×10，比较除之后的结果与7的大小关系。扩容时你可以选择2倍扩容或者其他方式扩容，但是较为科学的就是让哈希表扩容到一个远离2^n的素数，因此可以参考__stl_next_prime函数，__stl_next_prime不要求掌握。

__stl_next_prime函数

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const size_t __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list +
		__stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

插入核心代码：

bool Insert(const pair<K, V>& kv) {
	if (Find(kv.first))
		return false;

	//负载大于0.7就扩容
	if (_n * 10 / _table.size() >= 7) {
		HashTable<K, V> newtable;
		newtable._table.resize(__stl_next_prime(_table.size() + 1));
		for (auto& data : _table) {
			if(data._state == EXIST)
				newtable.Insert(data._kv);
		}
		std::swap(_table, newtable._table);
	}

	size_t size = _table.size();
	size_t hash0 = kv.first % _table.size();
	size_t i = 0;
	//只要存在就继续往后走
	while (_table[(hash0 + i) % size]._state == EXIST)
	{
		++i;
	}
	size_t hashi =  (hash0 + i) % size;
	_table[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	_n++;

	return true;
}

查找数据 

查找数据目的是找出当前哈希表存不存在key值，具体操作如下。

首先先找key求余映射的点，只要找的位置不为空那就继续找（因为线性探测法中，一个数可能放在他求余的原位置，但也有可能因为该位置被人占了放在了后面的位置），如果找到的_kv.first和key相等并且找到的位置是存在有值的说明找到了，那么就返回当前节点的地址，若没有就++i向后找，如果走到空都找不到说明当前哈希表没有key，返回nullptr。

可能看到这里你会有疑问：为什么要同时满足查找到节点状态为存在并且_kv.first等于key才能返回？这是因为后续的删除操作是只改变节点的状态，告诉操作者那个节点已经进行了删除操作不影响后续插值，但并没有真正把那个节点delete掉。也就是说，如果_kv.first等于key，但该节点的状态为delete说明该节点已经完成了删除，也就没法查找出来了。

HashNode<K, V>* Find(const K& key) {
	size_t hash0 = key % _table.size();
	size_t i = 0;
	while (_table[(hash0 + i) % _table.size()]._state != EMPTY) {
		if (_table[(hash0 + i) % _table.size()]._kv.first == key
			&& _table[(hash0 + i) % _table.size()]._state == EXIST)
				return &_table[(hash0 + i) % _table.size()];

		++i;
	}

	return nullptr;
}

删除操作

 删除操作就很简单了，我们只需要找出想删的值然后将存储该值的节点状态改为delete即可。为了避免代码冗余，我们可以复用Find函数实现查找功能。

bool Erase(const K& key) {
	HashNode<K, V>* ret = Find(key);
	
	if (!ret)
		return false;
	else
		ret->_state = DELETE;
	
	return true;
}

代码优化

另外，很多时候我们想插入的key不一定是整型，但是哈希表在求余时要求整型才能进行求余，那有没有什么办法可以解决，使得我们的哈希表不仅适合于类型为size_t的整形还适合string乃至其他类型呢。

答案是有的，我们可以采用仿函数。通过仿函数重载（）对不同的类型进行强转操作或者建立多层映射关系，从而实现最终在哈希表内的映射。

对于其他类型如浮点型，我们可以把它强转为size_t型

template <class K>
struct HashFunc
{
	size_t operator()(const K& key) {
		return (size_t)key;
	}
};

对于字符串类型，我们可以建立一层新映射关系，我们可以构造一个较大的数字，让每一个字符串都有其对应的数字，这样就做到了一个字符串映射一个数字，再用这个数字映射到哈希表中，我们的目的就实现了。这里的ans就是我们想要构造的数字，ans*=131是为了可能有多个字符串长度和字母出现次数都一样，但出现的顺序不一样的情况。如abcd和dcba两个字符串长度和出现的字母都一样，但是字母出现的顺序不一样，正常来说这两个字符串的哈希值是不一样的，所以我们可以通过每次对ans乘131（这里的131是我选择的数，你也可以选择一个较大的素数），从而区分出这类字符串，让他们映射不同的数字。

template<>
struct HashFunc<string>
{
	size_t operator()(const string& str){
		size_t ans = 0;
		for (auto& ch : str) {
			ans += ch;
			ans *= 131;
		}
		return ans;
	}
};

 所以完整代码如下：

#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;

//用枚举的方法枚举三种状态
enum State {
	EXIST,
	DELETE,
	EMPTY
};

template <class K>
struct HashFunc
{
	size_t operator()(const K& key) {
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& str){
		size_t ans = 0;
		for (auto& ch : str) {
			ans += ch;
			ans *= 131;
		}
		return ans;
	}
};

template <class K, class V>
struct HashNode {
	pair<K, V> _kv;
	State _state;

	HashNode():_state(EMPTY){}
	HashNode(pair<K, V>& kv): _kv(kv), _state(EMPTY){}
};

template <class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:
	vector<HashNode<K, V>> _table;
	size_t _n;
public:
	HashTable(): _table(__stl_next_prime(0)), _n(0){}

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const size_t __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	bool Insert(const pair<K, V>& kv) {
		if (Find(kv.first))
			return false;

		//负载大于0.7就扩容
		if (_n * 10 / _table.size() >= 7) {
			HashTable<K, V, Hash> newtable;
			newtable._table.resize(__stl_next_prime(_table.size() + 1));
			for (auto& data : _table) {
				if(data._state == EXIST)
					newtable.Insert(data._kv);
			}
			std::swap(_table, newtable._table);
		}

		size_t size = _table.size();
		size_t hash0 = HashFunc<K>()(kv.first) % _table.size();
		size_t i = 0;
		//只要存在就继续往后走
		while (_table[(hash0 + i) % size]._state == EXIST)
		{
			++i;
		}
		size_t hashi =  (hash0 + i) % size;
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		_n++;

		return true;
	}

	HashNode<K, V>* Find(const K& key) {
		size_t hash0 = HashFunc<K>()(key) % _table.size();
		size_t i = 0;
		while (_table[(hash0 + i) % _table.size()]._state != EMPTY) {
			if (_table[(hash0 + i) % _table.size()]._kv.first == key
				&& _table[(hash0 + i) % _table.size()]._state == EXIST)
					return &_table[(hash0 + i) % _table.size()];

			++i;
		}

		return nullptr;
	}

	bool Erase(const K& key) {
		HashNode<K, V>* ret = Find(key);
		
		if (!ret)
			return false;
		else
			ret->_state = DELETE;
		
		return true;
	}
};

测试代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Hash_Linearity.h"

void TestSize_t()
{
	HashTable<size_t, size_t> table;
	size_t a[] = { 19,30,5,36,13,20,21,12 };
	for (auto data : a) {
		table.Insert(pair<size_t, size_t>{ data, data });
	}

	table.Erase(30);

	HashNode<size_t, size_t>* ret = table.Find(30);
	if (ret)
		cout << "找到了，查找的值为:" << ret->_kv.first << endl;
	else
		cout << "没有找到" << endl;

	table.Insert({ 8,8 });
	HashNode<size_t, size_t>* ret2 = table.Find(8);
	if (ret2)
		cout << "找到了，查找的值为:" << ret2->_kv.first << endl;
	else
		cout << "没有找到" << endl;
}

void TestString()
{
	HashTable<string, string, HashFunc<string>> table;
	string str[] = {"apple","baby","cat","dog"};
	for (auto& ch : str) {
		table.Insert(pair<string, string>{ch, ch});
	}
	table.Erase("cat");

	HashNode<string, string>* ret = table.Find("cat");
	if (ret)
		cout << "找到了，查找的值为:" << ret->_kv.first << endl;
	else
		cout << "没有找到" << endl;

	table.Insert({ "happy","happy"});
	HashNode<string, string>* ret2 = table.Find("happy");
	if (ret2)
		cout << "找到了，查找的值为:" << ret2->_kv.first << endl;
	else
		cout << "没有找到" << endl;
}

int main()
{
	//TestSize_t();
	TestString();
	return 0;
}

1.1.2二次探测法

 除了上述的线性探测法，还有没有什么探测方案呢？有的兄弟，有的，这里引入二次探测法。线性探测法在某个位置发生冲突时，很容易会一堆数凑在一起，常常会出现一个哈希表中，一段区间放满了数，一段区间没什么数。为了减少这种情况，二次探测法就应运而生了。

当某个位置发生冲突时，探测的步骤是这样的：

1. 左右跳跃式搜索：从冲突的位置开始，先向右按“1²步、2²步、3²步...”的距离跳跃检查，如果右边没空位，再向左按同样的平方步数反向检查。

2. 循环绕回：如果向右检查到哈希表末尾还没找到空位，就绕回到表头继续找；如果向左检查到表头还没找到，就绕到表尾继续找。

3. 直到找到空位：按这个“左右跳跃+循环绕回”的规则，直到发现一个空闲的位置，把数据存进去。

举个例子：假设当前冲突的位置是5，表长是10：

• 第一次探测从5位置向右跳1²=1步，到位置6；

• 如果还冲突，从5位置向左跳1²=1步，到位置4；

• 如果仍冲突，从5位置向右跳2²=4步，到位置9；

• 再冲突，从5位置向左跳2²=4步，到位置1；

• 依此类推，直到找到能存放的位置。

这种方法通过“平方跳跃”扩大搜索范围，避免像线性探测那样扎堆，同时通过循环绕回覆盖整个哈希表。

则二次探测的公式为：hash0 = key % M

hashi = (hash0 ± i^2) % M,  (i ∈ {1，2，3，……，M/2}  （先往左跳还是先往右跳可自由选择）

下面演示 {19,30,52,63,11,22} 等这⼀组值映射到M=11的表中（这里以先往右跳为例）

 

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0，因此19放在8位置，30放在8的右一格， 52放在8的左一格，11放在0位置，22放在0的右一格。

1.1.3双重散列法

 除了上述提及的两种方法，这里还提供一种更为复杂的方法，双重散列法。

双重散列是什么 双重散列是解决哈希表中哈希冲突的办法。哈希表存数据时，可能不同数据被算到同一个位置，这就是冲突。双重散列的做法是，第一个哈希函数算出的位置有数据了（冲突），就用第二个哈希函数算一个和数据键相关的偏移量，从冲突位置往后一个个找，直到找到空位置存数据。

那么该怎么计算？

1. 第一步：初始位置计算。 用第一个哈希函数 h1(key)算初始哈希值，公式是 h1(key) = hash0 = key % M。这里 key 是数据的键，M 是哈希表大小，hash0 就是数据原本该存的地方。

2.第二步：冲突后处理。要是 hash0 位置已有数据，就用双重探测公式找新位置。公式是 hc(key, i) = hashi = (hash0 + i * h2(key)) % M。i 从 1 开始，一个个增加，按公式算新位置，直到找到空的。

3. 第二个哈希函数怎么取值。第二个哈希函数 `h2(key)` 算出的值要小于 M，而且 h2(key) 和 M 得是互质的（最大公约数是 1）。有两种取值方法： M 是 2 的整数次幂时，在 [0, M - 1] 里随便选个奇数当 h2(key) 的值。 M 是质数时，h2(key) = key % (M - 1) + 1。

为什么要互质 让 h2(key) 和 M 互质？这其实很关键，按固定偏移量找位置，能找到的位置会形成一个集合。如果 M 和 h2(key) 的最大公约数大于 1，能找到的位置个数就会比 M 小，没法用满整个哈希表。 比如，哈希表大小 M = 12，开始找的位置是 1，偏移量是 3，能找到的位置是 {1, 4, 7, 10}，能找的位置个数是 12 / gcd(12, 3) = 4，比 12 小，没把哈希表全用上。

1.2链地址法 

上述提及的三种开放定址法其实在减少冲突方面还是有所不足，这里介绍一种不同于开放地址法的方法，链地址法。链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。如下图所示：

代码实现如下:

 基础结构

template <class K, class V>
struct HashNode {
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	HashNode(const pair<K, V>& kv): _kv(kv), _next(nullptr){}
};

template <class K, class V>
class Hashbucket {
	typedef HashNode<K, V> Node;

private:
	vector<Node*> _table;
	size_t _n;

public:

}；

扩容

 链地址法的扩容跟线性探测法类似，也是尽量扩成一个不靠近2的整数词幂的素数。在这里，我们先在构造时初始化整个哈希表的大小为__stl_next_prime(0)，整个表的元素个数为0。

Hashbucket() : _table(__stl_next_prime(0)), _n(0) {}

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const size_t __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list +
		__stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

插入数据 

 同样的，在插入数据之前我们先检查整个哈希表中是否已经存在kv。这里我们调用Find函数，具体实现在稍后展示。

将旧表数据搬到新表：当表中的元素个数等于整个哈希表的大小时，我们认为需要扩容。对此我们新开一个vector用于存储新的哈希桶。然后我们就需要把原哈希表中的元素一个一个搬到新哈希表中。事实上，我们只需搬运原哈希表中存在的元素即可，并映射到新的哈希表中。对此，我们去遍历每个哈希桶，让cur指向桶头，如果桶不为空，我们就计算出该桶中cur节点的key应该映射到新哈希表中的哪个桶。然后先把cur的next指针存下来（为了待会继续往下遍历整个哈希桶），再让cur的next指向新桶（头插），新桶存储cur的地址。最后再让cur=next（往下走）。

插入操作：先计算出需要插入的key对应表的哪个桶，然后再构造出一个节点用于放入桶中。然后进行头插，让newnode的next指向桶，桶存储newnode的地址，最后让记录元素个数的_n++。

bool Insert(const pair<K, V>& kv) {
	if (Find(kv.first))
		return false;

	//扩容
	if (_n == _table.size()) {
		vector<Node*> newtable(__stl_next_prime(_table.size() + 1));
		for (size_t i = 0; i < _table.size(); i++) {
			Node* cur = _table[i];
			while (cur) {
				size_t newi = cur->_kv.first % newtable.size();
				Node* next = cur->_next;
				cur->_next = newtable[newi];
				newtable[newi] = cur;

				cur = next;
			}
		}
	}
	

	size_t hashi = kv.first % _table.size();
	//头插
	Node* newnode = new Node(kv);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;
	
	return true;
}

 查找数据

 查找逻辑就较为简单了，先找到key应该映射的桶，再遍历这个桶，如果有就返回该节点，否则返回空。

Node* Find(const K& key) {
	size_t hashi = key % _table.size();
	Node* cur = _table[hashi];
	while (cur) {
		if (cur->_kv.first == key)
			return cur;

		cur = cur->_next;
	}

	return nullptr;
}

删除数据 

删除数据的时候为了避免删掉想删的节点导致找不到后面的节点，对此要用到多一个指针prev先记录删掉节点的前一个节点。同样的，先找出key对应的桶，再从该桶开始向下寻找，这里有三种情况：一种是找的节点是桶头，一种是桶的中间，一种是没找到。如果找到了，并且prev为空，说明cur就是第一个节点，那么我们只需让桶存储cur的下一个节点（让cur的下一个节点当头）即可，如果prev不为空，那就让prev的next指向cur的next。最后统一delete掉cur，返回true。如果暂时没找到就继续往下找，若走完整个桶都没找到就返回false。

bool Erase(const K& key)
{
	size_t hashi = key % _table.size();
	Node* prev = nullptr;
	Node* cur = _table[hashi];
	while (cur) {
		if (cur->_kv.first == key) {
			if (prev == nullptr) {
				_table[hashi] = cur->_next;
			}
			else {
				prev->_next = cur->_next;
			}

			delete cur;
			return true;
		}
		else {
			prev = cur;
			cur = cur->_next;
		}
	}

	return false;
}

另外，同样的我们这个哈希表也想设计成适用于存放string乃至其他key类型的数据，所以我们一样引入仿函数。

template <class K>
struct HashFunc {
	size_t operator()(const K& key) {
		return (size_t)key;
	}
};

template<>
struct HashFunc<string> {
	size_t operator()(const string& str) {
		size_t hs = 0;
		for (int i = 0; i < str.size(); i++) {
			hs += str[i];
			hs *= 131;
		}

		return hs;
	}
};

在这样的优化下，就可以实现存放所有类型的数据的哈希表了。总的代码如下：

#pragma once
#include <iostream>
#include <vector>
using namespace std;

template <class K, class V>
struct HashNode {
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	HashNode(const pair<K, V>& kv): _kv(kv), _next(nullptr){}
};

template <class K>
struct HashFunc {
	size_t operator()(const K& key) {
		return (size_t)key;
	}
};

template<>
struct HashFunc<string> {
	size_t operator()(const string& str) {
		size_t hs = 0;
		for (int i = 0; i < str.size(); i++) {
			hs += str[i];
			hs *= 131;
		}

		return hs;
	}
};

template <class K, class V>
class Hashbucket {
	typedef HashNode<K, V> Node;

private:
	vector<Node*> _table;
	size_t _n;

public:
	Hashbucket() : _table(__stl_next_prime(0)), _n(0) {}
	
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const size_t __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	bool Insert(const pair<K, V>& kv) {
		if (Find(kv.first))
			return false;
		
		HashFunc<K> hash;

		//扩容
		if (_n == _table.size()) {
			vector<Node*> newtable(__stl_next_prime(_table.size() + 1));
			//vector<Node*> newtable(_table.size() * 2);
			for (size_t i = 0; i < _table.size(); i++) {
				Node* cur = _table[i];
				while (cur) {
					size_t newi = hash(cur->_kv.first) % newtable.size();
					Node* next = cur->_next;
					cur->_next = newtable[newi];
					newtable[newi] = cur;

					cur = next;
				}
			}
		}
		

		size_t hashi = hash(kv.first) % _table.size();
		//头插
		Node* newnode = new Node(kv);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		++_n;
		
		return true;
	}

	Node* Find(const K& key) {
		HashFunc<K> hash;
		size_t hashi = hash(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur) {
			if (cur->_kv.first == key)
				return cur;

			cur = cur->_next;
		}

		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashFunc<K> hash;
		size_t hashi = hash(key) % _table.size();
		Node* prev = nullptr;
		Node* cur = _table[hashi];
		while (cur) {
			if (cur->_kv.first == key) {
				if (prev == nullptr) {
					_table[hashi] = cur->_next;
				}
				else {
					prev->_next = cur->_next;
				}

				delete cur;
				return true;
			}
			else {
				prev = cur;
				cur = cur->_next;
			}
		}

		return false;
	}
};

测试代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Chain address.h"

void Test1()
{
	Hashbucket<size_t, size_t> bucket;
	int a[] = { 19,30,5,36,13,20,21,12,24,96 };
	for (auto& data : a) {
		bucket.Insert({ data, data });
	}

	HashNode<size_t, size_t>* ret = bucket.Find(30);
	if (ret)
		cout << "找到了，查找的数为：" << ret->_kv.first << endl;
	else
		cout << "没有找到" << endl;

	bucket.Erase(30);
	HashNode<size_t, size_t>* ret1 = bucket.Find(30);
	if (ret1)
		cout << "找到了，查找的数为：" << ret1->_kv.first << endl;
	else
		cout << "没有找到" << endl;
}

void Test2()
{
	Hashbucket<string, string> bucket;
	string str[] = { "apple", "baby", "cat", "dog" };
	for (auto& s : str) {
		bucket.Insert({ s,s });
	}

	HashNode<string, string>* ret = bucket.Find("baby");
	if (ret)
		cout << "找到了，查找的字符串为：" << ret->_kv.first << endl;
	else
		cout << "没有找到" << endl;

	bucket.Erase("baby");
	HashNode<string, string>* ret1 = bucket.Find("baby");
	if (ret1)
		cout << "找到了，查找的字符串为：" << ret1->_kv.first << endl;
	else
		cout << "没有找到" << endl;
}

int main()
{
	//Test1();
	Test2();

	return 0;
}

至此，关于哈希的基本概念和实现就全部讲完了，感谢您的阅读！！！ 同样也赞扬你的学习精神，希望能一直保持下去。最后，点个关注，一键三连呗！！！