你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

＜C++＞哈希及其模拟实现_实现hash函数的程序

作者：你好赵伟 | 2024-07-11 01:32:10

踩

实现hash函数的程序

一、哈希概念

顺序结构以及平衡树中，元素key与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过key的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即，搜索的效率取决于搜索过程中元素的比较次数。

效率最高的搜索方法：不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的key之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

1.哈希思想

哈希（Hash）是一种映射思想，规定存在一个唯一的 哈希值 与键值之前建立映射关系，由这种思想而构成的数据结构称为 哈希表（散列表）

哈希表中的数据查找时间可以做到 O(1)

这是非常高效的，比 AVL树还要快

哈希表中插入数据和查找数据的步骤如下：

插入数据：根据当前待插入的元素的键值，计算出哈希值，并存入相应的位置中
查找数据：根据待查找元素的键值，计算出哈希值，判断对应的位置中存储的值是否与键值相等

假设此时数组的大小 capacity 为 8，哈希函数 计算哈希值：HashI = key % capacity

数据存储如下：

显然，这个哈希表并没有把所有位置都填满，数据分布无序且分散

因此，哈希表 又称为 散列表

2.哈希表

哈希方法中使用的转换函数称为哈希函数（也叫散列函数），来建立映射关系，构造出来的结构称为哈希表 (Hash Table)(也叫散列表)。

如有数据集合{ 5,2,6,8,9,7}，假如哈希函数设置为：

hash(key) = key % capacity

其中capacity为存储元素底层空间总大小

按照这种方法查找不用拿key多次比较，因此查找的速度比较快。

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突。当再插入别的元素时，有可能发生哈希冲突，比如插入22，hashFunc(22) = 22%10 = 2，2的位置已经存了数据2了，那么22该如何存储呢？

引起哈希冲突的原因：哈希函数设计不合理。哈希函数设计原则包括：

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

3.常见的哈希函数

1.直接定址法（常用）

函数原型：HashI = A * key + B

优点：简单、均匀、节省空间，查找key O(1)的时间复杂度
缺点：需要提前知道键值的分布情况
适用场景：范围比较集中，每个数据分配一个唯一位置

例如计数排序，统计字符串中出现的用26个英文字符统计，给数组分配26个空间，遍历到的字符是谁，就把相应的元素值++

2.除留余数法（常用）

假设 哈希表 的大小为 m

函数原型：HashI = key % p (p < m)

把数据映射到有限的空间里面。设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将key转换成哈希地址。如第2节哈希表的例子。

优点：简单易用，性能均衡
缺点：容易出现哈希冲突，需要借助特定方法解决
适用场景：范围不集中，分布分散的数据

3.平方取中法（了解）

函数原型：Hash(Key) = mid(key * key)

适用场景：不知道键值的分布，而位数又不是很大的情况

假设键值为 1234，对其进行平方后得到 1522756，取其中间的三位数 227 作为 哈希值

4.折叠法（了解）

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

适用场景：事先不需要知道键值的分布，且键值位数比较多

假设键值为 85673113，分为三部分 856、731、13，求和：1600，根据表长（假设为 100），哈希值 就是 600

5.随机数法（了解）

选择一个随机函数，取键值的随机函数值为它的 哈希值

函数原型：Hash(key) = rand(key)
其中 rand 为随机数函数

适用场景：键值长度不等时

哈希函数 还有很多很多种，最终目的都是为了计算出重复度低的 哈希值

最常用的是 直接定址法 和 除留余数法

二、哈希冲突

哈希冲突（哈希碰撞） 是面试中的常客，可以通过一个 哈希冲突 间接引出哈希中的其他知识点

1.冲突的原因

哈希值 是键值通过 哈希函数 计算得出的 位置标识符，难以避免重复问题

比如在下面的 哈希表 中，存入元素 20，哈希值 HashI = 20 % 8 = 4，此时 4 位置中并没有元素，可以直接存入

但是如果继续插入元素 36，哈希值 HashI = 36 % 8 = 4，此时 4 位置处已经有元素了，无法继续存入，此时就发生了哈希冲突

不同的 哈希函数 引发 哈希冲突 的概率不同，但最终都会面临 哈希冲突 这个问题，因此需要解决一些方法，解决哈希冲突

