深度剖析哈希

小灵蛇

发布于 2024-06-06 21:33:53

860

发布于 2024-06-06 21:33:53

文章被收录于专栏：文章部

一. 哈希概念

C++11中引进了unordered系列的四个容器，而之所以这几个容器效率如此之高，是因为运用到了哈希的思想。

1.1 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置没有对应的关系，所以在插入和查找操作时，需要遍历结构，这样造成的时间复杂度太高。

而我们的哈希就是通过某种函数，让元素的关键码与元素的存储位置构建起一一映射关系。这就是哈希的概念。

当向该结构中：

插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

哈希中使用的函数叫做哈希函数，通过哈希构建的结构称为哈希表或者散列表。

特别注意：以上不论是顺序搜索，还是平衡树搜索或者哈希搜索，得到的key值都不能相同。

1.2 哈希冲突

什么是哈希冲突呢？其实啊就是不同的关键码通过相同的哈希函数得到相同的映射位置。

这种就叫哈希冲突或者哈希碰撞。发生哈希冲突并具有相同映射位置的不同的关键码就叫同义词。

1.3 哈希函数

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

我们的哈希函数需要满足：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

我们有下面常见的哈希函数：

1、直接定址法(常用)

直接定址法字面上来说就是通过关键码直接得到映射位置。最多再加一个倍数变换，也就是取关键字的某个线性函数为散列地址。

Hash(Key)= A*Key + B

直接定址法的优点是简单并且消除哈希冲突，但是需要事先知道数据的分布情况，因为直接定址法适用于数据集中且数据小的情况，如下：

2、除留余数法(常用)

如果我们设散列表允许的地址数为m，取一个不大于m，但最接近或者等于m的质数作为除数。

Hash(key)=key%p(p<=m)

简单来说，就是将关键码除以散列表的大小得到的余数作为映射的位置。除留余数法的优点是可以处理分散的数据，缺点是会导致哈希冲突，例如对于{1,4,5,614}。

可以看见是会发生哈希冲突的。

