C++寻位映射的奇幻密码：哈希

发布于：2025-05-20 ⋅ 阅读:(12) ⋅ 点赞:(0)

文章目录

哈希，用于将任意大小的数据映射为固定长度的数值（哈希值），这个过程通过哈希函数实现，其核心目标是高效地存储、查找和验证数据

1.什么是哈希？

在这里插入图片描述

在学哈希之前，我们对于数据的查找通常是建立于顺序表，树形结构的基础上进行的查找，但是随着数据量越来越庞大，数据的随机性和容量越发严峻

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

因此就在此基础上发展出了一种平均时间复杂度几乎为 O(1) 的数据查找方式，哈希，也称为散列

2.哈希的常见实现方法

2.1 直接定址法

在这里插入图片描述

对于一段相对集中的数据段，就可以使用直接定址法，这里最大的数是 30，最小的数是15，创建一个大小为 15 的数组，将所有值映射到数组上

优点： 简单、均匀
缺点： 需要事先知道关键字的分布情况
使用场景： 适合查找比较小且连续的情况，数据太分散就不适合了，开的数组会太大，造成空间浪费

2.2 除留余数法

在这里插入图片描述

除留余数法是一种通过固定的哈希函数计算方式将数据放入哈希表的常用方法，设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3.哈希冲突

简单来说，通过除留余数法，将每个进来的值除以哈希表的大小得到的余数，必定是在所开哈希表的容器大小范围内的，但是有可能不同的 key 会除出相同的余数，造成同一位置的冲突，该种现象称为哈希冲突或哈希碰撞

4.哈希冲突的解决

4.1 闭散列

也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把 key 存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

4.1.1 线性探测

下面将通过对借助哈希表的实现解析线性探测相关的知识：

4.1.1.1 哈希表的基本数据结构
enum STATE
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	STATE _state = EMPTY;
};

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
public：
	HashTable()
	{
		_table.resize(10);
	}

private:
	vector<HashData<K, V>> _table;
	size_t _n = 0; // 存储有效数据的个数
};

设置 _kv 存储实际的键值对数据，_state 跟踪该位置的状态

  • EXIST 表示位置已被占用（存在有效元素）
  • EMPTY 表示位置为空（从未被使用）
  • DELETE 表示位置已删除（曾被占用，现已删除）

为什么要用状态来表示呢？

因为用状态表示是最清晰直接的，有人说用零来表示已经删除的值不就好了，但是万一本身存储的值就是零呢？总而言之用状态表示是最方便的

4.1.1.2 哈希表的key转换
template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

除留余数法一般是对整数进行操作，但是我们并不能保证 key 一定是整数，有人说直接强转不就好了，但是你能保证强转的数据一定是对的吗？可能是 double，也有可能是string，因此最好的方法是利用我们之前常用的仿函数进行统一操作

整数小数等就走默认的 DefaultHashFunc 类，当 key 是 string 类型的时候，就走特化的版本 DefaultHashFunc<string>，这里特化是为了统一性，不然你再造一个仿函数就太麻烦了

template<class K, class V, class HashFunc = DefaultHashFunc<K>>

将仿函数设为默认类型，这样子在创建例如 HashTable<string, string> dict 的哈希表的时候就不用显式写仿函数的类型

🔥值得注意的是： 这里的 string 特化版本的仿函数，进行了一些 BKDR 数学上的处理，假设有 "abc"，"bca" 两个字符串，这两个字符串其实是不一样的数据，如果没有进行 hash *= 131 的数据处理，那么这两个字符串的加和就是一样的，那么使用除留余数法的时候就会发生哈希冲突

具体分析可以看博客园里的大佬的分析：

传送门：字符串Hash函数对比

