数据结构 哈希表

数据结构 哈希表

文章目录

  • 数据结构 哈希表
    • 1. 概念
    • 2. 冲突-概念
    • 3. 冲突-避免
      • 3.1 哈希函数设计
      • 3.2 负载因子调节
    • 4.冲突-解决
      • 4.1 闭散列
      • 4.2 开散列(哈希桶)
      • 4.3 哈希桶实现
    • 5. 性能分析
    • 6. 和java类集的关系

1. 概念

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

理想的搜索方法:

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

当向该结构中:

  • 插入元素

    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放

  • 搜索元素

    对元素的关键码进行同样的计数,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(HashTable)(或者称散列表)

例如:数据集合{1, 7, 6, 4, 5, 9};

哈希函数设置为**:hash(key) = key % capacity**; (capacity为存储元素底层空间总的大小)

在这里插入图片描述

用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较块

但是,如果按照上述哈希方法向集合中插入元素44,却会出现问题,为什么?往下看

2. 冲突-概念

对于两个数据元素的关键字 ki 和 k(j),有ki != kj,但有:Hash(ki) == Hash(kj),即:不同关键字通过相同哈希函数计算出相同的哈希地址,该现象称为哈希冲突或哈希碰撞

我们把具有不同关键码而具有相同哈希地址的数据元素称为"同义词"

3. 冲突-避免

首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题,冲突的发生是必然的,我们能做的就是尽量降低冲突率

3.1 哈希函数设计

引起哈希冲突的一个元素可能是:哈希函数设计不够合理

哈希函数设计原则:

  • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

常见哈希函数

  1. 直接定制法

    取关键字的某个线性函数为散列地址:Hash(Key) = A * Key + B

    优点:简单、均匀 缺点:需要事先知道关键字的分布情况

    使用场景:适合查找比较小且连续的情况

    代码示例:

    class Solution {public int firstUniqChar(String s) {int[] count = new int[26];for (int i = 0;i < s.length();i++) {count[s.charAt(i) - 97]++;}for (int i = 0;i < s.length();i++) {if (count[s.charAt(i) - 97] == 1) {return i;}}return -1;}}
    

    在这里插入图片描述

  2. 除留余数法

    设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数: Hash(Key) = Key % p(p <= m),将关键码转换成哈希地址

注:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

3.2 负载因子调节

在这里插入图片描述

负载因子和冲突率的关系粗略演示

在这里插入图片描述

所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率

已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组大小

4.冲突-解决

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

4.1 闭散列

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

那么如何寻找下一个空位置呢?

比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已放了值为4的元素,即发生哈希冲突

  1. 线性探测

    • 插入

      • 通过哈希函数获取待插入元素在哈希表中的位置

      • 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素

        在这里插入图片描述

      • 采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其它元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素

  2. 二次探测

    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后去找,因此二次探测为了避免该问题,找下一个空位置的方法为:Hi = (H0 + i²) % m,或者:Hi = (H0 - i²) % m。其中:i = 1,2,3…,H0是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置,m是表的大小。对于2.1中如果要插入44,产生冲突,使用解决后的情况为:

    在这里插入图片描述

    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容

因此,闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷

4.2 开散列(哈希桶)

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头节点存储在哈希表中

在这里插入图片描述

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

开散列(哈希桶),可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索

当冲突比较严重时,小集合的搜索性能解决效果也不高,这个时候

我们需要将这个所谓的小集合搜索问题继续进行转换,例如:

  1. 每个桶的背后是另一个哈希表
  2. 每个桶的背后是一棵搜索树

4.3 哈希桶实现

代码示例:

package demo1;public class HashBuck {static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] array; // 数组的每个元素都是一个桶,每个桶里都存放链表public int usedSize; // 实际存放数据public static final float DEFAULT_LOAD_FACTOR = 0.75f;public HashBuck() {array = new Node[10];}/*插入元素*/public void put(int key, int val) {int index = key % array.length;Node cur = array[index];while(cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}// 遍历完后说明没有找到key元素,利用头插法将元素加进桶中Node newNode = new Node(key, val);newNode.next = array[index];array[index] = newNode;usedSize++;//若负载因子超过0.75,扩容if (doLoadFact() > DEFAULT_LOAD_FACTOR) {resize();}}/*扩容*/private void resize() {Node[] newArray = new Node[array.length * 2];//遍历原来的数组for (int i = 0;i < array.length;i++) {Node cur = array[i];while(cur != null) {Node temp = cur.next;int newIndex = cur.key % newArray.length;//采用头插法,将节点插入新数组的newIndex下标中cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = temp;}}array = newArray;}private float doLoadFact() {return usedSize*1.0f / array.length;}/*获取元素*/public int get(int key) {int Index = key % array.length;Node cur = array[Index];while(cur != null) {if (cur.key == key) {return cur.val;}cur = cur.next;}return -1;}
}

