【数据结构】哈希表的开散列和闭散列模拟

2024-02-13 23:20

本文主要是介绍【数据结构】哈希表的开散列和闭散列模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

哈希思想


在顺序和树状结构中,元素的存储与其存储位置之间是没有对应关系,因此在查找一个元素时,必须要经过多次的比较。

顺序查找的时间复杂度为0(N),树的查找时间复杂度为log(N)。

我们最希望的搜索方式:通过元素的特性,不需要对比查找,而是直接找到某个元素。

这一个通过key与存储位置建立一一的思想就是hash思想。

哈希表就是基于哈希思想的一种具体实现。哈希表也叫散列表,是一种数据结构。无论有多少条数据,插入和查找的时间复杂度都是O(1),因此由于其极高的效率,被广泛使用。

建立映射关系:
例如集合{8,5,6,3,7,2,1,0}

key为每个元素的值,capaticy为哈希表元素的容量。

357801d7e27342f283f999b121998957.png

映射过程:
元素8   key=8  8%10=8 映射在数组下标为第8的位置上

元素7   映射在下标为7的位置上

  1. 直接定值法:(关键数范围集中,量不大的时候)关键字和存储位置是一一对应,不存在哈希冲突
  2. 除留余数法:(关键字很分散,量很大)关键字和存储位置是一对多的关系,存在哈希冲突

哈希冲突

对于两个数据元素的关键字 eq?k_%7Bi%7D 和 eq?k_j%7B%7D (i != j),有 eq?k_%7Bi%7D != eq?k_j%7B%7D ,但有:Hash(eq?k_%7Bi%7D) == Hash(eq?k_j%7B%7D),即:不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞

例如上述的举例:
key的值为 18  15的时候

hashi计算的方法得出 需要映射到8 和5的位置上,但是8 和5的位置已经存在其它值。这就产生了冲突


哈希冲突的解决

1.开放定址法(闭散列)

a:线性探测

        如果发生冲突,就往后一次一步寻找为空的位置。

b:二次探测

        发生冲突,每次往后走俩步,寻找没有冲突的位置。

线性探测的缺点:容易产生成片的冲突

二次探测的缺点:虽然解决了容易产生成片冲突,但是空间利用率也不高

2.开散列

又称开链法、哈希桶,计算如果产生了哈希冲突,就以链表的形式将冲突的值链接起来。


哈希表的闭散列实现

闭散列哈希中的,每个位置不仅需要存储数据,还需要标注状态,方便查找删除。

enum State { EMPTY, EXIST, DELETE };


标记状态的意义?

在一个哈希表中,如果需要存放,我们会计算出key映射位置。如果key映射位置被占走,会往后继续寻找到删除/空的位置放置。

在查找时,在映射位置找不到时,需要往后寻找,我们不可能一直往后寻找O(N).,那就失去哈希表的价值,当我们遇到存在/删除位置时继续往后寻找,直到找到空位置,说明没有该元素。

因此在存储时,每个位置都必须有状态和数据

		struct Elem{pair<K, V> _val;State _state;};

框架

希表还需要维持容量的问题。因此需要_size表示实际存放,来维持负载因子

template<class K,class V> //k—v结构
class HashTable	
{
public:
//...
private:vector<Elem> _ht;size_t _size;		//实际存储size_t _totalSize;  // 哈希表中的所有元素:有效和已删除, 扩容时候要用到
};

哈希表的插入

  1. 根据K查找是为空,是则返回false
  2. 计算负载因子,是否需要扩容
  3. 插入新元素
  4. 更新位置状态,有效数目增加

扩容的方法

  • 开新的哈希表(默认空间为原来的2倍)
  • 遍历旧表,调用哈希表的插入。
  • 交换俩个表。

		// 插入bool Insert(const pair<K, V>& val){if (Find(val.first) != -1)return false;//负载因子为7时,扩容if ((_size * 10) / _ht.size() == 7){size_t newsize = _ht.size() * 2;HashTable<K, V>newht;newht._ht.resize(newsize);//遍历旧表for (size_t i = 0; i < _ht.size(); i++){if (_ht[i]._state == EXIST)newht.Insert(_ht[i]._val);}_ht.swap(newht._ht);}//出入新元素size_t hashi = HashFunc(val.first);while (_ht[hashi]._state == EXIST){++hashi;hashi %= _ht.size();}_ht[hashi]._val = val;_ht[hashi]._state = EXIST;++_size;++_totalSize;return true;}

哈希表的查找

通过hash函数映射到hashi,往后一直比对,遇到存在比对,不是要找的val就往后需要,遇到删除也往后对比。直到遇到空返回。

		// 查找size_t Find(const K& key){size_t hashi = HashFunc(key);while (_ht[hashi]._state != EMPTY){if (_ht[hashi]._state == EXIST&& _ht[hashi]._val.first == key){return hashi;}++hashi;hashi %= _ht.size();}return -1;}

哈希表的删除

删除是比较简单,是一种伪删除,不需要对数据清楚,只需要修改状态为删除,减少有效个数

  1. 调用find,没有则返回flase
  2. 修改为状态
  3. 减少个数
		bool Erase(const K& key){int hashi = Find(key);if (hashi == -1)	return false;_ht[hashi]._state = DELETE;--_size;return true;}

这三部分就是闭散列的主体结构。需要维持负载因子和状态。

Gitee: 闭散列哈希代码


哈希桶


开散列哈希表就不要需要状态的使用,是由一个链表的数组构成。

就是一排一排的桶。想要查找数据,只需要映射位置,在桶中寻找,是O(1)的放法.

特别极端情况下可能达到O(N)。

框架


底层可以依赖单链表,只需要简单的头插即可。

链表的结点:需要包含下一个位置的指针,需要包含pair键值对

	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){}};

同样需要记录表中有效元素的个数,但是一般情况下,负载因子在80%-90%效率最大

我们为了简单实现,在100%时才扩容。 

template<class K, class V>
class HashTable
{
public://...
private:vector<Node*> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

哈希桶的插入

  1. 检查是否为已经存在的Key
  2. 检查负载因子,为1就扩容
  3. 往hashi位置头插插入
  4. 修改个数

扩容的方法

  1. rasize一个二倍数量的原表
  2. 遍历旧表,将一个元素从链表的头取下,插入到新表中的hashi位置上。注意保存下一个位置!
  3. 交换俩张表

		bool Inset(const pair<K, V>& kv){if (Find(kv.first)){return false;}hash hf;//扩容if (_tables.size() == _n){size_t newsize = _tables.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);for (size_t i = 0; i < (_tables.size()); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first % newtable.size());//头插cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);}size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}


哈希桶的查找

  • 计算hashi
  • 遍历单链表
  • 为空则返回flase
		Node* Find(const K& key){hash fc;size_t hashi = fc(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 fc;size_t hashi = fc(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){//找到了if (cur->_kv.first == key){//头删if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}}return false;}

 Gitee: 开散列哈希桶代码


关于仿函数HashFunc

仿函数是一种回调,可以定义出函数对象。

是对不同类型转化为key,之前在位图就已经介绍,本文用的是BDK算法

对于string字符串类型会有存在冲突,但是可以通过不同的算法映射到不到的位置上,通过几个值的比对能减少失误的概率。

template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};//特化 针对字符串
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDRsize_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};

 

 

这篇关于【数据结构】哈希表的开散列和闭散列模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/706897

相关文章

哈希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

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

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

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

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表(Hash Table)是一种数据结构,它通过将键(Key)映射到值(Value)的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希