[转]《Effective Java》中推荐的hashCode算法

标签: | 发表时间:2015-10-29 01:02 | 作者:lihui6636
出处:http://blog.csdn.net/lihui6636

http://blog.csdn.net/error_case/article/details/46503103


Google首席Java架构师Joshua Bloch在他的著作《Effective Java》中提出了一种简单通用的hashCode算法:

1. 初始化一个整形变量,为此变量赋予一个非零的常数值,比如int result = 17;
2. 选取equals方法中用于比较的所有域,然后针对每个域的属性进行计算:
  (1) 如果是boolean值,则计算f ? 1:0
  (2) 如果是byte\char\short\int,则计算(int)f
  (3) 如果是long值,则计算(int)(f ^ (f >>> 32))
  (4) 如果是float值,则计算Float.floatToIntBits(f)
  (5) 如果是double值,则计算Double.doubleToLongBits(f),然后返回的结果是long,再用规则(3)去处理long,得到int
  (6) 如果是对象应用,如果equals方法中采取递归调用的比较方式,那么hashCode中同样采取递归调用hashCode的方式。否则需要为这个域计算一个范式,比如当这个域的值为null的时候,那么hashCode 值为0
  (7) 如果是数组,没必要自己去重新遍历一遍数组,java.util.Arrays.hashCode方法包含了8种基本类型数组和引用数组的hashCode计算,算法同上,
  java.util.Arrays.hashCode(long[])的具体实现:
[java]  view plain copy
  1. public static int hashCode(long a[]) {   
  2.         if (a == null)   
  3.             return 0;   
  4.     
  5.         int result = 1;   
  6.         for (long element : a) {   
  7.             int elementHash = (int)(element ^ (element >>> 32));   
  8.             result = 31 * result + elementHash;   
  9.         }   
  10.     
  11.         return result;   
  12. }   

Arrays.hashCode(...)只会计算一维数组元素的hashCOde,如果是多维数组,那么需要递归进行hashCode的计算,那么就需要使用Arrays.deepHashCode(Object[])方法。

3. 最后,要如同上面的代码,把每个域的散列码合并到result当中:result = 31 * result + elementHash;
4. 测试,hashCode方法是否符合文章开头说的基本原则,这些基本原则虽然不能保证性能,但是可以保证不出错。

这个算法存在这么几个问题需要探讨:
1. 为什么初始值要使用非0的整数?这个的目的主要是为了减少hash冲突,考虑这么个场景,如果初始值为0,并且计算hash值的前几个域hash值计算都为0,那么这几个域就会被忽略掉,但是初始值不为0,这些域就不会被忽略掉,示例代码:
[java]  view plain copy
  1. import java.io.Serializable;   
  2.  public class Test implements Serializable {   
  3.     
  4.     private static final long serialVersionUID = 1L;   
  5.     
  6.     private final int[] array;   
  7.     
  8.     public Test(int... a) {   
  9.         array = a;   
  10.     }   
  11.     
  12.     @Override  
  13.     public int hashCode() {   
  14.         int result = 0; //注意,此处初始值为0         
  15.        for (int element : array) {   
  16.             result = 31 * result + element;   
  17.         }   
  18.         return result;   
  19.     }   
  20.     
  21.     public static void main(String[] args) {   
  22.         Test t = new Test(0, 0, 0, 0);   
  23.         Test t2 = new Test(0, 0, 0);   
  24.         System.out.println(t.hashCode());   
  25.         System.out.println(t2.hashCode());   
  26.     }   
  27.     
  28. }   

如果hashCode中result的初始值为0,那么对象t和对象t2的hashCode值都会为0,尽管这两个对象不同。但如果result的值为17,那么计算hashCode的时候就不会忽略这些为0的值,最后的结果t1是15699857,t2是506447

2.为什么每次需要使用乘法去操作result? 主要是为了使散列值依赖于域的顺序,还是上面的那个例子,Test t = new Test(1, 0)跟Test t2 = new Test(0, 1), t和t2的最终hashCode返回值是不一样的。