3、平方取中法(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。平方取中法适用于不知道关键字分布，但是数据又不是很大的时候。

4、折叠法(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。

5. 随机数法(了解)

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

random为随机数函数。随机数法适用于关键词长度不等的情况。

6. 数学分析法(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

二. 闭散列

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被填满，说明哈希表中必然还有空位置，那么可以把key存放到冲突位置的下一个空位置中去，为什么说是空位置呢？下面我们会讲解。

2.1 线性探测法

这里我们采用线性探测的方法：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

我们来看看实例，假设我们要将arr映射到Hash表中，而表的大小为10，那么：

int arr[]={4,6,14,25,34}
Hash(i)=arr[i]%10;//表的大小为10

那么就应该如下：

注意：当元素本来该在的位置被占用时，需要往后找下一个空位置。比如：4先进入表，就把4的位置占住了，那么当14再进去的时候，由于下标是4的地方已经被占住了，所以向后找到下标为5的位置，插入。而如果此时再来一个28，那么就插入下标为9的地方，而如果再来了一个29，我们可以看到后面的表已经满了，那么就要从头开始查找插入，结果就应该是：

2.2 引进状态

那么好，我们现在已经知道插入一个元素时，先用他的值对表的大小取模，得到位置，如果该位置为空，那么就插入；如果不为空，就向后找下一个空位置。那么大家有没有考虑过我先删掉一个元素再插入呢？

例如我先删除14，再插入54呢？可以看到有两个问题：

删除之后，我们该将删除之后位置的值变成多少呢？好像多少都不合适，因为无论你变成多少，都有可能会有新插入的元素值跟他一样！
我们插入54之后，按理来说我们应该插入到删除的14的位置，因为实际上来说删除了元素之后，那里就没有元素了，可是我们代码又如何去看该位置是不是空呢？因为第一个问题就是删除之后不知道该把值变为多少。

那么其实我们的解决方法就是，为每个位置引进一个state状态(EXIST,DELETE,NULL)。

2.3 闭散列的查找、插入、删除操作

那么我们就可以进行查找、插入、删除操作了：

查找：现根据哈希函数查找到该元素本来该在的位置，然后再考虑发生过哈希冲突的情况，那我们就要依次向后找不为空的位置，直到找到该元素且状态为存在。
插入：对于插入来说，我们要先根据哈希函数来获取插入元素在哈希表中的位置。如果该位置没有元素则插入，如果该位置有元素发生了哈希冲突，则向后依次找下一个空位置。如果负载因子(哈希表中的元素个数/哈希表的大小)超过给定的大小，则需要对哈希表进行扩容。
删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。先查找到位置，然后将该位置的状态变为DELETE。

代码实现如下：

#pragma once

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

//标识每个存储位置的状态--空、存在与删除
enum State {
	EMPTY,
	EXIST,
	DELETE
};

//定义哈希表中每个位置的结构
template<class K, class V>
struct HashData {
	pair<K, V> _kv;
	State _state = EMPTY;  //默认为空
};

//哈希表
template<class K, class V>
class HashTable {

public:
	HashTable()
		: _n(0)
	{
		//此处将哈希表的大小默认给为10，各位可以自己给定
		_tables.resize(10);
	}

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

		//除留余数法 && 线性探测法
		//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
		size_t hashi = kv.first % _tables.size();
		//不能放在EXIST的位置，DELETE和EMPTY都能放
		while (_tables[hashi]._state == EXIST)
		{
			++hashi;
			hashi%= _tables.size();//防止超过表的大小
		}

		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		++_n;

		return true;
	}

	//将find的返回值定义为Data的地址，可以方便我们进行删除以及修改V
	HashData<K, V>* find(const K& key) 
    {
		Hash hash;  //仿函数对象，后面会细讲
		size_t hashi = hash(key) % _tables.size();
		//记录hashi的起始位置
		size_t starti = hashi;
		//最多找到空
		while (_tables[hashi]._state != EMPTY) {
			//key相等并且state为EXIST才表示找到
			if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
			{
                return &_tables[hashi];
            }
			++hashi;
			hashi %= _tables.size();
		}

		return nullptr;
	}

	bool erase(const K& key) {
		//找不到就不删，找到就把状态置为DELETE即可
		HashData<K, V>* ret = find(key);
		if (ret) {
			ret->_state = DELETE;
			return true;
		}

		return false;
	}

private:
	vector<Data> _tables;
	size_t _n;  //记录表中有效数据的个数
};

2.4 闭散列插入时的扩容

可以看到，我们表的大小是有限的，不可能插入无数个数，所以不可避免的会发生扩容操作。

我们可以回忆一下数组的扩容，我们是直接在原来的数组上直接多开辟空间。那么同样的方法在这里行不行得通呢？

答案是否定的，因为我们这里要符合哈希函数的映射，如果我们扩容后映射条件是会改变的，比如表的大小从10扩容到20，那么同样的17，原来应该是在下标为7的地方，扩容后就应该在下标17的地方，所以扩容前后的映射条件是不同的。

那我们是不是要等到表满了才扩容呢，其实并不是，如果满了再扩容就有点局促了，没有一点的缓冲的地方，所以我们要规定，插入的元素达到表的多少就扩容。我们定义一个载荷因子。

我们这里定义载荷因子为0.7。

所以扩容具体操作如下：

//扩容
if ((double)_n / _tables.size() > 0.7)
{
	//此处不能直接原地扩容，因为映射关系需要改变
	Hashtable<K,V,Hash> newHT;
	newHT._tables.resize(_tables.size() * 2);
	for (auto& e : _tables)
	{
		if(e._state==EXIST)
		{
			//此处不会死循环，因为不会进入需不需要扩容这个判断
			newHT.Insert(e._data);
		}
	}
	_tables.swap(newHT._tables);
}

2.4 仿函数

我们上面考虑的情况都是插入的值为整数的情况，那么如果插入的是字符串呢？

按道理来讲我们要先将字符串转换为整数，再进行插入。那我们能不能把求映射位置的表达式换成这样呢？

size_t hashi = kv.first[0] % _tables.size();

很显然是不能的，这样又只能满足字符串，那么编译器又不知道你要插入什么类型的元素，万一你插入整型，而整型又不能取[]，又会显得鸡肋。

这种问题还得是需要仿函数这位大哥来解决。我们可以为不同的类型定义不同的处理方式：

//int类型
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		return s[0];
	}
};

那么对于字符串这种特殊情况，就有很多人去研究具体该如何定义他的映射函数才是更完美的。那么其中最好的就是BKDR哈希字符串算法，也就是将每一位的字符乘以131或者特定的数字，最后相加。

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

2.5 整体代码

#include<iostream>
#include<vector>
using namespace std;
//int类型
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t len = 0;
		for (auto e : s)
		{
			len += e;
			len *= 131;
		}
		return len;
	}
};

namespace open_address
{
	enum State
	{
		EMPTY,
		DELETE,
		EXIST
	};
	template<class K, class V>
	struct Hashdata
	{
		pair<K, V> _data;
		State _state = EMPTY;
	};