2.解决方法

主要的解决方法有两种：闭散列 与 开散列

1.用闭散列解决哈希冲突：

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。下一个位置怎样找呢？有以下两种常见方式：

1.线性探测法介绍

如下场景，要插入22，通过哈希函数hashfunc(22) = 22%10=2计算出的地址为2，2的位置已经有数据2了，现在发生了冲突：规定：当哈希表中存储的数据量与哈希表的容量比值（负载因子）过大时，扩大哈希表的容量，并重新进行映射

线性探测：因为有 负载因子 的存在，所以 哈希表是一定有剩余空间的，当发生 哈希冲突 时，从冲突位置向后探测，直到找到可用位置，直到寻找到下一个空位置为止。

负载因子 = 存储的有效数据个数/空间的大小

负载因子越大，冲突的概率越高，增删查改效率越低

负载因子越小，冲突的概率越低，增删查改的效率越高，但是空间利用率低，浪费多。

负载因子 <1，就能保证发生哈希冲突时一定能找到空位置

2.线性探测的实现

存储数据结构的定义：

闭散列中存储的数据至少包含两个信息：键值对、状态表示

键值对既可以是 K 也可以是 K / V，我们这里实现的是 K / V

（1）状态

区分哈希表的一个位置有没有数据，如果用两种状态表示，在(1)或不在(0)，那么就会带来两个问题：

0表示不在，那么如何存数据0呢？
如果数据发生冲突，当前位置和后面位置都存放的是冲突数据，加入当前位置的数据被删除了，那么查找key时发现当前位置状态为不在，那么就不会再向后查找了。

因此要用3个状态位分别表示空、已存在、已删除，用枚举表示状态位：

空 EMPTY 初始状态
存在 EXIST 插入数据后的状态
删除 DELETE 删除数据后的状态

其实简单分为 [可用 / 不可用] 两种状态也行，细分出 EMPTY 与 DELETE 是为了在进行探测时，提高效率

探测时，如果探测到空，就不必再探测，因为后面必然不存在我们想找的数据，如果存在，这里就不会为空了

所以闭散列中的 存储数据结构 可以用一个结构体定义


	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

（2）定义HashData

哈希数据应包含两个成员：数据和状态


 
    //存储数据结构类
    template<class K, class V>
    struct HashData
    {
	    pair<K, V> _kv;	//键值对
	    Status _status = EMPTY;	//状态
    };

（3）哈希表

哈希表包含两个成员：哈希数据、存储的有效数据的个数，模板有3个参数K、V、HashFunc。

①由于不知道 key 是K还是pair，所以需要定义两个模板参数K、V来包含key是K或pair的两种情况

②由于不知道key的数据类型是int还是string、pair、struct，计算key的映射位置时需要取模，但是只能对int型取模，string、struct、pair无法取模，HashFunc作为仿函数，它的实例可以分别应对这些类型的取模。


    template<class K, class V, class HashFunc>
	class HashTable
	{
    pubilc:
        // ...
    private:
		vector<HashData<K, V>> _table;//哈希表
		size_t _n = 0;//存储有效数据的个数
	};

（4）查找

①无论传给哈希表的数据是K还是pair，查找时，都需要用K做key来进行查找

②计算元素位置

③如果当前位置元素为key，那么就返回该元素，否则可能发生了冲突，继续向后探测


HashData<K, V>* Find(const K& key)
{
	if (_tables.size() == 0)
		return nullptr;
 
	size_t hashi = key % _tables.size();// 取余找位置
 
	// 线性探测
	size_t i = 1;
	size_t index = hashi;
 
	while (_tables[index]._state != EMPTY)
	{
		if (_tables[index]._state == EXIST// 如果不添加这段代码，是删除状态也会被找到，然后返回数据，所以只能是存在状态
			&& _tables[index]._kv.first == key) {
 
			return &_tables[index];//该位置存在且值为key返回地址方便对该数据进行修改
		}
 
		//冲突时，向后查找
		index = hashi + i;//线性探测  //index = start + i*i;//二次探测
		index %= _tables.size();// 取余防止越界
		++i;
 
		// 如果已经查找一圈，那么说明全是存在+删除
		if (index == hashi)
		{
			break;
		}
	}
	return nullptr;
}

