哈希表、哈希冲突

哈希表、哈希冲突哈希表1.哈希表是一种以键值key存储数据value的结构,以key作为标识值存储value值;只要输入待查找的key,即可获取其对应的value值。当按照键值查询元素时,使用相同的hash函数将key转换为数组下标,从数组中按照下标对应的位置获取数据。它实际上是数组的一种扩展,数组+链表+红黑树。2.哈希表的设计哈希函数的设计首先不能过于复杂,复杂的哈希函数会间接的影响hash表的性能;其次要求哈希值应该尽可能随机且均匀分布,避免或者减少哈希冲突的数量,使每个桶中存储的数据比较平均。常规的设计方法

大家好,又见面了,我是你们的朋友全栈君。

哈希表
1.哈希表是一种以键值key存储数据value的结构,以key作为标识值存储value值;只要输入待查找的key,即可获取其对应的value值。当按照键值查询元素时,使用相同的hash函数将key转换为数组下标,从数组中按照下标对应的位置获取数据。它实际上是数组的一种扩展,数组+链表+红黑树。
2.哈希表的设计
哈希函数的设计首先不能过于复杂,复杂的哈希函数会间接的影响hash表的性能;其次要求哈希值应该尽可能随机且均匀分布,避免或者减少哈希冲突的数量,使每个桶中存储的数据比较平均。

常规的设计方法有数据分析法,选择数据的业务特征提取部分数据进行计算,然后得到结果再与哈希表数组的长度求余后最为哈希值。另外还有直接寻址法、平方取中法、折叠法和随机数法等。

负载因子(加载因子):减少链表长度
低效扩容:乘以2进行扩容
加载因子越大,哈希表中存储的元素越多,空闲的位置就越少,哈希冲突的概率就越大,插入、删除和查找数据时的性能就随之降低。
应该避免低效扩容,因为极个别情况插入速度非常慢,会导致用户崩溃。
哈希函数
1.哈希函数计算达到的哈希值应该是一个非负整数
2.如果key1==key2,那么hash(key1)==hash(key2)
3.即使两个key的hash值相等,但是有可能key值不相等
4.应用场景:安全加密、唯一标识、数据校验、负载均衡、数据分片和分布式存储等
哈希冲突
由于映射的范围限制,key取值的可能性大于映射范围,出现两个不同的key映射到同一个位置

解决哈希冲突的常见方法有开放地址法和链表法。
开放地址法:一旦出现hash值冲突则通过重新探测新位置的方法来解决冲突。对于线性探测法当哈希表中存储的元素越多时,哈希冲突的概率越高,极端情况下需要探测整个哈希表,时间复杂度为O(n)。
链表法:链地址法,在具体的应用中使用较多,在哈希表中每个桶对应一个链表,把哈希值相同的元素存放在相同桶位置的对应链表中,由于需要对比key值所以插入时间复杂度为O(k),查找和删除时的时间复杂度与链表的长度成正比O(k),一般当k值不是很大时可以粗略的认为O(1)。需要尽量减少链表长度,可以引入一个参数:负载因子或者称为加载因子。负载因子用于间接的限定链表的长度,如果值越大则允许的链表长度越大,哈希表的性能越差,但是加载因子越小空间浪费越严重。

HashMap采用的是链表法解决hash冲突,ThreadLocalMap通过基于线性检测的开放寻址法解决冲突。

开放寻址法数据存储在数组中,可以有效地利用CPU缓存加快查询速度,不会涉及链表和指针的问题。当加载因子较大时会导致大量的探测行为操作,性能会急剧下降,同时删除数据也很麻烦,而且比链表法需要占用更多的存储空间。数据量比较小、负载因子小的时候适合开放地址法。
链表法数据存储在链表中,对内存的利用率比开发地址法高一些,可以容忍比较大的装载因子,由于节点中需要存储next指针,会消耗额外的内存空间【有效载荷问题】。实际上如果考虑链表长度变长的问题,可以考虑引入红黑树,以避免恶意的将数据存储在一个桶中的哈希碰撞攻击问题。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/151682.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 手机写java_手机怎么写java

    手机写java_手机怎么写java手机怎么写java通常我们写java程序都是在电脑上,很少在手机上写程序,因为手机屏幕小,写起来不方便,而且ide也没有电脑的好用。但手机相对来说比较便捷,随时随地就可以写代码,练练手,下面就介绍一下如何在手机上写java程序吧。1、下载安装软件软件名:JavaN-IDE-AndroidBuilder-JavaSECompiler2、进入软件刚开始进入时,会提示你创建工程、包名、主方法类,…

  • 宝塔服务器管理助手Linux面版-使用教程

    宝塔服务器管理助手Linux面版-使用教程

  • SSL 中证书能否够使用IP而不是域名[通俗易懂]

    SSL 中证书能否够使用IP而不是域名

  • docker下载安装教程_安卓安装docker

    docker下载安装教程_安卓安装docker前言Docker提供轻量的虚拟化,你能够从Docker获得一个额外抽象层,你能够在单台机器上运行多个Docker微容器,而每个微容器里都有一个微服务或独立应用,例如你可以将Tomcat运行在一个D

  • python协程系列_Python进阶

    python协程系列_Python进阶协程协程(Coroutine),又称微线程,纤程。(协程是一种用户态的轻量级线程)作用:在执行A函数的时候,可以随时中断,去执行B函数,然后中断B函数,继续执行A函数(可以自动切换)

  • ESLint-的基本介绍[通俗易懂]

    ESLint-的基本介绍[通俗易懂]什么是eslintESLint是一个代码检查工具,用来检查你的代码是否符合指定的规范(例如:=的前后必须有一个空格)。规范行业推荐的规范;在创建项目时,我们使用的是JavaScriptStandardStyle代码风格的规则自定义的规范。你和你的团队可以自行约定一套规范使用ESLint的好处在于:多人协作时代码风格统一eslint是法官,Standard是法律vue-cli工具在创建项目时提供选项,我们前面在创建项目时选中了它,所以它在本项目中是直接生效

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号