	template<class K, class V,class Hash=HashFunc<K>>
	class Hashtable
	{
	public:
		Hashtable(size_t size = 10)
		{
			_tables.resize(size);
		}
		Hashdata<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._data.first == key
					&& _tables[hashi]._state == EXIST)
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}
		bool Insert(const pair<K,V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
			//扩容
			if ((double)_n / _tables.size() > 0.7)
			{
				//此处不能直接原地扩容，因为映射关系需要改变
				Hashtable<K,V,Hash> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if(e._state==EXIST)
					{
						//此处不会死循环，因为不会进入需不需要扩容这个判断
						newHT.Insert(e._data);
					}
				}
				_tables.swap(newHT._tables);
			}
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				++hashi;
				hashi%= _tables.size();
			}
			_tables[hashi]._data = kv;
			_tables[hashi]._state = EXIST;
			return true;
		}
		bool Erase(const K& key)
		{
			if (!Find(key))
			{
				return false;
			}
			else
			{
				Hashdata<K, V>* ret = Find(key);
				ret->_state = DELETE;
				_n--;
				return true;
			}
		}
	private:
		vector<Hashdata<K,V>> _tables;
		size_t _n = 0;	//实际存储的数据个数
	}; 
}

三. 开散列

开散列法又叫做链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中(我们这里采用头插的方式)。

2.1 闭散列节点定义

闭散列的各个元素之间不会互相影响，所以就不用为每个节点定义状态了。而且每个节点里面都是链表节点。

//int类型
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t len = 0;
		for (auto e : s)
		{
			len += e;
			len *= 131;
		}
		return len;
	}
};
namespace hash_bucket {
	//哈希表的节点结构--单链表
	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 Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<K, V> Node;
        	private:
		vector<Node*> _tables;  //指针数组
		size_t _n;  //表中有效数据的个数
	};
}

2.2 开散列的插入查找删除操作

开散列所用的结构已经与闭散列不相同了，所以对应的操作也应该作出变换。

插入：还是先根据哈希函数算出该插入的位置，用该值创建一个新节点，我们这里采用的是头插的方式插入新节点，因为尾插还要找到尾部，影响了效率。
查找：根据哈希函数算出这个值所在的位置，从头结点开始遍历，一直遍历到某个节点的值等于要查找的值为止。
删除：现根据查找函数找出要删除的节点，如果该节点前面没有节点，则直接删除，然后让哈希表该位置的值为空，如果前面还有值，就先记录前面与后面的节点，删除节点之后，链接这两个节点。

//插入
bool insert(const pair<K, V>& kv) {
    if (find(kv.first))
        return false;

    //调用仿函数的匿名对象来将key转换为整数
    size_t hashi = Hash()(kv.first) % _tables.size();
    //哈希桶头插
    Node* newNode = new Node(kv);
    newNode->next = _tables[hashi];
    _tables[hashi] = newNode;
    ++_n;

    return true;
}

//查找
Node* find(const K& key) {
	size_t hashi = Hash()(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur) {
		if (cur->_kv.first == key)
			{
                return cur;
            }
		cur = cur->next;
	}
	return nullptr;
}

//删除
bool erase(const K& key) {
    //由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
    size_t hashi = Hash()(key) % _tables.size();
    Node* prev = nullptr;
    Node* cur = _tables[hashi];
    while (cur) {
        //删除还要分是否为头结点
        if (cur->_kv.first == key) {
            if (cur == _tables[hashi])
                _tables[hashi] = cur->next;
            else
                prev->next = cur->next;

            delete cur;
            --_n;
            return true;
        }

        //迭代
        prev = cur;
        cur = cur->next;
    }

    return false;
}

2.3 开散列插入时的扩容

与闭散列同样的道理，开散列的插入操作也涉及到扩容操作。因为当我们插入元素时，每个桶中的节点个数会增加，那么极端情况下，可能某个桶下面会挂炒鸡多的节点，这样会影响查找和删除操作的效率。我们就需要进行扩容操作。

我们该什么时候扩容呢？哈希表最好的情况是每个下面都挂一个节点，所以当插入元素个数等于表的大小的时候就进行扩容，此时载荷因子大小为1：

代码如下：

Hash hs;
if (_n == _tables.size())
{
	//不用跟开放地址法一样重新创一个HashTable对象，因为会造成指针节点创建又删除
	vector<Node*> newvector(_tables.size()*2,nullptr);
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur1 = _tables[i];
		while (cur1)
		{
			Node* cur2 = cur1->_next;
			size_t hashi = hs(cur1->_data) % newvector.size();
			cur1->_next = newvector[i];
			newvector[i] = cur1;
			cur1 = cur2;
		}

		//把原来的指针置空
		_tables[i] = nullptr;
	}
	_tables.swap(newvector);
}