（5）插入

①根据键值计算出下标（哈希值）

②线性探测，找到可用的位置 [空 / 删除]

③插入数据，有效数据量+1


bool Insert(const pair<K, V>& kv)
{
	// 存在就不允许插入
	if (Find(kv.first))
		return false;
 
    // 扩容
    // ...
 
	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;
}

如果想降低踩踏发生的概率，可以将 线性探测 改为 二次探测

HashI += (i * i);	//二次探测

以上就是插入操作的具体实现，此时面临着一个棘手的问题：扩容问题

当数据 第一次插入 或 负载因子达到临界值 时，需要进行扩容（因为 vector<Data> _table 一开始为空，所以第一次插入也要扩容）

当空间扩容后，容量发生了改变，这也就意味着数据与下标的映射关系也发生了改变，需要更新数据，即重新进行线性探测

扩容可分为传统写法和现代写法

传统：


bool Insert(const pair<K, V>& kv)
{
	// 存在就不允许插入
	if (Find(kv.first))
		return false;
 
	
	//考虑扩容问题（存储数据超过容量的 70% 就扩容）
	if (_table.size() == 0 || _n * 10 / _table.size() == 7)
	{
		size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
		vector<Data> newTable(newSize);	//创建新表
	
		//将老表中的数据，挪动至新表（需要重新建立映射关系）
		for (auto& e : _table)
		{
			//获取下标（哈希值）
			size_t HashI = e._kv.first % newTable.size();
			int i = 0;	//探测时的权值，方便改为二次探测
	
			//如果为空，进行探测
			while (newTable[HashI]._status == EXIST)
			{
				HashI += i;	//向后移动
				HashI %= newTable.size();
				i++;
			}
	
			//找到空位置了，进行插入
			newTable[HashI]._kv = e._kv;
			newTable[HashI]._status = EXIST;
			_n++;	//插入一个数据
		}
	
		//交换新表、旧表（成本不大）
		_table.swap(newTable);
	}
 
	//插入
	//……
}

传统写法思路：创建一个容量足够的新表，将 原表中的数据映射至新表中，映射完成后，交换新表和原表，目的是为了更新当前哈希表对象中的表。

关于 平衡因子 的控制
根据别人的试验结果，哈希表中的存储的有效数据量超过哈希表容器的 70% 时，推荐进行扩容。

假设容量为 M，存储的有效数据量为 N，两者比率 N / M == 0.7 时进行扩容。
因为我们这里的容量和数据量都是整数，所以在等式两边*10，可得 N * 10 / M == 7

传统写法比较繁琐，下面就来看看 现代写法


		bool Insert(const pair<K, V>& kv)
		{
			// 存在就不允许插入
			if (Find(kv.first))
				return false;
 
			// 负载因子超过0.7就扩容
			//if ((double)_n / (double)_tables.size() >= 0.7)
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				//_tables.reserve(_tables.capacity() * 2);
				// 错误：1、表为空，扩不上去  2、光扩容量无法访问，size没变
 
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//_tables.resize(newsize); 单纯扩容的话会导致原有数据的映射关系发生混乱，所以需另新开辟空间
 
				HashTable<K, V> newHT;
				newHT._tables.resize(newsize);
 
				// 遍历旧表，重新映射到新表
				for (auto& data : _tables)
				{
					if (data._state == EXIST)
						newHT.Insert(data._kv);
				}
				_tables.swap(newHT._tables);
			}
 
            // 插入
            // ...
 
			return true;
		}

其实 传统写法 中的 插入部分逻辑 与 Insert 中的 插入操作 重复了，因此我们可以借助现代思想（白嫖），创建一个 容量足够的哈希表，将 原表 中的数据遍历插入 新的哈希表 中，插入的过程调用 Insert，代码极其间接，并且不容易出错

细节：需不需将当前对象中的有效数据量 _n 进行更新？

答案是不需要，往新的哈希表中插入 _n 个数据，意味着无论是新的哈希表还是当前对象，它们的有效数据量都是一致的，因此不需要更新

