java的HashCode方法

    1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。
    2. 如果两个对象根据equals(Object o)方法是相等的，调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。
    3. 如果两个对象根据equals(Object o)方法是不相等的，调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，可以提高散列表的性能。
    有一个概念要牢记，两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象。

    所以hashcode相等只能保证两个对象在一个HASH表里的同一条HASH链上，继而通过equals方法才能确定是不是同一对象，如果结果为true, 则认为是同一对象不在插入，否则认为是不同对象继续插入。

    有许多人学了很长时间的Java，但一直不明白hashCode方法的作用， 我来解释一下吧。首先，想要明白hashCode的作用，你必须要先知道Java中的集合。

    总的来说，Java中的集合（Collection）有两类，一类是List，再有一类是Set。 你知道它们的区别吗？前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。

    那么这里就有一个比较严重的问题了：要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？

    这就是Object.equals方法了。但是，如果每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。 也就是说，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。
  
   于是，Java采用了哈希表的原理。哈希（Hash）实际上是个人名，由于他提出一哈希算法的概念，所以就以他的名字命名了。
哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。如果详细讲解哈希算法，那需要更多的文章篇幅，我在这里就不介绍了。

   初学者可以这样理解，hashCode方法实际上返回的就是对象存储的物理地址（实际可能并不是）。 这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。 如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了， 就调用它的equals方法与新元素进行比较，相同的话就覆写，不相同就存储，所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。 

  所以，Java对于eqauls方法和hashCode方法是这样规定的：
1、如果两个对象相同，那么它们的hashCode值一定要相同；
2、如果两个对象的hashCode相同，它们并不一定相同

    上面说的对象相同指的是用eqauls方法比较。 你当然可以不按要求去做了，但你会发现，相同的对象可以出现在Set集合中。同时，增加新元素的效率会大大下降。hashcode这个方法用来快速查找定位对象，在维护HashMap的key值唯一或HashSet不允许重复值时被用来检索。
HashMap的put方法:
   

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

   那你会说，不是还有equals这个方法吗？ 不错，这2个方法都是用来判断2个对象是否相等的。但是他们是有区别的。 一般来讲，equals这个方法是给用户调用的，如果你想判断2个对象是否相等，你可以重写equals方法，然后在代码中调用，就可以判断他们是否相等了。简单来讲，equals方法主要是用来判断从表面上看或者从内容上看，2个对象是不是相等。

    举个例子，有个学生类，属性只有姓名和性别，那么我们可以认为只要姓名和性别相等，那么就说这2个对象是相等的。 hashcode方法一般用户不会去调用，比如在hashmap中，由于key是不可以重复的，他在判断key是不是重复的时候就判断了hashcode这个方法，而且也用到了equals方法。这里不可以重复是说equals和hashcode只要有一个不等就可以了！

    所以简单来讲，hashcode相当于是一个对象的编码，就好像文件中的md5，他和equals不同就在于它返回的是int型的，比较起来不直观。我们一般在覆盖equals的同时也要覆盖hashcode，让他们的逻辑一致。举个例子，还是刚刚的例子，如果姓名和性别相等就算2个对象相等的话，那么 hashcode的方法也要返回姓名的hashcode值加上性别的hashcode值，这样从逻辑上，他们就一致了。要从物理上判断2个对象是否相等，用==就可以了。

    为什么HashCode对于对象是如此的重要?
    hashcode这个方法在维护HashMap的key值唯一或HashSet不允许重复值时是用来鉴定2个对象是否相等的。对其他大多数类而言。
    一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的Hash算法相比还不能叫真正的算法,但如何实现它,不仅仅是程序员的编程水平问题,而是关系到你的对象在存取时性能的非常重要的问题.有可能,不同的HashCode可能会使你的对象存取产生,成百上千倍的性能差别.

    我们先来看一下,在JAVA中两个重要的数据结构:HashMap和Hashtable,虽然它们有很大的区别,如继承关系不同,对value的约束条件(是否允许null)不同,以及线程安全性等有着特定的区别,但从实现原理上来说,它们是一致的.所以,我们只以Hashtable来说明:
在java中,存取数据的性能,一般来说当然是首推数组,但是在数据量稍大的容器选择中,Hashtable将有比数据性能更高的查询速度.具体原因看下面的内容.

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

    index = (o.hashCode() & 0x7FFFFFFF)%hs.length;
    这个对象就会直接放在Hashtable的第index位置,对于写入,这和数组一样,把一个对象放在其中的第index位置,但如果是查询,经过同样的算法,Hashtable可以直接从第index取得这个对象,而数组却要做循环比较.所以对于数据量稍大时,Hashtable的查询比数据具有更高的性能.

    既然可以根据HashCode直接定位对象在Hashtable中的位置,那么为什么Hashtable要用key来做映射呢(为了一些思维有障碍的人能看到懂我加了一句话:而不是直接放value呢)?这就是关系Hashtable性能问题的最重要的问题:Hash冲突.

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

    所以对于索引相同的对象,在该index位置存放了多个对象,这些值要想能正确区分,就要依靠key本身和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() + Attribute2.HashCode()...[+super.HashCode()],

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


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

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

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