3. 为什么是31?31是个神奇的数字,因为任何数n * 31就可以被JVM优化为 (n << 5) -n,移位和减法的操作效率要比乘法的操作效率高的多。

例子:

 
import java.util.Arrays;
import java.util.List;
import java.util.Map;


public class HashTest {

	 int intVar;
	 long longVar;
	 boolean booleanVar;
	 float floatVar;
	 double doubleVar;
	 byte byteVar;
	 String stringVar;
	 Object objectVar;
	 A aVar;
	 List<A> listVar;
	 Map<String, A> mapVar;
	 long[] longArrayVar;
	 A[] aArrayVar;
	 HashTest hashTestVar;
	 HashTest[] hashTestArrayVar;
	 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((aVar == null) ? 0 : aVar.hashCode());
		result = prime * result + (booleanVar ? 1231 : 1237);
		result = prime * result + byteVar;
		long temp;
		temp = Double.doubleToLongBits(doubleVar);
		result = prime * result + (int) (temp ^ (temp >>> 32));
		result = prime * result + Float.floatToIntBits(floatVar);
		result = prime * result + Arrays.hashCode(hashTestArrayVar);
		result = prime * result
				+ ((hashTestVar == null) ? 0 : hashTestVar.hashCode());
		result = prime * result + intVar;
		result = prime * result + ((listVar == null) ? 0 : listVar.hashCode());
		result = prime * result + Arrays.hashCode(longArrayVar);
		result = prime * result + (int) (longVar ^ (longVar >>> 32));
		result = prime * result + ((mapVar == null) ? 0 : mapVar.hashCode());
		result = prime * result
				+ ((objectVar == null) ? 0 : objectVar.hashCode());
		result = prime * result + Arrays.hashCode(aArrayVar);
		result = prime * result
				+ ((stringVar == null) ? 0 : stringVar.hashCode());
		return result;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		HashTest other = (HashTest) obj;
		if (aVar == null) {
			if (other.aVar != null)
				return false;
		} else if (!aVar.equals(other.aVar))
			return false;
		if (booleanVar != other.booleanVar)
			return false;
		if (byteVar != other.byteVar)
			return false;
		if (Double.doubleToLongBits(doubleVar) != Double
				.doubleToLongBits(other.doubleVar))
			return false;
		if (Float.floatToIntBits(floatVar) != Float
				.floatToIntBits(other.floatVar))
			return false;
		if (!Arrays.equals(hashTestArrayVar, other.hashTestArrayVar))
			return false;
		if (hashTestVar == null) {
			if (other.hashTestVar != null)
				return false;
		} else if (!hashTestVar.equals(other.hashTestVar))
			return false;
		if (intVar != other.intVar)
			return false;
		if (listVar == null) {
			if (other.listVar != null)
				return false;
		} else if (!listVar.equals(other.listVar))
			return false;
		if (!Arrays.equals(longArrayVar, other.longArrayVar))
			return false;
		if (longVar != other.longVar)
			return false;
		if (mapVar == null) {
			if (other.mapVar != null)
				return false;
		} else if (!mapVar.equals(other.mapVar))
			return false;
		if (objectVar == null) {
			if (other.objectVar != null)
				return false;
		} else if (!objectVar.equals(other.objectVar))
			return false;
		if (!Arrays.equals(aArrayVar, other.aArrayVar))
			return false;
		if (stringVar == null) {
			if (other.stringVar != null)
				return false;
		} else if (!stringVar.equals(other.stringVar))
			return false;
		return true;
	}
		 
}


class A{
	
	int a;
	long b;
	String c;
	
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + a;
		result = prime * result + (int) (b ^ (b >>> 32));
		result = prime * result + ((c == null) ? 0 : c.hashCode());
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		A other = (A) obj;
		if (a != other.a)
			return false;
		if (b != other.b)
			return false;
		if (c == null) {
			if (other.c != null)
				return false;
		} else if (!c.equals(other.c))
			return false;
		return true;
	}
	
	
}


作者:lihui6636 发表于2015/10/28 17:02:37 原文链接
阅读:197 评论:1 查看评论