（6）删除

删除操作就十分简单了，获取待删除数据，将其中的状态改为 删除 DELETE 即可，不必清空数据，只要访问不到就行了，当然，有效数据量-1


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

像这种线性探测（暴力探测）可以解决哈希冲突问题，但会带来新的问题：踩踏

踩踏：元素的存储位置被别人占用了，于是也只能被迫线性探测，引发连锁反应，插入、查找都会越来越慢

哈希冲突越多，效率越低

优化方案：二次探测，每次向后探测 i ^ 2 步，尽量减少踩踏

尽管如此，闭散列的实际效果不尽人意，因为其本质上就是一个零和游戏，闭散列 实战价值不大，因此只做简单了解即可，真正重点在于 开散列

2.用开散列解决哈希冲突

所谓 开散列 就在原 存储位置 处带上一个 单链表，如果发生 哈希冲突，就将 冲突的值依次挂载即可，因此也叫做 链地址法、开链法、哈希桶。

开散列 中不需要 负载因子，开散列的每个桶中存放的都是哈希冲突的元素，如果每个位置都被存满了，直接扩容就好了，当然扩容后也需要重新建立映射关系

开散列 中进行查找时，需要先根据 哈希值 找到对应位置，并在 单链表 中进行遍历

一般情况下，单链表的长度不会太长的，因为扩容后，整体长度会降低

如果 单链表 真的过长了（几十个节点），我们还可以将其转为 红黑树，此时效率依旧非常高

（1）哈希仿函数

在闭散列中，已经实现了Hash仿函数，用来获取哈希表中的元素的key，方便后续计算映射位置


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

模板特化：string元素使用频率较高，进行模板特化


// 特化string
template<>
struct HashFunc<string>
{
	// BKDR
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& ch : s)
		{
			hash += ch;
			hash *= 31; // 大佬定的值
		}
		return hash;
	}
};

（2）存储节点结构的定义

哈希桶 中需要维护一个 单链表，因此需要一个 _next 指针指向下一个节点


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

因为引入了 单链表，所以 哈希桶 中表的存储类型也变成了 节点指针


template<class K, class V>
class HashTable
{
	typedef HashNode<K, V> Node;
 
	//……
 
private:
		vector<Node*> _tables;// 节点指针数组
		size_t _n = 0;// 存储有效数据个数
};

（3）析构函数

因为有 单链表，所以在对象析构时，需要手动遍历其中的节点，将其释放，避免 内存泄漏


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

为什么 哈希表（闭散列） 中不需要写 析构函数？

因为在闭散列中，表中存储的数据不涉及自定义类型的动态内存管理，并且 vector 在对象调用默认析构时，会被调用其析构，释放其中的内存

（4）查找

先计算key在哈希表中的位置，然后后再该位置的哈希桶中遍历查找：


Node* Find(const K& key)
{
	if (_tables.size() == 0)
			return nullptr;
 
	Hash hash;
	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;
}

（5）插入

在进行数据插入时，既可以尾插，也可以头插，因为桶中的存储顺序没有要求

为了操作简单，我们选择头插

同样的，哈希桶在扩容时，也有传统写法和现代写法，这里采用传统写法


bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first) != nullptr)
		return false;	//冗余
	
    Hash hash;
 
	if (_n == _tables.size())
	{
		size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		vector<Node*> newtables(newsize, nullptr);
		for (auto& cur : _tables)
		{
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = hash(cur->_kv.first) % newtables.size();// 重新计算映射关系
 
				// 头插到新表
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				cur = next;
			}
		}
		_tables.swap(newtables);
 
        //现代写法
	    //size_t newSize = _table.size() == 0 ? 5 : _table.size() * 2;
	    //HashTable<K, V> newHashTable;
	    //newHashTable._table.resize(newSize);	//直接就扩容了
 
	    //for (auto& cur : _table)
	    //{
	    //    while (cur)
	    //    {
	    //	      newHashTable.Insert(cur->_kv);
	    //	      cur = cur->_next;
	    //    }
	    //}
	    //_table.swap(newHashTable._table);
 
 
	size_t hashi = hash(kv.first) % _tables.size();// 取余找位置
 
    // 头插
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
 
	return true;
}

