【C++】“最强查找“哈希表的底层实现

哈希表的查找的时间复杂度是O（1）~

文章目录

• 前言
• 一、哈希冲突和哈希函数
• 二、哈希表底层实现
  • 1.开放地址法
  • 2.链地址法
• 总结

前言

哈希概念：

顺序结构以及平衡树
中，元素关键码与其存储位置之间没有对应的关系，因此在
查找一个元素

时，必须要经过关键码的多次比较
。
顺序查找时间复杂度为
O(N)
，平衡树中为树的高度，即

O(logN)
，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以
不经过任何比较，一次直接从表中得到要搜索的元素
。

如果构造一种存储结构，通过某种函数
(hashFunc)
使元素的存储位置与它的关键码之间能够建立

一一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中：

插入元素:根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素:对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希
(
散列
)
方法，
哈希方法中使用的转换函数称为哈希
(
散列
)
函数，构造出来的结构称

为哈希表
(Hash Table)(
或者称散列表)

例如：
数据集合
{1
，
7
，
6
，
4
，
5
，
9}
；

哈希函数设置为：
hash(key) = key % capacity
; capacity
为存储元素底层空间总的大小。

 用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 。 

一、哈希冲突和哈希函数

哈希冲突：

对于我们上面所插入的数，如果我们插入了44会发生什么呢？44%10==4，但是4这个位置已经被占了，这就是哈希冲突。

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突
或哈希碰撞
。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

哈希函数：

引起哈希冲突的一个原因可能是：
哈希函数设计不够合理
。

哈希函数设计原则
：

1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有
m
个地址时，其值域必须在0
到
m-1
之间。

2.哈希函数计算出来的地址能均匀分布在整个空间中。

3.哈希函数应该比较简单。

常见哈希函数：

1.
直接定址法
–(
常用
)

取关键字的某个线性函数为散列地址：
Hash
（
Key
）
= A*Key + B

优点：简单、均匀。

缺点：需要事先知道关键字的分布情况。

使用场景：适合查找比较小且连续的情况。

2.除留余数法
–(
常用
)

设散列表中允许的
地址数为
m
，取一个不大于
m
，但最接近或者等于
m
的质数
p
作为除数，
按照哈希函数：
Hash(key) = key% p(p<=m),
将关键码转换成哈希地址。

3.
平方取中法
–(
了解
)

假设关键字为
1234
，对它平方就是
1522756
，抽取中间的
3
位
227
作为哈希地址；

再比如关键字为
4321
，对它平方就是
18671041
，抽取中间的
3
位
671(
或
710)
作为哈希地址

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4.
折叠法
–(
了解
)

折叠法是将关键字从左到右分割成位数相等的几部分
(
最后一部分位数可以短些
)
，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。

5.
随机数法
–(
了解
)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key) = random(key),
其中

random
为随机数函数。

通常应用于关键字长度不等时采用此法.

6.数学分析法
–(
了解
)

设有
n
个
d
位数，每一位可能有
r
种不同的符号，这
r
种不同的符号在各位上出现的频率不一定

相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只

有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散

列地址。例如：

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前
7
位都是相同

的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还

可以对抽取出来的数字进行反转
(
如
1234
改成
4321)
、右环位移
(
如
1234
改成
4123)
、左环移

位、前两数与后两数叠加
(
如
1234
改成
12+34=46)
等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

哈希冲突的解决：

解决哈希冲突
两种常见的方法是：
闭散列
和
开散列。

1.闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有

空位置，那么可以把
key
存放到冲突位置中的
“
下一个
”
空位置中去。
那如何寻找下一个空位置

呢？

1.
线性探测
：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
。

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素

会影响其他元素的搜索
。比如删除元素
4
，如果直接删除掉，
44
查找起来可能会受影

响。因此
线性探测采用标记的伪删除法来删除一个元素
。

线性探测优点：实现非常简单。

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？用二次探测的方法：

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位

置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，
找下一个空位置的方法

为：hashi = hashi + i*i
 
或者：hashi = hashi + i的n次方 
其中：
i =

1,2,3…

