文档章节

Java中的哈希值

colorlesswind
 colorlesswind
发布于 2016/09/25 09:08
字数 733
阅读 38
收藏 1

1、Hash值有什么用?

     HashMap、HashTable、HashSet,所以涉及到使用Hash值进行优化存储的地方,都会用到HashCode。HashCode是Key,这种计算为提高计算的性能。想想看,一般来说,数组算是比较快的集合类了吧,直接用index定位元素,简直就是O(1)的级别。但是添加元素就不这么乐观了。但是使用hash类的集合,添加元素,移动的元素少,只影响一小块,并且查找元素,由于hash值已经进行了定位分组,所以也会大大缩小涉及面,快速定位。

 

2、Hash值应该符合什么原则?

     A、等幂性。不管执行多少次获取Hash值的操作,只要对象不变,那么Hash值是固定的。如果第一次取跟第N次取不一样,那就用起来很麻烦,需要记录当前是第几次操作,这种需要记录状态的事情,可不是什么好事。

     B、对等性。若两个对象equal方法返回为true,则其hash值也应该是一样的。举例说明:若你将objA作为key存入HashMap中,然后new了一个objB。在你看来objB和objA是一个东西(因为他们equal),但是使用objB到hashMap中却取不出来东西。

     C、互异性。若两个对象equal方法返回为false,则其hash值最好也是不同的,但这个不是必须的,只是这样做会提高hash类操作的性能(碰撞几率低)。

 

3、Hash值应该怎么计算?

   A、简单计算就是组成成员的hash值直接相加即可。比如ObjectA有三个属性,propA、propB和propC,最直接的计算方式就是propA.hashcode+propB.hashcode+propC.hashcode。

 

   B、但是如果遇到有顺序相关的怎么办?比如String类型是由char数组组成,并且这些数组是有顺序的。如果使用第一种计算方法,则“ABCD”和“BCDA”就会产生同样的hashCode,那么怎么办呢?最直接想到的办法就是加权,不同的index加不同的权值,这个权值的确定最直接的方法就是某个常数值的几次幂。比如为String的计算hash值为K^0*A.hashCode+K^1*B.hashCode+K^2*C.hashCode+K^3*D.hashCode。K的选择也有说法,最好不要是偶数,因为偶数的相乘会造成信息的丢失(乘以2就是左移1位,一旦溢出就会造成信息的丢失,这种计算会造成溢出后的值与某个看似不相关的数值得到的结果是一样的),所以最好是奇数,在这一点上比较推荐使用7,因为7=8-1=2^3-1,这样计算的时候,直接左移几位再进行一次普通的加减法即可(Java中常用的是31(32-1=2^5-1))。

© 著作权归作者所有

共有 人打赏支持
colorlesswind
粉丝 1
博文 40
码字总数 9065
作品 0
广州
私信 提问
深入谈谈String.intern()在JVM的实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wangyangzhizhou/article/details/79860622 前言 String 类的方法可能大家比较少用也比较陌生,虽然实际项目中...

超人汪小建(seaboat)
2018/04/09
0
0
ThreadLocal 类 的源码解析以及使用原理

1、原理图说明      首先看这一张图,我们可以看出,每一个Thread类中都存在一个属性 ThreadLocalMap 成员,该成员是一个map数据结构,map中是一个Entry的数组,存在entry实体,该实体包...

小勇DW3
2018/08/13
0
0
java8: hashmap性能提升

HashMap是一个高效通用的数据结构,它在每一个Java程序中都随处可见。先来介绍些基础知识。你可能也知道,HashMap使用key的hashCode()和equals()方法来将值划分到不同的桶里。桶的数量通常要...

xinyitianii
2014/06/17
0
0
一起学Java7新功能扩展——深入历险分享(一)

特此声明:因网友疑问,这里声明一个重要的安全,就是大家所知的java惊现0day漏洞!8月30日,Oralce紧急发布了新版本的JDK和JRE,原因是发现了一个严重的0day漏洞CVE-2012-4681,远程攻击者可...

Beyond-Bit
2012/09/03
0
26
为 Java 程序员准备的 10 分钟 Perl 教程

这10分钟教程并不是Java和Perl的比较。目标是探索作为Java开发人员如何快速学习Perl。以下是一些从我的角度来看的关键笔记。 1.从基础开始 不像java,Perl不需要“main”方法作为入口点。要运...

oschina
2013/11/08
7.6K
17

没有更多内容

加载失败,请刷新页面

加载更多

如何高效地遍历 MongoDB 超大集合?

GitHub 仓库:Fundebug/loop-mongodb-big-collection 本文使用的编程语言是 Node.js,连接 MongoDB 的模块用的是mongoose。但是,本文介绍的方法适用于其他编程语言及其对应的 MongoDB 模块。...

Fundebug
21分钟前
1
0
把自己的代码发布到CocoaPods上

由于多个项目用到同一个功能,所以想把该功能模块化 主要参考了这篇文章:自己的库上传到pod详细步骤 不过还是遇到很多坑。 1,先在GitHub上创建一个仓库。比如我创建了一个PPodTest 2, 克隆...

山里来的
29分钟前
2
0
[activiti6]在springboot增加restful api服务

<activiti.version>6.0.0</activiti.version>... <dependency> <groupId>org.activiti</groupId> <artifactId>activiti-rest</artifactId> ......

Danni3
35分钟前
0
0
毕业季,我的Linux求职之路

毕业季,我的Linux求职之路 秋招终于告一段落了,本硕的七年求学之路也快画上了句号。回首求职的这一段日子,痛苦并快乐着。感谢所有陪伴着我走过这一段路程的同学,所有的辛酸都值得铭记。求...

linuxCool
39分钟前
0
0
PHP教程中验证正整数is_int($value+0),为什么要这样?

最近学习PHP应用,其中有一段是要验证变量是否为正整数,除了is_numeric($value)外,还要加上is_int($value+0)且($value+0) > 0,为什么还要 +0呢?直接验证$value不行吗? ,只要 is_int($...

dragon_tech
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部