这里的 传统写法 有一个很巧妙的地方：节点回收

既然旧表中节点不用了，那我可以直接把其中的节点 转移链接 至新表中，这样可以提高效率，且代码十分优雅

（6）删除

①计算key在表中的位置

②要删除的数据是不是该位置的第一个哈希桶，如果是，那就让哈希表的第一个节点变成第二个桶，否则让这个桶的前一个桶指向这个桶的下一个桶


bool Erase(const K& key)
{
	Hash hash;
	size_t hashi = hash(key) % _tables.size();// 取余找位置
	Node* prev = nullptr;
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			// 没有前节点
			if (prev == nullptr)
			{
				_tables[hashi] = cur->_next;
			}
			else// 有前节点
			{
				prev->_next = cur->_next;
			}
			delete cur;
 
			return true;
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
	}
	return false;
}

（7）桶的长度

哈希桶 中的长度不会太长，因为存在扩容机制，并且 每次扩容后，映射关系会进行更新，桶的整体高度会降低

可以插入大量数据，查看 哈希桶 的最大高度


class HashTable
{
	//……
	
	size_t MaxBucketSize()
	{
		size_t max = 0;
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			size_t size = 0;
			while (cur)
			{
				++size;
				cur = cur->_next;
			}
	
			if (size > max)
				max = size;
		}
	
		return max;
	}
 
	//……
};
 
void TestOpenHash3()
{
	//插入大量随机数，查看最长的桶长度
	srand((size_t)time(nullptr));
 
	HashTable<int, int> ht;
 
	int n = 1000000;
	for (int i = 0; i < n; i++)
	{
		int val = rand() + i;
		ht.Insert(make_pair(val, val));
	}
 
	cout << ht.MaxBucketSize() << endl;// 2
}

插入约 100w 数据，哈希桶 的最大高度不过为 2

因此，哈希桶可以做到常数级别的查找速度，并且不存在踩踏问题

其实库中的 unordered_set 和 unordered_map 就是使用 哈希桶 封装实现的，就像 红黑树 封装 set 和 map 那样。

三、完整代码

HashTable.h


#pragma once
#include <iostream>
#include <vector>
using namespace std;
 
namespace OpenAdress
{
	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:
		bool Insert(const pair<K, V>& kv)
		{
			// 存在就不允许插入
			if (Find(kv.first))
				return false;
 
			// 负载因子超过0.7就扩容
			//if ((double)_n / (double)_tables.size() >= 0.7)
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				//_tables.reserve(_tables.capacity() * 2);
				// 错误：1、表为空，扩不上去  2、光扩容量无法访问，size没变
 
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//_tables.resize(newsize); 单纯扩容的话会导致原有数据的映射关系发生混乱，所以需另新开辟空间
 
				HashTable<K, V> newHT;
				newHT._tables.resize(newsize);
 
				// 遍历旧表，重新映射到新表
				for (auto& data : _tables)
				{
					if (data._state == EXIST)
						newHT.Insert(data._kv);
				}
				_tables.swap(newHT._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;
		}
 
		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
 
			size_t hashi = key % _tables.size();// 取余找位置
 
			// 线性探测
			size_t i = 1;
			size_t index = hashi;
 
			while (_tables[index]._state != EMPTY)
			{
				if (_tables[index]._state == EXIST// 如果不添加这段代码，是删除状态也会被找到，然后返回数据，所以只能是存在状态
					&& _tables[index]._kv.first == key) {
 
					return &_tables[index];//该位置存在且值为key返回地址方便对该数据进行修改
				}
 
				//冲突时，向后查找
				index = hashi + i;//线性探测  //index = start + i*i;//二次探测
				index %= _tables.size();// 取余防止越界
				++i;
 
				// 如果已经查找一圈，那么说明全是存在+删除
				if (index == hashi)
				{
					break;
				}
			}
			return nullptr;
		}
 
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;// 存储的数据个数
	};
 
	void TestHashTable1()
	{
		int a[] = { 3,33,2,13,5,12,1002 };
		HashTable<int, int> ht;
		for (auto& e : a)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Insert(make_pair(15, 15)); // 扩容
	}
}
 
 
 