相关 [effective java hashcode] 推荐:

[转]《Effective Java》中推荐的hashCode算法

- - 荒岛码农
Google首席Java架构师Joshua Bloch在他的著作《Effective Java》中提出了一种简单通用的hashCode算法:. 初始化一个整形变量,为此变量赋予一个非零的常数值,比如int result = 17;. 选取equals方法中用于比较的所有域,然后针对每个域的属性进行计算:.

java中的hashcode作用

- - 编程语言 - ITeye博客
根据API文档,java中的hashcode事实上是跟equals是有着密切联系的,hashcode是为了提高哈希表的性能. public int hashCode()返回该对象的哈希码值. 支持此方法是为了提高哈希表(例如 java.util.Hashtable 提供的哈希表)的性能. 说明是一个本地方法,它的实现是根据本地机器相关的.

【转】java中hashcode()和equals()的详解

- - 互联网 - ITeye博客
首先equals()和hashcode()这两个方法都是从object类中继承过来的. equals()方法在object类中定义如下: . 很明显是对两个对象的地址值进行的比较(即比较引用是否相同). 但是我们必需清楚,当String 、Math、还有Integer、Double. 等这些封装类在使用equals()方法时,已经覆盖了object类的equals()方法.

如何正确实现 Java 中的 HashCode

- - ImportNew
相等 和 Hash Code. 从一般角度来看,Equality 是不错的,但是 hash code 更则具技巧性. 如果我们在 hash code上多下点功夫,我们就能了解到 hash code 就是用在细微处去提升性能的. 大部分的数据结构使用equals去检查是否他们包含一个元素. 这个变量 contains 是true.

深入解析Java对象的hashCode和hashCode在HashMap的底层数据结构的应用

- - 编程语言 - ITeye博客
对比对象实例的内存地址(也即对象实例的ID),来判断是否是同一对象实例;又可以说是判断对象实例是否物理相等;. 对比两个对象实例是否相等. 当对象所属的类没有重写根类Object的equals()方法时,equals()判断的是对象实例的ID(内存地址),是否是同一对象实例;该方法就是使用的等号(==)的判断结果.

关于hashcode与equal函数

- - 编程语言 - ITeye博客
hashcode:独一无二地代表了一个对象,并且通过hashcode可以找到这个对象. 在java.lang.Object的规范中,对hasCode有如下的约定:.  1 在一个应用程序执行期间,如果一个对象的equals方法做比较所用到的信息没有被修改的话,那么对该对象调用多次hashCode方法,它必须返回相同的整数.

从相似度算法谈起 - Effective similarity search in PostgreSQL

- - 云栖社区-精彩推荐
标签 PostgreSQL , 数组 , 相似度 背景 相似度分析是一个非常普遍的需求,例如根据用户提供的线索,从一堆文本数据、图片数据、视频数据中筛选一段与用户的描述相近的. 我之前写过一系列的文章来介绍,文本、图片相似度搜索的技术和使用场景. 《PostgreSQL 在视频、图片去重,图像搜.

为什么要重写equles和hashcode

- - 编程语言 - ITeye博客
  经过网上查阅资料得出如下结论.                      大家知道,Java中的集合(Collection)有两类,一类是List,再有一类是Set. 前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复. 那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢.

hashCode equal避免的几个误区

- - ITeye博客
对于hashcode方法和equals方法,我们需要注意以下几点:. 1.equals方法所需要的几个特性.    ?什么情况下进行equals的比较. 答案是用equals比较的只是值本身,对于equals方法,读者需要记住按照两种情况来运用,一比较基本类型的值的比较,二比较的是对象. equals比较的只是值或者对象的内容.

hashCode()方法的性能优化

- - 并发编程网 - ifeve.com
原文链接, 译文链接,原文作者: Robert Nystrom,译者:有孚. 本文主要讨论下不同的hashCode()的实现对应用程序的性能影响. hashCode()方法的主要目的就是使得一个对象能够成为hashMap的key或者存储到hashset中. 这种情况下对象还得实现equals(Object)方法,它的实现和hashCode()必须是一致的:.