哈希概念 | 哈希函数 | 哈希冲突 | 哈希桶实现 | 哈希线性探测代码实现 | 闭散列 | 开散列 | 字符串哈希算法

2024-01-28 16:12
文章标签 算法 代码 实现 函数 字符串 概念 哈希 线性 冲突 探测 闭散列 开散列

本文主要是介绍哈希概念 | 哈希函数 | 哈希冲突 | 哈希桶实现 | 哈希线性探测代码实现 | 闭散列 | 开散列 | 字符串哈希算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

        • 1.哈希概念
        • 2.哈希冲突
        • 3.解决哈希冲突
          • 3.1.闭散列
          • 3.2.开散列
        • 4.字符串哈希算法

1.哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。如果一个顺序结构，有N个数据，数据之间没有顺序，暴力查找时间复杂度是O（N），但如果数据之间是有序的，就可以使用二分查找能快速的找到查找的值，但是，顺序结构保证有序来存储数据，插入和删除的代价太大！
在这里插入图片描述

对应平衡树来说，查找的时间复杂度O（log2(N)）很优秀！

在这里插入图片描述

但更理想（高效）的方法是：将存储的值和存储的位置一一对应，那么一次就能找到要查找的元素；哈希(散列)方法：通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系；构造出来的结构称为哈希表(Hash Table)(或者称散列表)

在这里插入图片描述

这样的哈希函数称为 除留余数法；常用的还有，直接定址法。

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B，在关键字分分布集中的情况的下使用比较好，但是，如果存储的key范围分散如：arr[] = {1,111,999}要存储这些数据就很麻烦！

我们来看一个直接地址法的例子：字符串中第一个只出现一次字符

题目描述：给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。如：输入: s = “leetcode” 输出: 0

题目提示：s 只包含小写字母，说明关键字集中。

class Solution {
public:int firstUniqChar(string s) {int temp[256] = {0};for(char ch : s){temp[ch]++;}for(int i = 0; i < s.size();i++){if(temp[s[i]] == 1){return i;}}return -1;}
};
2.哈希冲突

在这里插入图片描述

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

3.解决哈希冲突
3.1.闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以key存放到冲突位置中的下一个空位置中去

下面使用线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。解决哈希冲突的问题，当然还有 二次探测（H_i = (H_0 + i^2 )% m, 或者：H_i = (H_0 - i^2 )% m。其中：i =1,2,3…，H_0是通过散列函数Hash(x)对元素的关键码key 进行计算得到的位置m是表的大小。

在这里插入图片描述

这两种方法，在解决哈希冲突的时候对其他元素产生影响，如：现在要插入数据8，这个位置被14占了，就需要找下一个位置；当然这种方法，也会浪费大量的空间，但这就是用空间换时间的策略，后面开散列才是常用的解决哈希冲突的方法！

在这里插入图片描述

下面快速的使用闭散列的线性探测，实现基于闭散列的哈希表：

代码结构：

namespace order_table
{enum state{EXIST = 1,EMPTY,DELETE};template<class K, class V>struct HashData{std::pair<K, V> _kv;state _st = EMPTY;};template<class K,class V>class HashTable{typedef HashData<K, V> Data;public:HashTable(const size_t size = 5){_table.resize(size);}...private:std::vector<Data> _table;size_t _n = 0;				//  填入表中的元素个数};
}

插入操作：

  1. 通过哈希函数，计算出待插入的位置，如果没有哈希冲突（也就是说判断这个位置有没有插入的值了）直接插入，这里定义一个枚举类型来判断状态
  2. 如果哈希冲突，使用线性探测的方式，寻找下一个空位置！
  3. 在插入之前其实有一个重要的扩容问题，哈希表什么时候扩容呢？ 哈希表的载荷因子定义为：α = 填入表中的元素个数 / 哈希表的长度；α 越大说明，填入表中的元素个数越多，哈希冲突的概率就会越大，所以在开放定址法中α严格定义在0.7 - 0.8之间！
  4. 哈希表扩容是会重新遍历，所以在扩容的那一下会消耗大一些
bool insert(const std::pair<K, V>& kv)
{// 查找一下，不添加重复的元素if (find(kv.first)){return false;}// 扩容if ((double)_n / (double)_table.size() >= 0.7){size_t newsize = _table.size() * 2;HashTable tb(newsize);for (int i = 0; i < _table.size(); i++){if (_table[i]._st == EXIST){tb.insert(_table[i]._kv);}}_table.swap(tb._table);}// 通过哈希函数，计算出待插入的位置，int hashi = kv.first % _table.size();// 线性探测，避免哈希冲突while (_table[hashi]._st == EXIST){hashi++;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._st = EXIST;_n++;return true;
}

查找操作

  1. 查找hash表中的元素，通过哈希函数计算初步计算出了查找的位置，EXIST存在但有可能不是查找的元素，如查找14，计算到了4这个位置，但是不是要找元素，另外，当找到状态为DELETE是不能停下来的！要找到下一个空（EMPTY）位置！

    在这里插入图片描述

  2. 如果找到下一个空（EMPTY）位置说明，哈希表中不存在该元素！

Data* find(const K& key)
{int hashi = key % _table.size();while (_table[hashi]._st != EMPTY){if (_table[hashi]._st == EXIST && _table[hashi]._kv.first == key){return &_table[hashi];}hashi++;hashi %= _table.size();}return nullptr;
}

删除操作