对于
2.1
中如果要插入
44
，产生冲突，使用解决后的情况为：

研究表明：
当表的长度为质数且表装载因子
a
不超过
0.5
时，新的表项一定能够插入，而且任

何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在

搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子
a
不超过
0.5
，
如果超出

必须考虑增容。

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

2.开散列

1.
开散列概念

开散列法又叫链地址法
(
开链法
)
，首先对关键码集合用散列函数计算散列地址，具有相同地

址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链

接起来，各链表的头结点存储在哈希表中
。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列与闭散列比较：

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销
。事实上：

由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子
a <=

0.7
，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

二、哈希表底层实现

1.开放地址法

 首先我们将代码放到一个命名空间内防止后面发生命名冲突，然后用一个结构体保存每个位置存储什么样的数据，这里我们就以kv结构为例：

enum State
	{
		EMPTY,
		DELETE,
		EXIST
	};
	template 
	struct HashDate
	{
		pair _kv;
		State _state = EMPTY;
	};

我们定义的枚举类型有代表空，删除，存在3种状态，至于为什么要用状态表示而不是直接将哈希表中的数据删除想必大家是有答案的，因为我们的开放地址法解决冲突的时候，如果此位置已经有数就需要往后查找，如果我们将这个位置删除那么还怎么查找后面的数呢。我们在初始化HashDate的时候要将刚开始的每个位置置为EMPTY状态，因为我们后面都是根据状态来插入删除的。

template 
	class HashTable
	{
	public:

    private:
		vector<HashDate> _tables;
		size_t _n = 0;   //记录插入了多少个元素

	};

哈希表的主体我们就直接用vector了，因为vector的功能很完全如果我们自己实现会比较麻烦。每个向量中存放HashDate类型的数据（记得加模板参数），然后我们用一个变量来记录向表中插入了多少数据，这里可不能直接用向量的size()，因为我们是会有删除状态，如果用size()删除状态也会被记录。

bool insert(const pair& kv)
		{
			size_t hashi = kv.first % _tables.size();
			size_t i = 1;
			size_t index = hashi;
			while (_tables[index]._state == EXIST)
			{
				index = hashi + i;
				index %= _tables.size();
				++i;
			}
			_tables[index]._kv = kv;
			_tables[index]._state = EXIST;
			++_n;
			return true;
		}

上面是哈希表插入的代码，我们先不考虑扩容的问题，在这里我们计算插入元素映射的位置一定不能%capacity(),我们画个图为例：

 我们要使用vector一定会使用到[]操作符的，但是这个操作符只能访问size()的值，超出size()就会触发报错，比如一个数组size() = 10,capacity() = 20,我们可以访问【5】但是不能访问【15】，所以我们计算映射的位置一定是%size().然后我们要判断映射的位置是否已经有元素了，如果有元素了就需要向后探测找空位置，我们用index的目的是以后改二次探测会非常简单，在向后寻找的过程中为了防止index越界所以每次都%哈希表的实际容量，找到位置后将键值对插入并且把状态改为存在，然后让计数器加加即可。下面我们考虑扩容的问题，扩容之前我们需要知道一个概念：

bool insert(const pair& kv)
		{
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				//扩容
				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				HashTable newtable;
				newtable._tables.resize(newsize);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newtable.insert(e._kv);
					}
				}
				_tables.swap(newtable._tables);
			}
			size_t hashi = kv.first % _tables.size();
			size_t i = 1;
			size_t index = hashi;
			while (_tables[index]._state == EXIST)
			{
				index = hashi + i;
				index %= _tables.size();
				++i;
			}
			_tables[index]._kv = kv;
			_tables[index]._state = EXIST;
			++_n;
			return true;
		}

