高效的搜索方式：哈希

article/2025/10/4 19:10:00

前言

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序结构查找时间复杂度为O(N)，平衡树查找时间复杂度为O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

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

一：哈希

哈希是一种新的搜索方式，哈希会通过某种函数将元素的存储位置与它的关键码之间建立一一映射的关系，这样我们可以不经过任何比较，一次直接从表中得到要搜索的元素。哈希方法中使用的转换函数称为哈希函数(散列函数)，构造出来的结构称为哈希表(散列表)。

  1. 插入元素： 根据待插入元素的关键码，以哈希函数计算出该元素的存储位置并按此位置进行存放。
  2. 搜索元素： 根据待搜索元素的关键码，以哈希函数计算出该元素的存储位置并在此位置取元素比较元素关键码。

1.1 哈希冲突

不同的关键码通过相同的哈希函数计算出相同的哈希地址

我们把具有不同关键码而具有相同哈希地址的数据元素称为 ”同义词“，哈希冲突越多，搜索效率就会越低。

我们该怎样解决哈希冲突呢？在下面我们会详细讲解。

1.2 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理

常见的哈希函数：

  1. 直接定址法： 取关键码的某个线性函数为哈希地址。简单均匀，但需要事先知道关键码的分布情况，若数据分布不均匀则可能会浪费较多空间，直接定制法适合查找关键码比较小并且连续的场景。（不存在哈希冲突）
  2. 除留余数法： 在限定大小的空间中将关键码进行映射，依据index = key % capacity将关键码转为哈希地址。（可能会导致哈希冲突）

1.3 哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

二：哈希冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列。

2.1 闭散列（开放定址法）

当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的下一个空位置中去。

那么该如何找到哈希表中的下一个空位置呢？

2.1.1 线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

插入：

  1. 通过哈希函数获取待插入元素在哈希表中的位置。
  2. 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

在这里插入图片描述
删除：

采用闭散列解决哈希冲突时，不能随意物理删除哈希表中已有的元素，否则可能会影响其它元素的搜索（比如直接物理删除元素4，44查找起来也会受影响）。

因此线性探测采用标记的伪删除法来删除一个元素，哈希表的每个空间都有标志，删除将标志位置为DELETE。

代码实现：

enum State{EMPTY,EXITS,DELETE,
};template<class T>
struct HashData{HashData(const T& data = T(), const State& state = EMPTY): _data(data), _state(state){}T _data;State _state;
};// unordered_set<K> -> HashTable<K, K>
// unordered_map<K, V> -> HashTable<K, pair<K, V>>
template<class K,class T, class KeyOfT>
class HashTable{
public:typedef HashData<T> HashData;bool Insert(const T& val){// 负载因子 = 表的数据 / 表的大小（空间换时间）// 衡量哈希表满的程度// 哈希表并不是满了才增容// 哈希表越接近满，冲突的概率就越大，效率就越低// 负载因子越小，冲突概率越小，效率提高的同时，伴随着空间的浪费。if (_tables.size() == 0 || _num*10 / _tables.size() >= 7){// 增容（直接将原表数据拷贝下来会造成表容量增大，而原有的映射关系发生改变的问题）// 1. 开一个二倍的空间HashTable<K,T,KeyOfT> newHT;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newHT._tables.resize(newsize);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXITS){newHT.Insert(_tables[i]._data);}}_tables.swap(newHT._tables);// 2. 将旧表的数据重新映射到新表// 3. 释放旧表的空间}KeyOfT koft;// 计算val中的key在表中映射的位置size_t index = koft(val) % _tables.size();while (_tables[index]._state == EXITS){if (koft(_tables[index].data) == koft(val)){return false;}++index;if (index == _tables.size()){index = 0;}}_tables[index]._data = val;_tables[index]._state = EXITS;_num++;}HashData* Find(const K& key){KeyOfT koft;// 计算val中的key在表中映射的位置size_t index = key % _tables.size();while (_tables[index]._state != EMPTY){if (koft(_tables[index]._data) == key){if (_tables[index]._state == EXITS){return &_tables[index];}else if (_tables[index]._state == DELETE){return nullptr;}}++index;if (index == _tables.size()){index = 0;}}return nullptr;}bool Erase(const K& key){HashData* ret = Find(key);if (ret){ret->_state == DELETE;--_num;return true;}else{return false;}}
private:vector<HashData> _tables;size_t _num = 0; // 存储有效数据的个数
};

优缺点：