4.1.1.3 哈希表的插入
bool Insert(const pair<K, V>& kv)
{
	// 扩容
	//if ((double)_n / (double)_table.size() >= 0.7)
	if (_n * 10 / _table.size() >= 7)
	{
		size_t newSize = _table.size() * 2;
		// 遍历旧表，重新映射到新表
		HashTable<K, V, HashFunc> newHT;
		newHT._table.resize(newSize);

		// 遍历旧表的数据插入到新表即可
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i]._state == EXIST)
			{
				newHT.Insert(_table[i]._kv);
			}
		}

		_table.swap(newHT._table);
	}

	// 线性探测
	HashFunc hf;
	size_t hashi = hf(kv.first) % _table.size();
	while (_table[hashi]._state == EXIST)
	{
		++hashi;
		hashi %= _table.size();
	}

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

	return true;
}

这里的插入，解决哈希冲突的方式利用的是线性探测的方式：

先对哈希函数计算值所带入的 key 进行处理，转换为合理的计算值，如果计算得出的位置为 EXIST，就依次往后探测，直到找到空位置为止，然后插入即可

那么哈希表满了之后的扩容是怎么一回事呢？

在这里插入图片描述

我们要知道判断一个哈希表是否应该开始扩容的标准是负载因子，通过 size / capacity 判断哈希表的填充程度，我们这里设置为 0.7 即扩容

既然扩容了，之前的数据就必须重新计算位置放入哈希表，不然关系就全乱了，或许会有人想为什么不直接新创建一个数组来放？而是创建一个新对象 HashTable<K, V, HashFunc> newHT，再来创建新哈希表，这是因为在对象里操作可以使用插入等便捷操作，使得新哈希表的创建更方便

🔥值得注意的是：

  • 计算位置时除 size，而不是 capacity，因为 size 直接反映了数组的有效长度， capacity 只是为创建更大的数组做准备的，[0, table_size-1] 是索引的合法范围
  • hashi %= _table.size() 是为了避免超出数组有效索引范围，只要大于 size 就会被除余回到数组第一个位置
  • 有人担心扩容会影响搜索效率，其实影响并不是很大，每次扩容都为之前的两倍，会比之前大很多，也就碰上扩容那一次效率不太高，整体来讲影响是不大的
4.1.1.4 哈希表的查找
HashData<const K, V>* Find(const K& key)
{
	// 线性探测
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	while (_table[hashi]._state != EMPTY)
	{
		if (_table[hashi]._state == EXIST
			&& _table[hashi]._kv.first == key)
		{
			return (HashData<const K, V>*) & _table[hashi];
		}

		++hashi;
		hashi %= _table.size();
	}

	return nullptr;
}

循环条件为 _table[hashi]._state != EMPTY 是因为在插入的时候为空就必定插入，那么查找的过程中在找到新的空之前必定能找到想要的值（如果正确插入的话），if条件还必须加入 _table[hashi]._state == EXIST 是因为避免查找到的是已删除的值

🔥值得注意的是： 返回的是 HashData<const K, V>*，而不是 HashData< K, V>*，防止 key 被错误修改

4.1.1.5 哈希表的删除
bool Erase(const K& key)
{
	HashData<const K, V>* ret = Find(key);
	if (ret)
	{
		ret->_state = DELETE;
		--_n;

		return true;
	}

	return false;
}

删除可以说是我们学的那么多个结构里，比插入简单的了，直接删除修改状态即可

4.1.2 二次探测

二次探测的位置计算基于平方序列探测的，下面将给出详细的计算步骤：

  1. 核心计算公式

给定初始哈希位置 h₀ 和探测次数 i，下一个探测位置为：

h(i) = (h₀ + i²) % table_size
  • h₀：初始哈希值（例如 hash(key) % table_size）
  • i：探测次数，从 1 开始递增
  • table_size：哈希表的大小（必须为素数，否则可能无法覆盖所有槽位）
  1. 计算步骤示例

假设哈希表大小 table_size = 7（素数），初始哈希位置 h₀ = 3，插入时发生冲突，则二次探测的位置序列为：

探测次数 i 计算公式 结果 h(i)
1 (3 + 1²) % 7 4
2 (3 + 2²) % 7 0
3 (3 + 3²) % 7 5
4 (3 + 4²) % 7 2
5 (3 + 5²) % 7 6
6 (3 + 6²) % 7 1

