请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

java知识分享-我的java记事本

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 1071|回复: 0

Hashcode的作用

[复制链接]

131

主题

132

帖子

581

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
581
发表于 2017-5-29 21:16:14 | 显示全部楼层 |阅读模式
Hash是散列的意思,就是把任意长度的输入,通过散列算法变换成固定长度的输出,该输出就是散列值。关于散列值,有以下几个关键结论:
1、如果散列表中存在和散列原始输入K相等的记录,那么K必定在f(K)的存储位置上
2、不同关键字经过散列算法变换后可能得到同一个散列地址,这种现象称为碰撞
3、如果两个Hash值不同(前提是同一Hash算法),那么这两个Hash值对应的原始输入必定不同
HashCode
然后讲下什么是HashCode,总结几个关键点:
1、HashCode的存在主要是为了查找的快捷性,HashCode是用来在散列存储结构中确定对象的存储地址的
2、如果两个对象equals相等,那么这两个对象的HashCode一定也相同
3、如果对象的equals方法被重写,那么对象的HashCode方法也尽量重写
4、如果两个对象的HashCode相同,不代表两个对象就相同,只能说明这两个对象在散列存储结构中,存放于同一个位置
HashCode有什么用
回到最关键的问题,HashCode有什么用?不妨举个例子:
1、假设内存中有0 1 2 3 4 5 6 7 8这8个位置,如果我有个字段叫做ID,那么我要把这个字段存放在以上8个位置之一,如果不用HashCode而任意存放,那么当查找时就需要到8个位置中去挨个查找
2、使用HashCode则效率会快很多,把ID的HashCode%8,然后把ID存放在取得余数的那个位置,然后每次查找该类的时候都可以通过ID的HashCode%8求余数直接找到存放的位置了
3、如果ID的 HashCode%8算出来的位置上本身已经有数据了怎么办?这就取决于算法的实现了,比如ThreadLocal中的做法就是从算出来的位置向后查找第 一个为空的位置,放置数据;HashMap的做法就是通过链式结构连起来。反正,只要保证放的时候和取的时候的算法一致就行了。
4、如果ID的 HashCode%8相等怎么办(这种对应的是第三点说的链式结构的场景)?这时候就需要定义equals了。先通过HashCode%8来判断类在哪一 个位置,再通过equals来在这个位置上寻找需要的类。对比两个类的时候也差不多,先通过HashCode比较,假如HashCode相等再判断 equals。如果两个类的HashCode都不相同,那么这两个类必定是不同的。
举个实际的例子Set。我们知道Set里面的元素是不可以重复的,那么如何做到?Set是根据equals()方法来判断两个元素是否相等的。比方 说Set里面已经有1000个元素了,那么第1001个元素进来的时候,最多可能调用1000次equals方法,如果equals方法写得复杂,对比的 东西特别多,那么效率会大大降低。使用HashCode就不一样了,比方说HashSet,底层是基于HashMap实现的,先通过HashCode取一 个模,这样一下子就固定到某个位置了,如果这个位置上没有元素,那么就可以肯定HashSet中必定没有和新添加的元素equals的元素,就可以直接存 放了,都不需要比较;如果这个位置上有元素了,逐一比较,比较的时候先比较HashCode,HashCode都不同接下去都不用比了,肯定不一 样,HashCode相等,再equals比较,没有相同的元素就存,有相同的元素就不存。如果原来的Set里面有相同的元素,只要HashCode的生 成方式定义得好(不重复),不管Set里面原来有多少元素,只需要执行一次的equals就可以了。这样一来,实际调用equals方法的次数大大降低, 提高了效率。

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|java知识分享 ( 闽ICP备14003021号-4   

GMT+8, 2019-7-19 16:30 , Processed in 0.086562 second(s), 34 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表
声雨竹官方旗舰店    制砂机    我爱辅助网    煎药机    束丝机    两化融合    深圳seo    网络公关