此处我们无需再去跟开放地址法一样创建一个HashTable对象，然后再根据所有的值各自创建节点插入到扩容后的新表中，因为这样导致新节点的创建，旧节点的销毁。这样是得不偿失的。

我们采用的是直接取出旧表中的节点插入到新表中(注意：不能将整个桶直接插入到新表，因为同样的值对于新表来说映射结果可能改变了)，然后交换旧表与新表即可，这样节约了大量的时间。

2.4 整体代码

//哈希表的仿函数
template<class K>
struct HashFunc {
	size_t operator()(const K& key) {
		return key;
	}
};

//类模板特化
template<>
struct HashFunc<string> {
	size_t operator()(const string& key) {
		//BKDR字符串哈希算法
		size_t sum = 0;
		for (auto ch : key)
			sum = sum * 131 + ch;

		return sum;
	}
};

//开散列
namespace hash_bucket {
	//哈希表的节点结构--单链表
	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 Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<K, V> Node;

	public:
		//构造
		HashTable()
			: _n(0)
		{
			_tables.resize(10, nullptr);
		}

		//析构--手动释放哈希表中的每个元素，以及每个元素指向的哈希桶
		~HashTable() {
			//释放每个元素的哈希桶
			for (size_t i = 0; i < _tables.size(); ++i) {
				Node* cur = _tables[i];
				while (cur) {
					Node* next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}

		//插入
		bool insert(const pair<K, V>& kv) {
			if (find(kv.first))
				return false;
            
            Hash hs;
			//扩容--当载荷因子达到1时我们进行扩容
			if (_n == _tables.size()) {
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); ++i) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->next;
						//重新计算映射关系--调用仿函数的匿名对象来将key转换为整数
						size_t hashi = hs(cur->_kv.first) % newTables.size();
						cur->next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}
				}

				_tables.swap(newTables);
				newTables.clear();  //不写也可以，局部的vector变量出作用域自动调用析构
			}

			//调用仿函数的匿名对象来将key转换为整数
			size_t hashi = Hash()(kv.first) % _tables.size();
			//哈希桶头插
			Node* newNode = new Node(kv);
			newNode->next = _tables[hashi];
			_tables[hashi] = newNode;
			++_n;

			return true;
		}

		//查找
		Node* find(const K& key) {
            Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur) {
				if (cur->_kv.first == key)
					return cur;
				cur = cur->next;
			}

			return nullptr;
		}

		//删除
		bool erase(const K& key) {
            Hash hs;
			//由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur) {
				//删除还要分是否为头结点
				if (cur->_kv.first == key) {
					if (cur == _tables[hashi])
						_tables[hashi] = cur->next;
					else
						prev->next = cur->next;

					delete cur;
					--_n;
					return true;
				}

				//迭代
				prev = cur;
				cur = cur->next;
			}

			return false;
		}

	private:
		vector<Node*> _tables;  //指针数组
		size_t _n;  //表中有效数据的个数
	};
}

四. 素数做除数和哈希表结构问题

我们上面在介绍除留余数法时给出的定义是这样的：设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照哈希函数 Hash(key) = key % p (p<=m), 将关键码转换成哈希地址；

这里为什么要选择素数来作为除数呢？因为这样能减少哈希冲突发生的概率。

所以我们C++中就有人专门去研究了哪些素数最合适作为除数。那么STL源码如下：

// Note: assumes long is at least 32 bits.
static const int __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
};

inline unsigned long __stl_next_prime(unsigned long n)
{
  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;
}

这里还有一个问题，我们设定的是当载荷因子达到1的时候就进行扩容，这样保证哈希表中的每个位置下面挂着三五个节点，保证了效率。

但是极端情况下，例如经历某些特殊攻击的时候(专门插入位于同一种哈希碰撞情况的素数)，那么机会导致某个链表很长，这里我们就要对链表这个数据机构做出变换，可以把它换成红黑树，红黑树可以保证查找、插入和删除操作的时间复杂度都是 O(log n)，比链表快得多。

所以在极端情况下，可以用红黑树来作为存储结构，而普通情况下就采用链表来存储就可以了。

总结

好了，到这里今天的知识就讲完了，大家有错误一点要在评论指出，我怕我一人搁这瞎bb，没人告诉我错误就寄了。

祝大家越来越好，不用关注我（疯狂暗示）

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-06，如有侵权请联系 cloudcommunity@tencent.com 删除

size