也就是说我们要看载荷因子是多少，载荷因子是表中实际插入的数除表的实际大小（要记住实际大小是size()）,但是由于计算机中两个整形怎么除都不会变成小数，所以两边乘10就解决了这个问题，当然也可以强转为double去除。为了防止除0问题所以我们判断哈希表是否为0或者载荷因子是否大于0.7.新空间每次按原来空间的两倍扩容，这里大家思考一下可以直接在原来的数组扩容吗？答案是不行的，因为原来映射的位置经过扩容会发生改变，比如原先size()为10，11这个数会放在1这个位置，但是扩容到size()=20后，11这个数因为放在11的位置才对。为了防止这个问题我们直接重新创建一个哈希表对象，给这个哈希表对象中的表扩容为新空间大小，要注意的是：只有resize()才会改变size()的大小，reserve只会改变capacity，我们实际用的size()所以必须要让size()改变。开好空间后我们遍历旧表的数据看每个位置是否有存在的元素，有的话就插入到新表（这里调用inser是不会扩容的，因为是新表调用的，新表的空间是开好的，只会重新映射位置进行插入），插入结束后直接让原来的向量和新表中的向量交换即可。

HashDate* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			size_t hashi = key % _tables.size();
			size_t index = hashi;
			size_t i = 1;
			while (_tables[index]._state != EMPTY)
			{
				if (_tables[index]._state == EXIST
					&& _tables[index]._kv.first == key)
				{
					return &_tables[index];
				}
				index = hashi + i;
				index %= _tables.size();
				if (index == hashi)
				{
					break;
				}
				++i;
			}
			return nullptr;
		}

Find接口实现起来就比较简单了，当表为空我们就返回空即可。然后计算映射的位置直接去这个位置查找元素是否存在，要注意我们查找的时候只要这个位置不为空我们就进行查找，因为这个位置有可能是删除状态，删除状态的话需要向这个位置后面去寻找，所以条件是不为空，进入循环后我们要判断当前元素是否和我们查找的元素的key相等并且这个位置还必须是存在状态，只有满足这个条件我们才返回该位置的数据（这里我们用的引用，而返回值是指针类型，但是我们在将引用的时候说过，引用就是指针实现的，所以这里返回值没有问题），当我们查找一圈又回到一开始的映射位置的时候，这个时候肯定找不到了直接退出循环即可。

