当前位置： 首页 > web >正文

《从零实现哈希表：详解设计、冲突解决与优化》

web 2025/8/12 6:49:01

《从零实现哈希表：详解设计、冲突解决与优化》

文章目录

  • 《从零实现哈希表：详解设计、冲突解决与优化》
  • 一、哈希概念
    • 1.1 直接定址法
    • 1.2 哈希冲突
    • 1.3 负载因子
    • 1.4 将关键字转为整数
    • 1.5 哈希函数
      • 1.5.1 除法散列法/除留余数法
      • 1.5.2 乘法散列法
      • 1.5.3 全域散列法
    • 1.6 处理哈希冲突
      • 1.6.1 开放定址法
        • 线性探测
        • 二次探测
        • 双重散列
      • 1.6.2 开放定址法代码实现
        • 扩容
        • key不能取模的问题
        • 完整代码实现
      • 1.6.3 链地址法
        • 解决冲突的思路
        • 扩容
        • 极端场景
      • 1.6.4 链地址法代码实现
  • 二、整体源代码实现

一、哈希概念

在这里插入图片描述

1.1 直接定址法

在这里插入图片描述
在这里插入图片描述

1.2 哈希冲突

在这里插入图片描述

1.3 负载因子

在这里插入图片描述

1.4 将关键字转为整数

在这里插入图片描述

1.5 哈希函数

一个好的哈希函数应该让N个关键字被等概率地均分的散列分布到哈希表的M个空间中，
但是实际中却很难做到，但是我们要尽量往这个方向去考量设计

1.5.1 除法散列法/除留余数法

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

1.5.2 乘法散列法

在这里插入图片描述

1.5.3 全域散列法

在这里插入图片描述

1.6 处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突， 解决冲突的两种方法：开放定址发和链地址法

1.6.1 开放定址法

在这里插入图片描述

线性探测

在这里插入图片描述

二次探测

在这里插入图片描述

双重散列

在这里插入图片描述

1.6.2 开放定址法代码实现

开放定址法在实践中，不如下面讲的链地址发，因为开放定址法解决冲突不管使用哪种方法，
占用的都是哈希表中的空间，始终存在互相影响的问题。
所以开放定址法，我们简单选择线性探测实现即可

在这里插入图片描述

开放定址法的哈希表结构：代码如下（示例）：

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 HashTable
{
private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存储数据个数
};

在这里插入图片描述

扩容

在这里插入图片描述在这里插入图片描述

代码如下（示例）：

inline unsigned long __stl_next_prime(unsigned long n)
{// 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};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;
}
key不能取模的问题

在这里插入图片描述在这里插入图片描述

代码如下（示例）：

template < class K>
struct HashFunc
{size_t operator()(const K & key){return (size_t)key;}
};// 特化
template < >struct HashFunc < string>{// 字符串转换成整形，可以把字符ascii码相加即可// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的// 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131//等效果会⽐较好size_t operator()(const string & key){size_t hash = 0;for (auto e : key){hash *= 131;hash += e;}return hash;}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存储数据个数
};
完整代码实现

代码如下（示例）：