在这里插入图片描述

5. 性能分析

虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突个数是可控的,也就是每个桶中的链表的长度是一个常数,所以,通常意义下,我们认为哈希表的插入/删除/查找时间的复杂度是O(1)

6. 和java类集的关系

  1. HashMapHashSet 是java中利用哈希表实现的Map 和 Set
  2. java中使用的是哈希桶方式解决冲突的
  3. java会在冲突链表长度大于一定阈值后,将链表转变为搜索树(红黑树)
  4. java中计算哈希值实际上是调用的类的hashCode方法,进行key的相等性比较是调用key的equals方法。所以如果要同自定义类作为HashMap的key或者HashSet的值,必须覆写hashCode和equals方法,并且要做到equals相等的对象,hashCode一定是一致的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/167958.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QML之Repeater 控件使用

Repeater 控件是 重复作用 根据 model中的index 数量进行重复 废话不说 直接看如何用 当model 为数字时 Rectangle{height: 1200width: 500visible: trueanchors.fill: parentColumn{spacing: 20Repeater{model: 10delegate: Rectangle{width: 60height: 20color: index%2 …

Locust负载测试工具实操

本中介绍如何使用Locust为开发的服务/网站执行负载测试。 Locust 是一个开源负载测试工具&#xff0c;可以通过 Python 代码构造来定义用户行为&#xff0c;避免混乱的 UI 和臃肿的 XML 配置。 步骤 设置Locust。 在简单的 HTTP 服务上模拟基本负载测试。 准备条件 Python…

基于Pix4D使用无人机光学影像制作正射影像(DOM)和数字表面模型(DSM) 操作步骤

基于Pix4D使用无人机光学影像制作正射影像&#xff08;DOM&#xff09;和数字表面模型&#xff08;DSM&#xff09; 操作步骤 0. 前言1.获取无人机光学影像2.DOM和DSM3.操作步骤3.1 初始界面3.2 新建项目3.3查看处理过程报告3.4查看处理进度和成果 4.在ArcMap中打开DSM和DOM 0.…

学习笔记2——Nosql

学习笔记系列开头惯例发布一些寻亲消息 链接&#xff1a;https://baobeihuijia.com/bbhj/contents/3/194205.html 跟学链接 跟学视频链接&#xff1a;https://www.bilibili.com/video/BV1S54y1R7SB/?spm_id_from333.999.0.0 &#xff08;建议有java基础的同学学习或者一直…

Mac电脑无法识别移动硬盘怎么办?

很多人都喜欢在Mac电脑上办公、学习&#xff0c;但有时我们将移动硬盘连接Mac电脑时&#xff0c;却会发现电脑无法识别移动硬盘。那么&#xff0c;Mac电脑无法识别移动硬盘怎么办呢&#xff1f; Mac无法识别移动硬盘的原因 导致Mac不识别移动硬盘的原因有很多&#xff0c;你可…

Jmeter(九):jmeter_逻辑控制器与HTTP Cookie管理器详解

Jmeter&#xff1a;jmeter_逻辑控制器_事务控制器 事务 性能测试中&#xff0c;事务指的是从端到端&#xff0c;一个完整的操作过程&#xff0c;比如一次登录、一次 筛选条件查询&#xff0c;一次支付等&#xff1b;技术上讲&#xff1a;事务就是由1个或多个请求组成的 事务…

Java数据结构之稀疏数组

目录 线性结构与非线性结构线性结构非线性结构 稀疏数组应用场景 代码实现二维数组转稀疏数组稀疏数组转二维数组 线性结构与非线性结构 线性结构 数据结构分两种&#xff0c;线性与非线性&#xff0c;线性结构的数据元素之间存在一对一的关系。 一对一指的是每个数据元素都…

Spring中配置文件参数化

目录 一、什么是配置文件参数化 二、配置文件参数化的开发步骤 一、什么是配置文件参数化 配置文件参数化就是将Spring中经常需要修改的字符串信息&#xff0c;转移到一个更小的配置文件中。那么为什么要进行配置文件参数化呢&#xff1f;我们看一个代码 <bean id"co…

Bootstrap的旋转器组件

旋转效果可以用来指示状态&#xff0c;比如页面的加载状态。 可以用类spinner-border实现普通旋转的旋转器效果。 用类spinner-grow实现渐渐变大的旋转器效果。 01-最基本的示例代码 <!DOCTYPE html> <html> <head><meta charset"UTF-8">…

当年很流行,现在已经淘汰的前端技术有哪些?

近几年&#xff0c;前端技术真可谓是飞速发展&#xff0c;不断有新的技术涌现&#xff0c;爆火的前端框架 Astro&#xff0c;前端运行时 Bun&#xff0c;构建工具 Vite 等都给前端提供了强大动力。当然&#xff0c;也有很多前端技术随着技术的发展不再需要使用&#xff0c;有了…

博客续更(五)

十一、后台模块-菜单列表 菜单指的是权限菜单&#xff0c;也就是一堆权限字符串 1. 查询菜单 1.1 接口分析 需要展示菜单列表&#xff0c;不需要分页。可以针对菜单名进行模糊查询。也可以针对菜单的状态进行查询。菜单要按照父菜单id和orderNum进行排序 请求方式 请求路径…

python输出小数控制的方法

大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 如果有什么疑惑/资料需要的可以点击文章末尾名片领取源码 一、要求较小的精度 将精度高的浮点数转换成精度低的浮点数。 1.round()内置方法 round()不是简单的四舍五入的处理方式。 >>> round(2.5) 2 >>> ro…

Python树莓派开发

欢迎关注博主 Mindtechnist 或加入【智能科技社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和技术。关…

【漏洞复现】蓝凌EIS智慧协同平台saveImg接口存在任意文件上传

漏洞描述 蓝凌智慧协同平台满足组织企业在知识、协同及项目管理系统中建设等需求。该平台在saveImg接口处存在任意文件上传,攻击者可通过该漏洞上传Weshell控制服务器。 免责声明 技术文章仅供参考,任何个人和组织使用网络应当遵守宪法法律,遵守公共秩序,尊重社会公德,…

VM虚拟机创建centos7 64位系统提示此主机不支持64位客户机操作系统,此系统无法运行

VM虚拟机创建centos7 64位系统提示此主机不支持64位客户机操作系统,此系统无法运行 背景解决方案 背景 本身系统是window10 64位专业版系统&#xff0c;理论上不应该不支持64位的。 解决方案 最近安装docker开启了虚拟化hyper-v&#xff0c;关闭即可。 打开cmd&#xff08;…

VLAN互通

文章目录 VLAN互通2种方法单臂路由实现VLAN互通TOP图配置-LSW配置-Router1测试&#xff1a;PC1PC2 VLANIF(更受欢迎)TOP图LSW2配置测试PC1 VLAN互通2种方法 单臂路由实现VLAN互通 TOP图 名称IPGatewayPC1192.168.1.1/24192.168.1.254PC2192.168.2.1/24192.168.2.254 名称VLA…

测试老鸟总结,Allure测试报告-自动化测试详解,惊险避坑...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、Allure安装教程…

Java 8 新特性 Ⅱ

方法引用 举例: Integer :: compare 理解: 可以看作是基于lambda表达式的进一步简化 当需要提供一个函数式接口的实例时, 可以使用lambda表达式提供实例 当满足一定条件下, 可以使用方法引用or构造器引用替换lambda表达式 实质: 方法引用作为函数式接口的实例 (注: 需要熟悉…

Promise笔记-同步回调-异步回调-JS中的异常error处理-Promis的理解和使用-基本使用-链式调用-七个关键问题

Promise笔记 1. 预备知识1.1 实例对象与函数对象1.2 两种类型的回调函数1. 同步回调2. 异步回调 1.3 JS中的异常error处理1. 错误的类型2. 错误处理&#xff08;捕获与抛出&#xff09;3. 错误对象 2.Promise的理解和使用2.1 Promise是什么1.理解Promise2.Promise 的状态3. Pro…

内衣洗衣机有必要买吗?口碑好的小型洗衣机测评

在近年以来&#xff0c;由于人们对健康的认识和生活质量的不断改善&#xff0c;使得内衣洗衣机这一类的产品在近年来得到了飞速的发展&#xff0c;洗烘一体机、洗烘套装的价格总体下降&#xff0c;功能和性能都得到了改善&#xff0c;往往更多的用户会选择一台或者多台洗衣机来…