【C++练级之路】【Lv.18】哈希表（哈希映射，光速查找的魔法）

2024-04-08 1394阅读


【C++练级之路】【Lv.18】哈希表（哈希映射，光速查找的魔法）


快乐的流畅：个人主页


个人专栏：《算法神殿》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！

文章目录

  • 引言
  • 一、哈希
    • 1.1 哈希概念
    • 1.2 哈希函数
    • 1.3 哈希冲突
    • 二、闭散列
      • 2.1 数据类型
      • 2.2 成员变量
      • 2.3 默认成员函数
        • 2.3.1 constructor
        • 2.4 查找
        • 2.5 插入
        • 2.6 删除
        • 三、开散列
          • 3.1 结点
          • 3.2 成员变量
          • 3.3 默认成员函数
            • 3.3.1 constructor
            • 3.3.2 destructor
            • 3.4 查找
            • 3.5 插入
            • 3.6 删除
            • 3.7 哈希化
            • 总结

              引言

              之前学习的红黑树，增删查改都为O(logN)，但是今天学习的哈希表，理论上可以达到增删查改都为O(1)，让我们来看看是什么结构这么神奇吧~

              一、哈希

              1.1 哈希概念

              在线性结构和树形结构中，元素键值key与其存储位置之间没有对应关系，因此在查找指定元素时，要经过key的多次对比。

              时间复杂度：顺序查找为O(N)，二叉搜索平衡树查找为O(logN)。

              理想的查找方式：不经过任何比较，直接通过key获取其存储位置。

              这就是哈希的本质，通过某种函数（称之为哈希函数）构建key与其存储位置的一一映射关系，从而达到查找为O(1)。而这种结构也称为哈希表（Hash Table），又称散列表。

              1.2 哈希函数

              哈希函数设计原则：

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

                那么，下面介绍两种常见的哈希函数：

                1. 直接定址法
                  • Hash(key) = A*key + B

                优点：简单、均匀

                缺点：需要事先知道key的分布情况

                1. 除留余数法
                  • Hash(key) = key % p (p EMPTY, EXIST, DELETE }; template pair public: protected: vector _tables.resize(10); } size_t hashi = key % _tables.size(); size_t pos = hashi; size_t i = 1; while (_tables[pos]._state != EMPTY) { if (_tables[pos]._state == EXIST && _tables[pos]._kv.first == key) { return &_tables[pos]; } pos = hashi + i; if (pos = _tables.size()) { return nullptr; } ++i; } return nullptr; }

                    细节：

                    1. 先用key取模数组size，得到哈希地址hashi
                    2. 然后沿当前位置向后找，直到该位置状态为空或超出数组边界，才算找不到
                    3. 如果该位置状态为存在且key相等，则找到了

                    2.5 插入

                    bool Insert(const pair& kv)
{
	if (Find(kv.first))//保持key唯一
	{
		return false;
	}
	//...
	size_t hashi = kv.first % _tables.size();
	size_t pos = hashi;
	size_t i = 1;
	while (_tables[pos]._state == EXIST)
	{
		pos = hashi + i;//线性探测
		if (pos >= _tables.size())
		{
			return false;
		}
		++i;
	}
	_tables[pos]._kv = kv;
	_tables[pos]._state = EXIST;
	++_n;
	return true;
}

                    细节：

                    1. 先查找当前是否存在该值，如果存在，则不插入
                    2. 用key取模数组size，得到哈希地址hashi
                    3. 然后沿当前位置向后找，直到状态为空或删除，才插入

                    但是，上述情况是哈希表未满时，如果满了如何扩容？还有，一定要满了才扩容吗？

                    这里，我们引入负载因子的概念：α = 有效数据个数 / 哈希表长度

                    当负载因子越大，哈希冲突的概率就越大，同时发生哈希踩踏的概率也越大，对于开放定址法，应该控制负载因子小于0.7，超过将扩容。

                    if (_n * 10 / _tables.size() >= 7)//负载因子大于等于0.7， 扩容
{
	size_t newsize = _tables.size() * 2;
	vector newtables(newsize);
	for (auto& cur : _tables)
	{
		size_t hashi = cur._kv.first % newsize;
		size_t pos = hashi;
		size_t i = 1;
		while (newtables[pos]._state == EXIST)
		{
			pos = hashi + i;//线性探测
			++i;
		}
		newtables[pos]._kv = kv;
	 _tables[pos]._state = EXIST;
	}
	_tables.swap(newtables);
}

                    细节：

                    1. 判断时左右同乘以10，避免比较浮点数而带来误差
                    2. newsize为原本的2倍（本来应该是接近2倍的素数，这里简单起见没实现）
                    3. 将原哈希表中的元素一一映射到新表中
                    4. 最后交换旧表和新表（类似于拷贝构造的现代写法）

                    2.6 删除

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

                    细节：

                    1. 先查找当前是否存在该值，如果存在，则删除
                    2. 这里的删除，只用将状态变量改为删除即可

                    以上讲解的查找和插入，它们所用的探测方法是线性探测（一个一个往后找），这种探测方法可能会造成大量的哈希冲突。

                    那么，有没有什么探测方法能缓解哈希冲突呢？有，那就是二次探测！

                    改法也很简单，以一小段代码举例：

                    while (newtables[pos]._state == EXIST)
{
	pos = hashi + i*i;//二次探测
	++i;
}

                    这样就是每次跨越 i 的二次方向后探测，中间间隔大，哈希冲突就可以得到缓解。

                    三、开散列

                    但是，闭散列（开放定址法）有一个致命的缺陷，那就是空间利用率低！它必须保留相当一部分的开放空间，才能不断插入。

                    所以，实际上，我们更常用另一种方式来实现哈希表——闭散列，又称为开链法。

                    在开链法中，哈希表的每个槽位（bucket），又称为哈希桶，通过一个单链表来存储所有散列到该槽位的元素。这意味着即使不同的key经过哈希函数映射到同一个槽位，它们也可以被存储在同一个单链表上，从而避免了冲突。

                    【C++练级之路】【Lv.18】哈希表（哈希映射，光速查找的魔法）

                    3.1 结点

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

                    细节：

                    • 这里没有使用STL的list或者forward_list，而是自己设计结点，为了更方便操纵内部细节

                      3.2 成员变量

                      template