bool eraser(const K& key)
		{
			HashDate* tmp = Find(key);
			if (tmp)
			{
				tmp->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}

删除接口我们直接用Find函数去查找，如果找到了就将当前位置的状态置为删除，然后将计数器减减返回true。我们在insert的时候也可以用Find判断一下，如果要插入的值已经存在了我们就不插入了。

 以上就是开放地址法的三个重要接口下面我们测试一下：

void TeshHashTable1()
	{
		int a[] = { 3,33,2,13,5,12,102 };
		HashTable ht;
		for (auto& e : a)
		{
			ht.insert(make_pair(e, e));
		}
		ht.insert(make_pair(16, 16));
		auto t = ht.Find(13);
		if (t)
		{
			cout << "13在" << endl;
		}
		else
		{
			cout << "13不在" << endl;
		}
		ht.eraser(13);
		t = ht.Find(13);
		if (t)
		{
			cout << "13在" << endl;
		}
		else
		{
			cout << "13不在" << endl;
		}
	}

 没问题，我们再看看扩容时是否成功映射：

 运行结果没毛病，下面我们实现链地址法。

2.链地址法（哈希桶）

 同样我们将代码放到命名空间中，然后我们要用struct实现节点，这个节点将来会挂在哈希表的某个位置。

template 
	struct HashNode
	{
		HashNode* _next;
		pair _kv;
		HashNode(const pair& kv)
			:_kv(kv)
			, _next(nullptr)
		{

		}
	};

节点中只需要有个next指针指向其他节点，然后一个键值对就搞定了，由于是节点我们肯定是需要通过开空间new出来的，所以我们就写个构造函数，通过pair来构造这个节点即可。

template 
	class HashTable
	{
		typedef HashNode Node;
	public:

    private:
		vector _tables;
		size_t _n = 0;
	};

主体同样用vector，里面存放节点的指针即可，同样还需要有一个计数器记录插入了多少元素。

bool insert(const pair& kv)
		{
			size_t hashi = kv.first % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

同样我们先不考虑扩容的问题，直接算出映射的位置，然后创建新节点，然后头插就可以了，让新节点的next链接原先表中的头结点，然后再让新节点变成映射位置的头结点这样就完成了头插，头插后让计数器++即可，下面来考虑扩容的问题：

bool insert(const pair& kv)
		{
			if (_n == _tables.size())
			{
				//扩容
				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				vector newtable(newsize, nullptr);
				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = cur->_kv.first % newtable.size();
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						cur = next;
					}
				}
				_tables.swap(newtable);
			}
			size_t hashi = kv.first % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

哈希桶的扩容只需要当每个桶都有元素了再扩容就好了，这样就能保证每个桶中的数据都是差不多的。当插入的元素除以实际元素也就是载荷因子为1时扩容，对于哈希桶的扩容我们也可以像上面开放地址法那样开一个新的哈希表，但是这样效率太低了，要知道哈希桶中链接的节点重新插入然后插入成功后还要一个个释放空间这样效率太低了，所以我们直接重新开一个vector，然后直接将旧的哈希表中的节点一个个重新映射到vector中，这样当映射完成后我们就不用释放节点的空间了，因为我们使用旧的节点重新映射的，没有新开节点。重新映射也很简单，就是遍历旧的哈希表，当此位置节点不为空时，我们就保存这个节点的下一个节点，然后计算这个节点的新的映射位置（这里计算一定是用新的size()空间去映射，这样才叫重新映射），然后让当前节点链接映射位置的头结点，然后再让当前节点变成映射位置的头结点就完成了头插。插入完成后交换vector即可。

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

查找函数同样先看表是否为空，如果为空返回空指针即可。然后我们计算映射位置直接拿到这个位置的头结点，然后从头结点开始去遍历，如果找到要查找的元素就返回当前节点，如果到循环结束还没有找到就返回空指针即可。

bool eraser(const K& key)
		{
			size_t hashi = key % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						Node* next = cur->_next;
						_tables[hashi] = next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

删除接口首先计算要映射的位置，然后拿到这个位置的头结点，用一个变量去保存前一个节点，当头结点不为空就进入循环，如果没有找到要删除的节点我们就继续遍历，遍历前把当前位置给prev节点去记录前面的位置，当找到要删除节点的时候我们需要判断当前节点是否是头结点，如果是头结点那么直接让头结点的next当头结点，把原先的头结点释放即可。如果要删除的不是头结点，就让前面节点的next链接要删除节点的next即可，然后释放节点即可。

下面我们测试一下代码：

void TeshHashTable2()
	{
		int a[] = { 3,33,2,13,5,12,1002 };
		HashTable ht;
		for (auto& e : a)
		{
			ht.insert(make_pair(e, e));
		}
		ht.insert(make_pair(16, 16));
		ht.insert(make_pair(14, 14));
		ht.insert(make_pair(15, 15));
		ht.insert(make_pair(17, 17));
		auto t = ht.Find(13);
		if (t)
		{
			cout << "13在" << endl;
		}
		else
		{
			cout << "13不在" << endl;
		}
		ht.eraser(13);
		t = ht.Find(13);
		if (t)
		{
			cout << "13在" << endl;
		}
		else
		{
			cout << "13不在" << endl;
		}
	}

 接口没有问题，下面我们看看扩容的问题：

 上面是没扩容时候的哈希表，下面我们再看看扩容后的样子：

 我们可以看到扩容后所有的值都经过重新映射了，下面我们实现一下析构函数，因为当我们程序结束后vector只会是否释放自己的空间，对于每个位置链表的空间是不会释放的，所有需要我们手动释放：

~HashTable()
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				cur = nullptr;
			}
		}

 析构的时候我们直接遍历，当这个位置的头结点不为空时我们就保存这个位置的下一个节点，然后将当前节点释放掉再让cur变成刚刚保存的节点重新执行delete操作。当一个桶的数据全部释放后我们就将当前桶的指针置为空即可。

总结

以上就是哈希表的底层实现了，下一篇文章我会将哈希桶进行封装然后变成unordered_map和unordered_set的底层，前面我们也进行了红黑树的封装，这次的封装还红黑树相差不大只不过会比红黑树麻烦一点。