C++STL-无序容器-哈希表（散列存储）网站首页 技术交流

C++STL-无序容器-哈希表（散列存储）

Iamasleep 2023-06-05 04:00:02

简介C++STL-无序容器-哈希表（散列存储）

有关于STL中的哈希表一些基础知识

为什么要设计哈希表——查找元素效率高 O(1)，和关联式容器相比，无序容器擅长通过指定键查找对应的值；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。
通过什么机制实现的——关键字通过哈希函数O(1)可以直接确定哈希地址，常见的有直接定址法、除留余数法
会产生什么问题——不同的关键字可能会得到相同的哈希地址，称为哈希碰撞
如何解决哈希碰撞——闭散列找空位置（每次向后找1或i^2），或者开散列在同一个哈希地址的键值对存在同一个哈希桶中，哈希桶可以是单链表或红黑树，哈希地址中存放单链表头结点或红黑树根节点存放在
闭散列和开散列比较——开散列更加实用，一是开散列的负载因子更大（闭散列负载因子不能超过 1，一般建议控制在 0.0 ~ 0.7 之间；开散列负载因子可以超过 1，一般建议控制在 0.0 ~ 1.0 之间），二是开散列在极端情况（所有关键字都得到同一个哈希地址，哈希表退化为单链表O(n)）还可以采取红黑树O(log n) 作为哈希桶

四种数据存储结构：

顺序存储：逻辑上相邻的数据元素其对应的物理存储位置也是相邻的）
链式存储：每个元素一部分存储元素值本身，另一部分用于存放指向下一个元素的指针
索引存储：索引表中的每一项包括关键字和地址，关键字是能够唯一标示一个数据元素的数据项，地址是指示数据元素的存储地址或者存储区域的首地址的
散列存储：将数据元素存储在一个连续的区域，每一个数据元素的具体存储位置是根据该数据的关键字值，通过散列（哈希）函数直接计算出来的

四种无序容器	存储元素	key能否重复	key能否修改
unordered_map	<key,value>	NO	NO
unordered_multimap	<key,value>	YES	NO
unordered_set	<value,value>	NO	NO
unordered_multise	<value,value>	YES	NO

哈希表是牺牲空间换取时间，通过使用额外的数组、set或是map来存放数据，才能实现快速的查找。

哈希函数

要寻找哈希表中的元素，只需要通过哈希函数对该元素关键字进行计算，就可以得出存储地址，也就是说元素的存储位置与它的关键码之间能够建立一种映射的关系

直接定址法

关键字的某个线性函数作为哈希地址
$H a s h (k ey) = a \times k ey + b$

除留余数法

散列表的长度是 $m ， p$ 是0~m中最大的质数
$H a s h (k ey) = k ey (m o d) p$

哈希碰撞

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为 哈希冲突 或 哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素称为同义词。

线性探测

从发生冲突的位置依次向后查找，直到找到一个空位置

二次探测

从发生冲突的位置向后查找，每次往后移动 i^2 个位置，直到找到空位置，也就是每次往后移动的距离都会增大，不容易导致数据堆积

链地址法

首先对关键字集合通过哈希函数计算出哈希地址，将有相同哈希地址的关键字放在同一个子集合，也就是一个哈希桶，在哈希桶内部关键字通过单链表连接，头结点放在哈希表中
在这里插入图片描述

红黑树作为哈希桶（地址全都相同的情况）

所有元素全部产生冲突，最终都放到了同一个单链表中，此时该哈希表增删查改的效率就退化成 O ( N ) ，我们就可以用红黑树来作为哈希桶的数据结构。红黑树搜索时间复杂度是 O(logN)
在这里插入图片描述
但有些地方也会选择不把桶中的单链表结构换成红黑树结构，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大。

具体函数操作

参考：C++ STL unordered_map容器用法详解

容器模板

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型

template < class Key,      //键（key）的类型
           class T,        //值（value）的类型
           class Hash = hash<Key>,  //底层存储键值对时采用的哈希函数
           class Pred = equal_to<Key>,  //判断各个键值对的键相等的规则
           class Alloc = allocator< pair<const Key,T> > // 指定分配器对象的类型
           > class unordered_multimap;

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_set;

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_multiset;

创建容器

调用模板类的默认构造函数，创建空的容器

