深入 HashCode 方法

2024-06-04 06:18
文章标签 方法 深入 hashcode

本文主要是介绍深入 HashCode 方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Go deep into HashCode

为什么HashCode对于对象是如此的重要?
一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的
Hash算法相比还不能叫真正的算法,它如何实现它,不仅仅是程序员的编程水平问题,
而是关系到你的对象在存取是性能的非常重要的关系.有可能,不同的HashCode可能
会使你的对象存取产生,成百上千倍的性能差别.

我们先来看一下,在JAVA中两个重要的数据结构:HashMap和Hashtable,虽然它们有很
大的区别,如继承关系不同,对value的约束条件(是否允许null)不同,以及线程安全性
等有着特定的区别,但从实现原理上来说,它们是一致的.所以,我们只以Hashtable来
说明:

在java中,存取数据的性能,一般来说当然是首推数组,但是在数据量稍大的容器选择中,
Hashtable将有比数组性能更高的查询速度.具体原因看下面的内容.

Hashtable在存储数据时,一般先将作为key的对象的HashCode和0x7FFFFFFF做与操作,因为一个
对象的HashCode可以为负数,这样操作后可以保证它为一个正整数.然后以Hashtable的
长度取模,得到值对象在Hashtable中的索引.

index = (o.hashCode() & 0x7FFFFFFF)%hs.length;
这个值对象就会直接放在Hashtable的第index位置,对于写入,这和数组一样,把一个对象
放在其中的第index位置,但如果是查询,经过同样的算法,Hashtable可以直接通过key得到index,

从第index取得这个值对象,而数组却要做循环比较.所以对于数据量稍大时,Hashtable的查询比数据
具有更高的性能.

虽然不同对象有不同的hashcode,但不同的hashCode经过与长度的取余,就很可能产生相同的index.

极端情况下会有大量的对象产生一个相同的索引.这就是关系Hashtable性能问题的最重要的问题:

Hash冲突.

常见的Hash冲突是不同key对象最终产生了相同的索引,而一种非常甚至绝对少见的Hash冲突
是,如果一组对象的个数大过了int范围,而HashCode的长度只能在int范围中,所以肯定要
有同一组的元素有相同的HashCode,这样无论如何他们都会有相同的索引.当然这种极端
的情况是极少见的,可以暂不考虑,但是对于同的HashCode经过取模,则会产中相同的索引,
或者不同的对象却具有相同的HashCode,当然具有相同的索引.

事实上一个设计各好的HashTable,一般来说会比较平均地分布每个元素,因为Hashtable
的长度总是比实际元素的个数按一定比例进行自增(装填因子一般为0.75)左右,这样大多
数的索引位置只有一个对象,而很少的位置会有几个元素.所以Hashtable中的每个位置存
放的是一个链表,对于只有一个对象是位置,链表只有一个首节点(Entry),Entry的next为
null.然后有hashCode,key,value属性保存了该位置的对象的HashCode,key和value(对象
本身),如果有相同索引的对象进来则会进入链表的下一个节点.如果同一个索引中有多个
对象,根据HashCode和key可以在该链表中找到一个和查询的key相匹配的对象.

从上面我看可以看到,对于HashMap和Hashtable的存取性能有重大影响的首先是应该使该
数据结构中的元素尽量大可能具有不同的HashCode,虽然这并不能保证不同的HashCode
产生不同的index,但相同的HashCode一定产生相同的index,从而影响产生Hash冲突.

对于一个象,如果具有很多属性,把所有属性都参与散列,显然是一种笨拙的设计.因为对象
的HashCode()方法几乎无所不在地被自动调用,如equals比较,如果太多的对象参与了散列.
那么需要的操作常数时间将会增加很大.所以,挑选哪些属性参与散列绝对是一个编程水平
的问题.

从实现来说,一般的HashCode方法会这样:

return Attribute1.HashCode() + Attribute1.HashCode()..[+super.HashCode()],

我们知道,每次调用这个方法,都要重新对方法内的参与散列的对象重新计算一次它们的
HashCode的运算,如果一个对象的属性没有改变,仍然要每次都进行计算,所以如果设置一
个标记来缓存当前的散列码,只要当参与散列的对象改变时才重新计算,否则调用缓存的
hashCode,这可以从很大程度上提高性能.