  1. 查找的逻辑，然后，将状态置成DELETE即可。
bool erase(const K& key)
{Data* data = find(key);if (data != nullptr){data->_st = DELETE;_n--;return true;}return false;
}
3.2.开散列

开散列法又叫链地址法(开链法)，或称为哈希桶开辟一个指针数组，通过哈希函数计算关键字，出现哈希冲突时，将冲突的元素通过单链表的方式链接。

在这里插入图片描述

代码结构：

namespace hash_backet
{template<class K,class V>struct HashNode{std::pair<K, V> _kv;HashNode* _next;HashNode(const std::pair<K, V>& kv):_kv(kv),_next(nullptr){}};template<class K,class V>class HashTable{typedef HashNode<K, V> Node;public:HashTable(const size_t size = 5){_table.resize(size, nullptr);}...private:std::vector<Node*> _table;size_t _n = 0;				//  填入表中的元素个数};
}

插入操作：

  1. 考虑扩容，由于使用哈希桶的方式解决哈希冲突的问题，是以链表的方式，对冲突元素进行链接，冲突不对影响其他元素，所以平衡因子 = 1时扩容

  2. 扩容使用现代方法，即重新开辟一个哈希表对象，将旧表元素插入新表中，然后旧表和新表交换！

  3. 哈希冲突时使用头插法

    在这里插入图片描述

bool insert(const std::pair<K,V> kv)
{// 避免插入重复元素if (find(kv.first)){return false;}if (_n / _table.size() >= 1){size_t new_size = _table.size() * 2;HashTable<K, V> new_table(new_size);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){new_table.insert(cur->_kv  );cur = cur->_next;}}_table.swap(new_table._table);}int hashi = kv.first % _table.size();// 插入逻辑Node* new_node = new Node(kv);Node *cur = _table[hashi];_table[hashi] = new_node;new_node->_next = cur;_n++;return true;
}

查找操作

Node* find(const K& key)
{int hashi = key % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

删除操作

  1. 如果为NULL不用删除，返回fasle；如果删除1，即_table[hashi]这个位置，置为NULL然后删除；如果删除4，那么4位置出为cur，prev = _table[hashi]；prev-> _next = cur-> _next，然后delete删除cur
    在这里插入图片描述
bool erase(const K& key)
{int hashi = key % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev = cur->_next;}delete(cur);_n--;return true;}prev = cur;cur = cur->_next;}return false;
}
4.字符串哈希算法

如果你完整的实现了上面的代码，那么使用哈希函数：int hashi = key % _table.size();时会发现，这个哈希函数只能对能整形进行计算！

如何能对浮点数和字符串进行哈希计算呢

template<class K>
struct DefaultHashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct DefaultHashFunc<std::string>
{size_t operator()(const std::string& key){size_t hash = 0;for (char ch : key){hash = hash * 131 + ch;}return hash;}
};

这样就支持了！关于哈希字符串函数算法：参考博客，完整的哈希桶的实现代码

namespace hash_backet
{	template<class K>struct DefaultHashFunc{size_t operator()(const K& key){return (size_t)key;}};template<>struct DefaultHashFunc<std::string>{size_t operator()(const std::string& key){size_t hash = 0;for (char ch : key){hash = hash * 131 + ch;}return hash;}};template<class K,class V>struct HashNode{std::pair<K, V> _kv;HashNode* _next;HashNode(const std::pair<K, V>& kv):_kv(kv),_next(nullptr){}};template<class K,class V>class HashTable{typedef HashNode<K, V> Node;public:HashTable(const size_t size = 5){_table.resize(size, nullptr);}bool insert(const std::pair<K,V> kv){// 避免插入重复元素if (find(kv.first)){return false;}if (_n / _table.size() >= 1){size_t new_size = _table.size() * 2;HashTable<K, V> new_table(new_size);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){new_table.insert(cur->_kv  );cur = cur->_next;}}_table.swap(new_table._table);}DefaultHashFunc<K> dtf;size_t hashi = dtf(kv.first )% _table.size();// 插入逻辑Node* new_node = new Node(kv);Node *cur = _table[hashi];_table[hashi] = new_node;new_node->_next = cur;_n++;return true;}bool erase(const K& key){DefaultHashFunc<K> dtf;size_t hashi = dtf(key )% _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev = cur->_next;}delete(cur);_n--;return true;}prev = cur;cur = cur->_next;}return false;}Node* find(const K& key){DefaultHashFunc<K> dtf;size_t hashi =  dtf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}void print(){for (int i = 0; i < _table.size(); i++){printf("%d:", i);Node* data = _table[i];while (true){if (data== nullptr){std::cout << "NULL" << std::endl;break;}else{std::cout << data->_kv.second << "-->";data = data->_next;}}}}private:std::vector<Node*> _table;size_t _n = 0;				//  填入表中的元素个数，用于计算平衡因子};
}

这篇关于哈希概念 | 哈希函数 | 哈希冲突 | 哈希桶实现 | 哈希线性探测代码实现 | 闭散列 | 开散列 | 字符串哈希算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/654128。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2