std::unordered_map<std::string, std::string> umap;

创建的同时初始化

std::unordered_map<std::string, std::string> umap{
    {"Python教程","http://c.biancheng.net/python/"},
    {"Java教程","http://c.biancheng.net/java/"},
    {"Linux教程","http://c.biancheng.net/linux/"} };

调用模板中的拷贝构造函数，将现有容器中存储的键值对，复制给新建的容器

std::unordered_map<std::string, std::string> umap2(umap);

调用移动构造函数，即以右值引用的方式将临时 unordered_map 容器中存储的所有键值对，全部复制给新建容器

//返回临时 unordered_map 容器的函数
std::unordered_map <std::string, std::string > retUmap(){
    std::unordered_map<std::string, std::string>tempUmap{
        {"Python教程","http://c.biancheng.net/python/"},
        {"Java教程","http://c.biancheng.net/java/"},
        {"Linux教程","http://c.biancheng.net/linux/"} };
    return tempUmap;
}
//调用移动构造函数，创建 umap2 容器
std::unordered_map<std::string, std::string> umap2(retUmap());

使用类模板提供的迭代器，在现有容器中选择部分区域内的键值对，为新建的容器初始化

//传入 2 个迭代器，
std::unordered_map<std::string, std::string> umap2(++umap.begin(),umap.end());

at（key)、find（key)、u_map[key]