  1. 优点：实现非常的简单
  2. 缺点：哈希冲突连在一起造成数据的堆积，不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
2.1.2 二次探测

二次探测：从发生冲突的位置开始以二次方间隔向后探测，找到空位置为止。

代码实现：

bool Insert(const T& d){KeyOfT koft;// 二次探测// 计算d中的key在表中映射的位置size_t  start = koft(d) % _tables.size();size_t index = start;int i = 1;while (_tables[index]._state == EXITS){if (koft(_tables[index]._data) == koft(d)){return false;}index = start + i*i;++i;index %= _tables.size();}_tables[index]._data = d;_tables[index]._state = EXITS;_num++;return true;
}

二次探测使得冲突的数据相对更为分散，可以初步缓解哈希冲突导致的数据堆积问题。

闭散列没有从根源解决哈希冲突，是一种抢占式的插入法则，有可能会造成空间的浪费并且效率会降低。

2.2 开散列（哈希桶）

对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。开散列中每个桶中放的都是发生哈希冲突的元素。

在这里插入图片描述
当大量的数据冲突时，这些发生冲突的数据就会放到同一个链式桶中，查找时效率就会随着桶中数据的增多而降低。

哈希桶如何控制哈希冲突呢？

哈希桶通过负载因子控制哈希冲突，哈希桶中的负载因子可以高一些，一般控制到1。

代码实现：

#include<iostream>
#include<vector>
using namespace std;// 结点结构体
template<class T>
struct Hash_Node{T _data;Hash_Node<T>* _next;Hash_Node(const T& data):_data(data), _next(nullptr){}
};template<class K,class T,class KeyOfT>
class Hash_Table{typedef Hash_Node<T> Node;
private:bool Insert(const T& data){// 计算关键码在vector中的位置KeyOfT koft;// 如果负载因子=1，则增容，避免大量的哈希冲突if (_tables.size() == _nums){vector<Node*> newtables;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newtables.resize(newsize);for (size_t i = 0; i < _tables.size(); i++){// 将旧表中的结点取下，计算在新表中的位置Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t index = koft(cur->_data) % newtables.size();cur->_next = newtables[index];newtables[index] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}size_t index = koft(data) % _tables.size();// 寻找结点存在不存在Node* cur = _tables[index];while (cur){if (koft(cur->_data) == koft(data)){return false;}else{cur = cur->_next;}}// 头插Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_nums;return true;}Node* Find(const K& key){KeyOfT koft;size_t index = key % _tables.size();Node* cur = _tables[index];while (cur){if (koft(cur->_data) == key){return cur;}else{cur = cur->_next;}}return nullptr;}bool Erase(const K& key){// 计算key在表中位置再寻找桶KeyOfT koft;size_t index = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur){// 单链表的删除就要找到被删除结点的前一个结点if (koft(cur->_data) == key){if (prev == nullptr){// 此时删除的是第一个结点_tables[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}vector<Node*> _tables;// 数组中存放结点的指针size_t _nums = 0; // 记录表中存储数据的个数
};

假设总是有一些桶挂的数据很多，哈希冲突比较严重，该怎么解决？

一个桶链的长度超过一定值，就将挂链表改为挂红黑树。（Java HashMap长度超过8）


http://chatgpt.dhexx.cn/article/l8AF8jwQ.shtml

相关文章

默克尔树入门

默克尔树入门

目录 什么是默克尔树构建默克尔树的过程默克尔树验证的原理参考 什么是默克尔树 默克尔树&#xff08;Merkle tree&#xff09;是一种数据结构&#xff0c;以它的提出者默克尔命名&#xff0c;根据默克尔树的性质也可以叫哈希树&#xff0c;是一种典型的二叉树。 默克尔树由根…
阅读更多...
java merkle树,使用Merkle树检测数据不一致(翻译)

java merkle树,使用Merkle树检测数据不一致(翻译)

背景 Cassandra的逆熵功能使用Merkle树来检测副本之间的数据不一致。 定义 Merkle树是一种哈希树&#xff0c;其中的叶子包含各个数据块的哈希值&#xff0c;父节点包含其各自的子节点的哈希值。它提供了一种有效的方法来查找副本上存储的数据块中的差异&#xff0c;并减少了传…
阅读更多...
区块链 — 默克尔树

区块链 — 默克尔树

文章目录 默克尔树生成过程应用场景在区块链中的应用 默克尔树 默克尔树&#xff08;又叫哈希树&#xff09;是一种典型的二叉树结构&#xff0c;有一个根节点、一组中间节点和一组叶节点组成。默克尔树最早由 Merkle Ralf 在 1980 年提出&#xff0c;曾广泛用于文件系统和P2P…
阅读更多...
哈希算法的原理以及代码实现

哈希算法的原理以及代码实现

哈希函数&#xff1a; 简单来说就是把红框内的数字根据 一定规律 存放到下方白色的数组中 &#xff08;称为哈希表&#xff09; 这里它的一定规律是 取余法 H&#xff08;key&#xff09;key%p &#xff08;还有其他方法&#xff0c;这里采用的是取余法&#xff09;,p为这个…
阅读更多...
二、哈希算法和Merkle Tree

二、哈希算法和Merkle Tree

章节系列目录&#xff1a;点击跳转 文章目录 哈希算法哈希函数的定义可靠哈希函数需满足的要求哈希函数的主要作用哈希实际例子 Merkle Tree默克尔树完整性校验的方法哈希列表 Hash ListMerkle Tree 哈希树总结 哈希算法 哈希函数的定义 哈希函数&#xff1a;给一个任意大小的…
阅读更多...
Android安全启动学习（四）：device-mapper-verity (dm-verity)和哈希树

Android安全启动学习（四）：device-mapper-verity (dm-verity)和哈希树

上一篇说AVB内存装不下的较大分区&#xff08;如文件系统&#xff09;可能会使用哈希树&#xff0c;还提到了dm-verity。这篇来看看这两个是啥&#xff1f; dm-verity 1、dm-verity 1、能不能将多个硬盘&#xff0c;映射成一个逻辑的硬盘&#xff0c;那样我们程序就不用关心复…
阅读更多...
哈希表与树的介绍

哈希表与树的介绍

前言 该篇文章&#xff0c;主要带我们认识什么哈希表和树&#xff0c;为我们在研究各个数据结构的实现及扩展算法&#xff0c;有个基本的认识。 哈希表 特点 数组 &#xff1a;寻址容易 &#xff1b;数据连续存储空间链表&#xff1a;插入与删除容易 &#xff1b;放在堆内…
阅读更多...
简单哈希树

简单哈希树

哈希树 在各种介绍里的都比较抽象&#xff0c;其实没有那么难&#xff0c;这里进行一个最简单的说明。 在将一个数进行哈希的时候&#xff0c;我曾经写过关于哈希的这么些东西&#xff1a;对于数&#xff0c;当一个质数不够用的时候&#xff0c;可以加上第二个质数&#xff0c;…
阅读更多...
查找——图文翔解HashTree（哈希树）

查找——图文翔解HashTree（哈希树）

引 在各种数据结构&#xff08;线性表、树等&#xff09;中&#xff0c;记录在结构中的相对位置是随机的。因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。查找的效率依赖于查找过程中所进行的比较次数。 之前我们介绍的各种…
阅读更多...
图文详解哈希树-Merkle Tree（默克尔树）算法解析

图文详解哈希树-Merkle Tree（默克尔树）算法解析

2019独角兽企业重金招聘Python工程师标准>>> Merkle Tree概念 Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1] 1、Hash Hash是…
阅读更多...
图文详解HashTree（哈希树）

图文详解HashTree（哈希树）

引 在各种数据结构&#xff08;线性表、树等&#xff09;中&#xff0c;记录在结构中的相对位置是随机的。因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。查找的效率依赖于查找过程中所进行的比较次数。 之前我们介绍的各…
阅读更多...
哈希树HashTree(trie树)

哈希树HashTree(trie树)

引 在各种数据结构&#xff08;线性表、树等&#xff09;中&#xff0c;记录在结构中的相对位置是随机的。因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。查找的效率依赖于查找过程中所进行的比较次数。 之前我们介绍的各种…
阅读更多...
哈希（Hash）和哈希树（Merkle tree）

哈希（Hash）和哈希树（Merkle tree）

哈希函数&#xff08;英语&#xff1a;Hash function&#xff09;又称散列函数&#xff0c;是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要&#xff0c;使得数据量变小&#xff0c;将数据的格式固定下来。该函数将数据打乱混合&#xff0c…
阅读更多...
哈希树总结-java版

哈希树总结-java版

目录 哈希树的理论基础 质数分辨定律 余数分辨定理 哈希树简介 查找 删除 优点 缺点 哈希树的java实现 节点 哈希树 哈希树的应用 哈希树的理论基础 质数分辨定律 这个定理可以简单的表述为&#xff1a;n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等…
阅读更多...
哈希树的python实现

哈希树的python实现

一、问题的背景 给定一组商品购买信息&#xff0c;找到商品购买中频繁出现的商品集。比如说&#xff0c;我们有如下的商品交易信息&#xff1a; 市场购物信息 TipItems1Bread, Milk2Bread, Diaper, Beer, Egg3Milk, Diaper, Beer, Coke4Bread, Milk, Diaper, Beer5Bread, Milk,…
阅读更多...
哈希列表、哈希链、哈希树

哈希列表、哈希链、哈希树

通过哈希算法检验大量数据&#xff08;比如大量文件&#xff09;的一致性时&#xff0c;常见的存储方案&#xff1a; 哈希列表&#xff08;Hash List&#xff09; 原理&#xff1a; 计算每个数据的哈希值&#xff0c;保存为一个列表。记录该列表的哈希值&#xff0c;用于检验…
阅读更多...
哈希树

哈希树

哈希树&#xff1a; 哈希树(HashTree)算法就是要提供一种在理论上和实际应用中均能有效地处理冲突的方法。一般的哈希(Hash)算法都是O(1)的&#xff0c;而且基本是以空间换时间。这很容易导致对存储空间无限制的需求。本文中哈希树(HashTree)算法在实际操作中使用了一些技巧使…
阅读更多...
哈希树 (HashTree)

哈希树 (HashTree)

在讲hash树之前首先我们来理解一下质数分辨定理。 什么是质数分辨定理&#xff1f; 什么是质数 &#xff1a; 即只能被 1 和 本身 整除的数。 为什么用质数&#xff1a;因为N个不同的质数可以 ”辨别“ 的连续整数的数量&#xff0c;与这些质数的乘积相同。 百度文库解答&#…
阅读更多...
Merkle树介绍

Merkle树介绍

默克尔树&#xff08;Merkle树&#xff09;又叫哈希树&#xff0c;是区块链数据存储运用到的一个重要的技术算法。 简单来说&#xff0c;哈希树&#xff08;默克尔树&#xff09;中&#xff0c;每个节点都标有一个数据块的加密哈希值。哈希树可以用来验证任何一种在计算机中和计…
阅读更多...
Merkle Tree（默克尔树）算法解析

Merkle Tree（默克尔树）算法解析

Merkle Tree概念 Merkle Tree&#xff0c;通常也被称作Hash Tree&#xff0c;顾名思义&#xff0c;就是存储hash值的一棵树。Merkle树的叶子是数据块(例如&#xff0c;文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1] 1、Hash Hash是一个把任意长…
阅读更多...
推荐文章

Copyright @ 2022~2023