namespace open_address
{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 Hash = HashFunc<K>>class HashTable{public:inline unsigned long __stl_next_prime(unsigned long n){// 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};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;}HashTable(){_tables.resize(__stl_next_prime(0));}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因⼦⼤于0.7就扩容if (_n * 10 / _tables.size() >= 7){// 这⾥利⽤类似深拷⻉现代写法的思想插⼊后交换解决HashTable<K, V, Hash> newHT;newHT._tables.resize(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hash;size_t hash0 = hash(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state == EXIST){// 线性探测hashi = (hash0 + i) % _tables.size();// ⼆次探测就变成 +- i^2++i;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hash;size_t hash0 = hash(key) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 线性探测hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;--_n;return true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存储数据个数};
}

1.6.3 链地址法

解决冲突的思路

在这里插入图片描述在这里插入图片描述

扩容

在这里插入图片描述

极端场景

在这里插入图片描述在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

1.6.4 链地址法代码实现

代码如下（示例）：

// 链地址法代码实现
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;inline unsigned long __stl_next_prime(unsigned long n){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};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;}public:HashTable(){_tables.resize(__stl_next_prime(0), 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;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){Hash hs;size_t hashi = hs(kv.first) % _tables.size();// 负载因⼦==1扩容if (_n == _tables.size()){/*HashTable<K, V> newHT;newHT._tables.resize(__stl_next_prime(_tables.size()+1);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){newHT.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);*/
// 这⾥如果使⽤上⾯的⽅法，扩容时创建新的结点，后⾯还要使⽤就结点，浪费了// 下⾯的⽅法，直接移动旧表的结点到新表，效率更好vector<Node*>newtables(__stl_next_prime(_tables.size() + 1), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t hashi = hs(cur->_kv.first) %newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}// 头插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;size_t hashi = hs(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;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 表中存储数据个数};
}

二、整体源代码实现

代码如下（示例）：

//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 HashTable
//{
//private:
//	vector<HashData<K, V>> _tables;
//	size_t _n = 0; // 表中存储数据个数
//};
//
//
//inline unsigned long __stl_next_prime(unsigned long n)
//{
//	// 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
//	};
//	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;
//}
//#include<string>
//
//template < class K>
//struct HashFunc
//{
//	size_t operator()(const K & key)
//	{
//		return (size_t)key;
//	}
//};
//
// // 特化
//template < >
// struct HashFunc < string>
// {
//	 // 字符串转换成整形，可以把字符ascii码相加即可
//		 // 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
//		 // 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131
//		//等效果会⽐较好
//		 size_t operator()(const string & key)
//		{
//		size_t hash = 0;
//		 for (auto e : key)
//			 {
//				hash *= 131;
//			hash += e;
//		}
//		return hash;
//	}
//};
//template<class K, class V, class Hash = HashFunc<K>>
//class HashTable
//{
//public:
//private:
//	vector<HashData<K, V>> _tables;
//	size_t _n = 0; // 表中存储数据个数
//};namespace open_address
{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 Hash = HashFunc<K>>class HashTable{public:inline unsigned long __stl_next_prime(unsigned long n){// 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};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;}HashTable(){_tables.resize(__stl_next_prime(0));}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因⼦⼤于0.7就扩容if (_n * 10 / _tables.size() >= 7){// 这⾥利⽤类似深拷⻉现代写法的思想插⼊后交换解决HashTable<K, V, Hash> newHT;newHT._tables.resize(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hash;size_t hash0 = hash(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state == EXIST){// 线性探测hashi = (hash0 + i) % _tables.size();// ⼆次探测就变成 +- i^2++i;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hash;size_t hash0 = hash(key) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 线性探测hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;--_n;return true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存储数据个数};
}// 链地址法代码实现
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;inline unsigned long __stl_next_prime(unsigned long n){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};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;}public:HashTable(){_tables.resize(__stl_next_prime(0), 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;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){Hash hs;size_t hashi = hs(kv.first) % _tables.size();// 负载因⼦==1扩容if (_n == _tables.size()){/*HashTable<K, V> newHT;newHT._tables.resize(__stl_next_prime(_tables.size()+1);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){newHT.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);*/
// 这⾥如果使⽤上⾯的⽅法，扩容时创建新的结点，后⾯还要使⽤就结点，浪费了// 下⾯的⽅法，直接移动旧表的结点到新表，效率更好vector<Node*>newtables(__stl_next_prime(_tables.size() + 1), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t hashi = hs(cur->_kv.first) %newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}// 头插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;size_t hashi = hs(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;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 表中存储数据个数};
}
http://www.xdnf.cn/news/17525.html

相关文章：

  • [激光原理与应用-197]：光学器件 - 图解双折射晶体的工作原理
  • Aurora接口FPGA设计
  • C# 异步编程(使用异步Lambda表达式)
  • pdf预览Vue-PDF-Embed
  • C++ 类模板
  • Android MVP架构详解：从理论到实践
  • [优选算法专题一双指针——四数之和]
  • 大语言模型概述
  • 【后端】Java Stream API 介绍
  • Java -- 日期类-第一代-第二代-第三代日期
  • Datawhale AI夏令营第三期，多模态RAG方向 Task2
  • QT环境搭建
  • 下肢康复机器人机械结构设计cad【6张】三维图＋设计说明说书
  • 【数据结构入门】栈和队列
  • 用天气预测理解分类算法-从出门看天气到逻辑回归
  • LeetCode111~130题解
  • Nginx 性能优化与动态内容处理
  • linux 操作ppt
  • 排序概念以及插入排序
  • C++-红黑树
  • 嵌入式 Linux Mender OTA 实战全指南
  • 上海AI Lab、浙大EagleLab等提出RRVF：利用「验证非对称性」，只输入图片学习视觉推理
  • 【LLM】Openai之gpt-oss模型和GPT5模型
  • NestJS Config 入门教程
  • 自动生成视频的AI大模型高效创作指南
  • Java Stream API 实战：提升集合处理的效率与可读性！
  • 微雪电子发布工业级ESP32-S3-POE工控板：8路隔离IO，双核240MHz赋能AIoT，一根网线解决供电与通信，工业物联网迎来高性价比控制新选择
  • 关键点检测（10）——yolov8-pose 复现coco-pose
  • 【QT】QMainWindow：打造专业级桌面应用的基石
  • Python基础教程（七）匹配模式：隐藏在结构之美中的编程革命