默认的实现是将对象内部地址转化为整数作为HashCode,这当然能保证每个对象具有不同
的HasCode,因为不同的对象内部地址肯定不同(废话),但java语言并不能让程序员获取对
象内部地址,所以,让每个对象产生不同的HashCode有着很多可研究的技术.

如果从多个属性中采样出能具有平均分布的hashCode的属性,这是一个性能和多样性相矛
盾的地方,如果所有属性都参与散列,当然hashCode的多样性将大大提高,但牺牲了性能,
而如果只能少量的属性采样散列,极端情况会产生大量的散列冲突,如对"人"的属性中,如
果用性别而不是姓名或出生日期,那将只有两个或几个可选的hashcode值,将产生一半以上
的散列冲突.所以如果可能的条件下,专门产生一个序列用来生成HashCode将是一个好的选
择(当然产生序列的性能要比所有属性参与散列的性能高的情况下才行,否则还不如直接用
所有属性散列).

如何对HashCode的性能和多样性求得一个平衡,可以参考相关算法设计的书,其实并不一定
要求非常的优秀,只要能尽最大可能减少散列值的聚集.重要的是我们应该记得HashCode对
于我们的程序性能有着生要的影响,在程序设计时应该时时加以注意.

 

从上面的过程我们可以看到,Object类花费了很大精力完成了一个hashCode功能,但实际上,我们

的对象的多少机会是用来做hash型数据结构的key的?可以说95%以上的时候,一个对象的hashCode

是一个浪费,因为你根本用不到它。遗憾的是这个hashCode被设计成Object类的方法,其实它更应该

在一个接口中定义。当你需要把一个对象作为hash型数据结构r key由这个数据结构检查它是否实现了

hashCode,而其它对象则根本不需要考虑hashCode.

 

另外提醒一点,千万不要用hashCode作为持久化唯一性验证。比如你把"mypasswd"的hashCode

存到数据库作为明码的加密方式。当你的JDK版本发生改变时,String的hashCode完全有可能用一种

新的方式实现。而你原来的hashCode将完全不能验证,结果你是所有用户登录失效。

这篇关于深入 HashCode 方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

QT移植到RK3568开发板的方法步骤

《QT移植到RK3568开发板的方法步骤》本文主要介绍了QT移植到RK3568开发板的方法步骤,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录前言一、获取SDK1. 安装依赖2. 获取SDK资源包3. SDK工程目录介绍4. 获取补丁包二

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

Android WebView无法加载H5页面的常见问题和解决方法

《AndroidWebView无法加载H5页面的常见问题和解决方法》AndroidWebView是一种视图组件,使得Android应用能够显示网页内容,它基于Chromium,具备现代浏览器的许多功... 目录1. WebView 简介2. 常见问题3. 网络权限设置4. 启用 JavaScript5. D

Java捕获ThreadPoolExecutor内部线程异常的四种方法

《Java捕获ThreadPoolExecutor内部线程异常的四种方法》这篇文章主要为大家详细介绍了Java捕获ThreadPoolExecutor内部线程异常的四种方法,文中的示例代码讲解详细,感... 目录方案 1方案 2方案 3方案 4结论方案 1使用 execute + try-catch 记录

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法

《SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法》本文主要介绍了SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法,具有一定的参考价值,感兴趣的可以了解一下... 目录方法1:更改IDE配置方法2:在Eclipse中清理项目方法3:使用Maven命令行在开发Sprin

JAVA SE包装类和泛型详细介绍及说明方法

《JAVASE包装类和泛型详细介绍及说明方法》:本文主要介绍JAVASE包装类和泛型的相关资料,包括基本数据类型与包装类的对应关系,以及装箱和拆箱的概念,并重点讲解了自动装箱和自动拆箱的机制,文... 目录1. 包装类1.1 基本数据类型和对应的包装类1.2 装箱和拆箱1.3 自动装箱和自动拆箱2. 泛型2

C# 委托中 Invoke/BeginInvoke/EndInvoke和DynamicInvoke 方法的区别和联系

《C#委托中Invoke/BeginInvoke/EndInvoke和DynamicInvoke方法的区别和联系》在C#中,委托(Delegate)提供了多种调用方式,包括Invoke、Begi... 目录前言一、 Invoke方法1. 定义2. 特点3. 示例代码二、 BeginInvoke 和 EndI