namespace HashBucket
{
	template<class K, class V>
	struct HashNode
	{
		HashNode<K, V>* _next;
		pair<K, V> _kv;
 
		HashNode(const pair<K, V>& kv)
			:_next(nullptr)
			,_kv(kv)
		{}
	};
 
	// 仿函数
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
 
	// 特化string
	template<>
	struct HashFunc<string>
	{
		// BKDR
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto& ch : s)
			{
				hash += ch;
				hash *= 31; // 大佬定的值
			}
			return hash;
		}
	};
 
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		~HashTable()
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next; 
					delete cur;
					cur = next;
				}
				cur = nullptr;
			}
		}
 
		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
 
			Hash hash;
			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)
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();// 取余找位置
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 没有前节点
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else// 有前节点
					{
						prev->_next = cur->_next;
					}
					delete cur;
 
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first) != nullptr)
				return false;	//冗余
 
			Hash hash;
 
			if (_n == _tables.size())
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newtables(newsize, nullptr);
				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hash(cur->_kv.first) % newtables.size();// 重新计算映射关系
 
						// 头插到新表
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
				}
				_tables.swap(newtables);
			}
 
			size_t hashi = hash(kv.first) % _tables.size();// 取余找位置
 
			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
 
			return true;
		}
 
		// size_t newsize = GetNextPrime(_tables.size());
		size_t GetNextPrime(size_t prime)
		{
			// SGI
			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
			};
 
			size_t i = 0;
			for (; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > prime)
					return __stl_prime_list[i];
			}
 
			return __stl_prime_list[i];
		}
 
		// 最长桶长度
		size_t MaxBucketSize()
		{
			size_t max = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				auto cur = _tables[i];
				size_t size = 0;
				while (cur)
				{
					++size;
					cur = cur->_next;
				}
				// printf("[%d]->%d\n", i, size);
				if (size > max)
				{
					max = size;
				}
			}
			return max;
		}
 
	private:
		vector<Node*> _tables;// 节点指针数组
		size_t _n = 0;// 存储有效数据个数
	};
 
 
	struct HashStr
	{
		// BKDR
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto& ch : s)
			{
				hash += ch;
				hash *= 31; // 大佬定的值
			}
			return hash;
		}
	};
 
	void TestHashTable2()
	{
		HashTable<string, string> ht; // 走特化
 
		ht.Insert(make_pair("sort", "排序"));
		ht.Insert(make_pair("string", "字符串"));
		ht.Insert(make_pair("left", "左边"));
		ht.Insert(make_pair("right", "右边"));
 
		HashStr hashstr;
		cout << hashstr("abcd") << endl;
		cout << hashstr("bcda") << endl;
		cout << hashstr("aadd") << endl;
		cout << hashstr("eat") << endl;
		cout << hashstr("ate") << endl;
		// 没用BKDR前，虽然顺序不一样，但就单纯的+=字符串的每个字符ascll值，加起来的和是一样的
		// BKDR后，值就不一样了
	}
 
	void TestHashTable4()
	{
		size_t N = 900000;
		HashTable<int, int> ht;
		srand(time(0));
		for (size_t i = 0; i < N; ++i)
		{
			size_t x = rand() + i;
			ht.Insert(make_pair(x, x));
		}
 
		cout << ht.MaxBucketSize() << endl;
	}
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/808345

＜C++＞ 哈希及其模拟实现_实现hash函数的程序

目录

一、哈希概念

1.哈希思想

2.哈希表

3.常见的哈希函数

1.直接定址法（常用）

2.除留余数法（常用）

3.平方取中法（了解）

4.折叠法（了解）

5.随机数法（了解）

二、哈希冲突

1.冲突的原因

2.解决方法

1.用闭散列解决哈希冲突：

1.线性探测法介绍

2.线性探测的实现

（1）状态

（2）定义HashData

（3）哈希表

（4）查找

（5）插入

（6）删除

2.用开散列解决哈希冲突

（1）哈希仿函数

（2）存储节点结构的定义

（3）析构函数

（4）查找

（5）插入

（6）删除

（7）桶的长度

三、完整代码

＜C++＞哈希及其模拟实现_实现hash函数的程序