序列： 3 → 4 → 0 → 5 → 2 → 6 → 1，覆盖所有 7 个槽位

  1. 为什么表大小必须是素数？
    若 table_size 为合数，可能无法覆盖所有槽位。例如，当 table_size = 4（合数）时：
探测次数 i 计算公式 结果 h(i)
1 (h₀ + 1²) % 4 h₀ + 1
2 (h₀ + 2²) % 4 h₀
3 (h₀ + 3²) % 4 h₀ + 1

序列： h₀ → h₀+1 → h₀ → h₀+1，只能访问 2 个槽位，导致死循环

  1. 代码实现示例
bool Insert(const pair<K, V>& kv)
{
    // 扩容逻辑（略）
    
    HashFunc hf;
    size_t h0 = hf(kv.first) % _table.size();
    
    // 二次探测
    for (size_t i = 1; i < _table.size(); ++i) {
        size_t hashi = (h0 + i * i) % _table.size();
        
        if (_table[hashi]._state != EXIST) {
            _table[hashi]._kv = kv;
            _table[hashi]._state = EXIST;
            ++_n;
            return true;
        }
    }
    
    return false; // 表满（实际不会触发，因提前扩容）
}

4.1.3 线性探测和二次探测对比

特性 线性探测 二次探测
探测序列 h₀, h₀+1, h₀+2, ... h₀, h₀+1, h₀+4, h₀+9, ...
聚集问题 严重（主聚集） 较轻（二次聚集）
空间利用率 低（易导致连续槽位被占用） 高（更均匀分布）
表满检测 遍历全量槽位即可检测 需遍历约一半槽位

4.2 开散列

4.2.1 哈希桶

在这里插入图片描述

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

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷，那么有没有办法不把数据只局限在数组里，有的兄弟有的，可以使用拉链法，也叫哈希桶，将数据以单链表的形式挂起来

4.2.1.1 哈希表的基本数据结构
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 = DefaultHashFunc<K>>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
	HashTable()
	{
		_table.resize(10, nullptr);
	}

	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}

			_table[i] = nullptr;
		}
	}
private:
	vector<Node*> _table; // 指针数组
	size_t _n = 0; // 存储了多少个有效数据
};

vector<Node*> 或者 vector<list> 都是可以的，节点都是指针需要释放，析构函数需要自己实现

4.2.1.2 哈希表的插入
bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}

	HashFunc hf;

	// 负载因子到1就扩容
	if (_n == _table.size())
	{
		size_t newSize = _table.size() * 2;
		vector<Node*> newTable;
		newTable.resize(newSize, nullptr);

		// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;

				// 头插到新表
				size_t hashi = hf(cur->_kv.first) % newSize;
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;

				cur = next;
			}

			_table[i] = nullptr;
		}

		_table.swap(newTable);
	}

	size_t hashi = hf(kv.first) % _table.size();
	// 头插
	Node* newnode = new Node(kv);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;
	return true;
}

由于每个哈希桶可以挂多个数据以节省空间，负载因子可以扩大到 1，平均下来一个桶一个数据

在这里插入图片描述

这里悬挂操作是以如图头插的方式进行的，在扩容时，把原先的桶挂到新表上的时候，由于是头插，原先的单链表会在新表上倒置，但是这不影响查找元素，每条桶的元素还是固定的，只是顺序不一样而已

4.2.1.3 哈希表的查找
Node* Find(const K& key)
{
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	Node* cur = _table[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}

		cur = cur->_next;
	}

	return nullptr;
}

当查找的节点为头节点时，prev为空，

4.2.1.4 哈希表的删除
bool Erase(const K& key)
{
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	Node* prev = nullptr;
	Node* cur = _table[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (prev == nullptr)
			{
				_table[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}

			delete cur;
			return true;
		}

		prev = cur;
		cur = cur->_next;
	}

	return false;
}

当查找的节点为头节点时，prev 为空，直接让下一个节点成为头节点即可
当查找的节点为其他节点时，让前一个节点和下一个节点链接

记得释放删除的节点

4.3 开散列与闭散列比较

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

事实上： 由于开放地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子 a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布