at(key) 返回 key 对应的 value ，如果 key 不存在，则会抛出 out_of_range 异常。
find(key) 查找以 key 为键的 <key,value>，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器)
value = u_map [ key ]：若key不存在，则会新增
一个键值对

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    //创建并初始化一个 unordered_map 容器，其存储的 <string,string> 类型的键值对
    std::unordered_map<std::string, std::string> u_map{
        {"at_key","value=u_map.at(key)"},
        {"Python教程","http://c.biancheng.net/python/"},
        {"Java教程","http://c.biancheng.net/java/"} };
    //查找指定键对应的值，效率比关联式容器高
    string str = my_uMap.at("at_key");
    cout << "str = " << str << endl;
    //输出为：str = value=u_map.at(key)

    //使用迭代器遍历哈希容器，效率不如关联式容器
    for (auto iter = my_uMap.begin(); iter != my_uMap.end(); ++iter)
    {
        //pair 类型键值对分为 2 部分
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

emplace() 、emplace_hint() 、insert()

C++11新增的emplace() 和 emplace_hint()都比insert效率高
C++ unordered_map insert()用法精讲
 C++ unordered_map emplace()和emplace_hint()方法

count(key)

count(key) 在容器中查找以 key 键的键值对的个数。

bucket(key) 、bucket_count()、bucket_size(n)

bucket(key) 返回以 key 为键的键值对所在桶的编号。
bucket_count() 返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
bucket_size(n) 返回第 n 个桶中存储键值对的数量。

遍历

for (auto& x : umap)  //输出
      cout<<x.first<<" : "<<x.second<<endl;
for ( auto it = mymap.begin(); it != mymap.end(); ++it )
      cout << it->first << " : " << it->second<<endl;

迭代器

unordered_map容器的迭代器p 是一个前向迭代器，则其只能进行 *p、p++、++p 操作

unordered_map<int, int>::iterator iter = hmap.begin(); //申请迭代器，并初始化为哈希表的起始位置
//通过迭代器进行哈希表的遍历
for( ; iter != hmap.end(); iter++){
 cout << "key: " <<  iter->first  << "value: " <<  iter->second <<endl;
}
//获取指向指定键值对的前向迭代器
unordered_map<string, string>::iterator iter = umap.find("Java教程");
cout <<"umap.find("Java教程") = " << "<" << iter->first << ", " << iter->second << ">" << endl;

闭散列实现

参考：数据结构中常见的哈希表，到底是什么？

定义结构

// 哈希表每个空间的状态标记
enum State
{
	EMPTY, // 空
	EXITS, // 存在
	DELETE // 已删除
};

// 每个位置存储的结构
template<class K, class V>
struct HashData
{
	pair<K, V> _kv; // KV结构
	State _state = EMPTY; // 数据的状态（默认设为空）
};

// 哈希表
template<class K, class V>
class HashTable
{
	typedef HashData<K, V> Data;
public:
	// 插入函数
	bool Insert(const pair<K, V>& kv);

	// 查找函数
	Data* Find(const K& key);

	// 删除函数
	bool Erase(const K& key);
private:
	vector<Data> _tables; // vector里面存的是一个结构体数组
	size_t _n = 0; // 存储关键字的个数
};

插入函数insert（）

先判断哈希表中该关键字是否存在
不存在就通过负载因子判断是否需要扩容，若负载因子>0.7，哈希表扩大一倍：
a、创建一个两倍大的新哈希表
b、遍历原哈希表，根据新哈希表的大小重新计算哈希地址，插入元素
c、交换原哈希表与新哈希表
用哈希函数计算出哈希地址
遇到哈希冲突就通过线性探测等方法找到一个空位置，并插入键值对
最后哈希表有效元素个数+1

代码实现

// 插入函数
bool Insert(const pair<K, V>& kv)
{
	// 1.判断哈希表中是否存在相同的键值对
	if (Find(kv.first))
	{
		return false; // 插入失败
	}

	// 2.调整负载因子，如果大于等于0.7，就扩容
	if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
	{
		// 如果是空哈希表，那么初始化为10
		// 如果不是空哈希表，那么就扩大到原来的2倍
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

		// 扩容以后，需要重新映射
		HashTable<K, V, HashFunc> newHT;
		newHT._tables.resize(newSize);

		// 遍历旧表，将原哈希表当中的数据插入到新哈希表中
		for (auto& e : _tables)
		{
			if (e._state == EXITS)
			{
				newHT.Insert(e._kv);
			}
		}

		// 最后再交换新表和旧表中的数据
		newHT._tables.swap(_tables);
	}

	// 3.将键值对插入哈希表
	// a.先取模计算插入的位置
	HashFunc hf; // 用仿函数来判断key的类型
	size_t starti = hf(kv.first); // 拿到第一个数据
	starti %= _tables.size(); // 去模上表的容量（除数不能是capacity）

	size_t hashi = starti;
	size_t i = 1;

	// b.找到一个状态为EMPTY或DELETE的位置
	while (_tables[hashi]._state == EXITS)
	{
		hashi = starti + i; // 线性探测
		//hashi = starti + i * i; // 二次探测
		++i;
		hashi %= _tables.size(); // 防止下标超出哈希表范围
	}

	// c.将数据插入该位置，并将该位置的状态设置为EXIST
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXITS;
	_n++; // 哈希表中的有效元素个数加一

	// 插入成功
	return true;
}

查找函数find（）

以key作为参数寻找哈希表中的元素，如果哈希表中存在该key值则返回该位置上的迭代器，否则返回哈希表最后一个元素下一位置上的迭代器

代码实现

// 查找函数
Data* Find(const K& key)
{
	// 1.如果哈希表大小为0，则查找失败
	if (_tables.size() == 0)
	{
		return nullptr;
	}

	// 2.开始查找
	HashFunc hf; // 用仿函数来判断key的类型
	size_t starti = hf(key);
	starti %= _tables.size();

	size_t hashi = starti;
	size_t i = 1;
	// 直到找到空位置就停下来
	while (_tables[hashi]._state != EMPTY)
	{
		// 如果该位置的状态不是DELETE，并且key值匹配，则查找成功
		if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi]; // 那么直接返回该位置的地址
		}

		hashi = starti + i; //线性探测
		//hashi = starti + i * i; // 二次探测
		++i;
		hashi %= _tables.size(); // 防止下标超出哈希表范围
	}

	// 直到找到空位置时，还没有找到目标元素，说明查找失败
	return nullptr;
}

删除函数erase（）

只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为 DELETE

代码实现

// 删除函数
bool Erase(const K& key)
{
	// 1.查看哈希表中是否存在该键值的键值对
	Data* ret = Find(key);

	if (ret) // 如果存在
	{
		ret->_state = DELETE; // 则将该键值对所在位置的状态改为DELETE即可
		--_n; // 哈希表中的有效元素个数减一
		return true;
	}
	else // 如果不存在
	{
		return false; // 返回false
	}
}

开散列实现

定义结构

在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是链表结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。