class HashTable
{
protected:
	typedef HashNode Node;
public:
protected:
	vector _tables;
	size_t _n = 0;//有效数据个数
};

                      细节：

                      1. 数组（vector）中存储单链表的头结点指针
                      2. 模板参数的Hash，是为了任意类型都能转换为整型来取模

                      3.3 默认成员函数

                      3.3.1 constructor

                      HashTable()
{
	_tables.resize(10);
}

                      细节：这里vector提前开空间，可以避免后续为空的讨论

                      3.3.2 destructor

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

                      细节：因为涉及链表结点空间的动态开辟，所以要手动释放

                      3.4 查找

                      Node* Find(const K& key)
{
	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;
}

                      细节：

                      1. 先取模计算出哈希地址
                      2. 再沿当前单链表向下查找

                      3.5 插入

                      bool Insert(const pair& kv)
{
	if (Find(kv.first))//保持key唯一
	{
		return false;
	}
	Hash hash;
	//...
	size_t hashi = hash(kv.first) % _tables.size();
	Node* newnode = new Node(kv);
	//头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

                      细节：

                      1. 先查找当前是否存在该值，如果存在，则不插入
                      2. 取模计算出哈希地址，再头插新节点

                      运用开链法后，虽然没有哈希冲突了，但是链表长度过长也会影响效率。所以，哈希表也需要通过扩容来使链表长度变短，理想的状态是负载因子为1时扩容。

                      悄悄说一句：链表过长，还有另一种解决方法，那就是在该哈希桶下改挂一棵红黑树~

                      if (_n == _tables.size())//负载因子为1时，扩容
	{
		size_t newsize = _tables.size() * 2;
		vector newtables(newsize);
		for (auto& cur : _tables)
		{
			while (cur)
			{
				Node* next = cur->_next;
				//将旧表结点重新映射到新表上
				size_t hashi = hash(cur->_kv.first) % newsize;
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				//跳回旧表的下一结点
				cur = next;
			}
		}
		_tables.swap(newtables);
	}

                      细节：

                      1. 二倍扩容（本来应该是接近2倍的素数，这里简单起见没实现）
                      2. 遍历旧表，将旧表结点重新映射到新表上（这里直接链接，而不是创建新节点）
                      3. 最后交换旧表和新表

                      3.6 删除

                      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;
			--_n;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	return false;
}

                      细节：

                      1. 单链表删除，设置prev前置指针
                      2. 注意头删的情况，分类处理

                      3.7 哈希化

                      由于除留余数法涉及到取模运算，而只有整型才能取模。所以针对非整型的数据，需要将其转化为整型，这一过程称为哈希化。

                      template
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
template
struct HashFunc
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& ch : s)
		{
			hash = hash * 31 + ch;
		}
		return hash;
	}
};

                      细节：

                      1. 第一个哈希化函数，针对的是内置类型（整型或浮点型等），返回值设置为size_t，相近类型会进行隐式类型转换
                      2. 第二个哈希化函数，针对的是字符串，运用了模板的特化。同时，为了防止字符串的异位串（对应字符数相同，而位置不同），并不是直接相加，而是每次相加后乘以31，保证肯定不重复。
                      3. 同时，如果针对特殊的类，用户可以手写一个特定的哈希化函数进行模板传参

                      总结

                      相比闭散列，开散列看似增加了存储指针的空间开销，实际上闭散列要保证大量的空闲单元以降低哈希冲突，所以开散列反而更加节省空间，其空间利用率更高！

                      哈希表与红黑树的对比：

                      • 哈希表平均查找可达O(1)，但最坏降到O(N)（哈希冲突）
                      • 红黑树最坏查找也可保持O(logN)，比较稳定

                        数据有序性：哈希表无序，而红黑树有序

                        适用场景：哈希表适合单点查找，红黑树适合范围查找

                        【C++练级之路】【Lv.18】哈希表（哈希映射，光速查找的魔法）

                        真诚点赞，手有余香
VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]