// 每个哈希桶中存储数据的结构
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 HashFunc = DefaultHash<K>>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
	// 析构函数
	~HashTable();

	// 插入函数
	bool Insert(const pair<K, V>& kv);

	// 查找函数
	Node* Find(const K& key);

	// 删除函数
	bool Erase(const K& key);
private:
	// 指针数组
	vector<Node*> _tables; // 哈希表
	size_t _n = 0; // 哈希表中的有效元素个数
};

插入函数insert（）

不需要判断负载因子，而是在元素个数刚好等于桶的个数时，给哈希表增容。

通过哈希函数计算出对应的哈希地址。
若产生哈希冲突，则直接将该结点头插到对应单链表即可

代码实现

// 插入函数
bool Insert(const pair<K, V>& kv)
{
	// 1.查看哈希表中是否存在该键值的键值对
	if (Find(kv.first))
	{
		return false; // 如果存在，则插入失败
	}

	// 2.判断是否需要调整哈希表的大小
	if (_tables.size() == _n) // 如果哈希表的大小等于表中的元素个数
	{
		// 如果哈希表大小为 0，则将哈希表的初始大小设置为 10
		// 然后创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍，并初始化为nullptr
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		vector<Node*> newTable;
		newTable.resize(newSize, nullptr);
		
		// 将原哈希表当中每个位置存储的单链表插入到新哈希表
		HashFunc hf; // 用仿函数来判断key的类型
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i]; // 记录原哈希表中第一个哈希桶的节点（记录单链表的头节点）
			while (cur) // 哈希桶不为空，进入循环（头节点不为空，也就是单链表不为空，进入循环）
			{
				Node* next = cur->_next; // 记录cur的下一个结点

				// 通过哈希函数，找到原哈希表中，第一个哈希桶里面的第一个节点，然后通过哈希函数把节点数据转换成整型
				// 接着计算出这个整型的哈希地址，也就是对应的哈希桶编号hashi
				size_t hashi = hf(cur->_kv.first) % newSize;

				cur->_next = newTable[hashi]; // 将该结点头插到新哈希表中编号为hashi的哈希桶中
				newTable[hashi] = cur;

				cur = next; // 取原哈希表中该桶的下一个结点
			}
			// 该桶取完后将该桶置空
			_tables[i] = nullptr;
		}
		// 交换这两个哈希表
		newTable.swap(_tables);
	}

	//3.将键值对插入哈希表
	HashFunc hf; // 用仿函数来判断key的类型
	size_t hashi = hf(kv.first); // 先通过哈希函数把key转为整型
	hashi %= _tables.size(); // 然后计算出对应的哈希桶编号

	// 头插到对应的桶即可
	Node* newnode = new Node(kv); // 新开辟一个待插入结点
	newnode->_next = _tables[hashi]; // 将该结点头插到新哈希表中编号为hashi的哈希桶中
	_tables[hashi] = newnode; // 把哈希桶中第一个节点更新为刚刚插入的节点（更新链表头节点）

	// 4.哈希表中的有效元素个数加一
	++_n;

	return true; // 插入成功
}

查找函数find（）

先判断哈希表的大小是否为 0，若为 0 则查找失败。
然后通过哈希函数计算出对应的哈希地址。
最后通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。

代码实现

// 查找函数
Node* Find(const K& key)
{
	// 1.如果哈希表大小为0，则查找失败
	if (_tables.size() == 0)
	{
		return nullptr;
	}

	// 2.开始查找
	HashFunc hf; // 用仿函数来判断key的类型
	size_t hashi = hf(key); // 先通过哈希函数把key转为整型
	hashi %= _tables.size(); // 然后计算出对应的哈希桶编号
	Node* cur = _tables[hashi]; // 记录哈希桶里面的第一个节点，也就是单链表的头节点

	// 开始遍历整个哈希桶
	while (cur)
	{
		if (cur->_kv.first == key) // 如果key值匹配，则查找成功
		{
			return cur; // 返回节点指针
		}
		cur = cur->_next;
	}
	// 如果把哈希桶全部遍历完还没有找到目标元素，则查找失败
	return nullptr;
}

删除节点erase（）

通过哈希函数计算出对应的哈希桶编号。
遍历对应的哈希桶，寻找待删除结点。
若找到了待删除结点，则将该结点从单链表中移除并释放。
删除结点后，将哈希表中的有效元素个数减一。

代码实现

// 删除函数
bool Erase(const K& key)
{
	// 1.如果哈希表的大小为0，则删除失败
	if (_tables.size() == 0)
	{
		return false;
	}

	// 2.在编号为hashi的哈希桶中寻找待删除结点
	HashFunc hf; // 用仿函数来判断key的类型
	size_t hashi = hf(key); // 先通过哈希函数把key转为整型
	hashi %= _tables.size(); // 然后计算出对应的哈希桶编号
	Node* prev = nullptr; // 定义前驱指针，初始化空
	Node* cur = _tables[hashi]; // 记录哈希桶里面的第一个节点，也就是单链表的头节点

	// 开始遍历整个哈希桶
	while (cur)
	{
		if (cur->_kv.first == key) // 如果key值匹配，说明找到了待删除结点，则删除该结点
		{
			if (prev == nullptr) // 如果待删除结点是哈希桶中的第一个结点
			{
				_tables[hashi] = cur->_next; // 将第一个结点从该哈希桶中移除
			}
			else // 如果待删除结点不是哈希桶的第一个结点
			{
				prev->_next = cur->_next; // 则让cur的前驱节点指向cur的下一个节点
			}

			// 然后释放掉cur 
			delete cur;

			// 删除成功
			return true;
		}

		prev = cur; // 把前驱节点更新为cur

		cur = cur->_next; // cur指向它的下一个节点
	}
	// 如果哈希桶全部遍历完毕还没有找到待删除元素，则删除失败
	return false;
}

析构函数🤡

为什么开散列实现就要有析构函数？
拷贝构造对于 vector 来说是深拷贝，但是对于 vector 里面的链表是浅拷贝，因为链表是我们自己实现的内置类型，所以完成的是浅拷贝。

也就是说，如果我们要对哈希表进行拷贝构造的话，那么两个 vector 就会指向同一个哈希桶，必定会存在析构两次的问题，所以我们这里要对每个哈希桶里的单链表进行析构。

代码实现

// 析构函数
~HashTable()
{
	// 遍历整个哈希表
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		Node* cur = _tables[i]; // 记录哈希表中哈希桶的节点（记录单链表的头节点）
		while (cur) // 遍历哈希桶中的单链表
		{
			Node* next = cur->_next; // 先记录cur的下一个节点
			delete cur; // 释放cur
			cur = next; // 再把next赋值给cur
		}

		// 当哈希桶中的单链表全部被删除时，还要将哈希桶置空
		_tables[i] = nullptr;
	}
}

负载因子α＝填入表中的元素个数／散列表的长度

闭散列的开放定址法，负载因子不能超过 1，一般建议控制在 0.0 ~ 0.7 之间。
开散列的哈希桶，负载因子可以超过 1，一般建议控制在 0.0 ~ 1.0 之间。

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：

哈希桶的负载因子可以更大，空间利用率高。
哈希桶在极端情况下还有可用的解决方案。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
【数据结构与算法】无队头指针的队列置空...

下一篇
【数据结构与算法】八大排序

站长推荐

U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》
分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)

您现在的位置是：首页 >技术交流 >C++STL-无序容器-哈希表（散列存储）网站首页技术交流

C++STL-无序容器-哈希表（散列存储）

文章目录

四种数据存储结构：

哈希函数

直接定址法

除留余数法

哈希碰撞

线性探测

二次探测

链地址法

红黑树作为哈希桶（地址全都相同的情况）

具体函数操作

容器模板

创建容器

at（key)、find（key)、u_map[key]

emplace() 、emplace_hint() 、insert()

count(key)

bucket(key) 、bucket_count()、bucket_size(n)

遍历

迭代器

闭散列实现

定义结构

插入函数insert（）

代码实现

查找函数find（）

代码实现

删除函数erase（）

代码实现

开散列实现

定义结构

插入函数insert（）

代码实现

查找函数find（）

代码实现

删除节点erase（）

代码实现

析构函数🤡

代码实现

负载因子α＝填入表中的元素个数／散列表的长度

上一篇 【数据结构与算法】无队头指针的队列置空...

下一篇 【数据结构与算法】八大排序

站长推荐

上一篇
【数据结构与算法】无队头指针的队列置空...

下一篇
【数据结构与算法】八大排序