hashcode()和hash()

1 为什么有hashcode()方法

equals()和hashcode()这两个方法都是从object类中继承过来的.

hashcode() 方法，在object类中定义如下：

public native int hashCode();

native说明是一个本地方法，它的实现是根据本地机器相关的。当然我们可以在自己写的类中覆盖hashcode()方法，比如String、Integer、Double。。。。等等这些类都是覆盖了hashcode()方法的
例如String类中:就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。(为什么取31?主要是因为31是一个奇质数，所以31i=32i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多).

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

Integer类的:

public static int hashCode(int value) {
        return value;
 }

Double类的

public static int hashCode(double value) {
        long bits = doubleToLongBits(value);
        return (int)(bits ^ (bits >>> 32));
 }

hashCode对于List集合、数组而言，他就是一个累赘,但是对HashMap、HashSet、HashTable而言，它变得异常重要.hashCode是用来在散列存储结构中确定对象的存储地址的.
考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在）也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值
2 hashCode与equals
如果x.equals(y)返回“true”，那么x和y的hashCode()必须相等。
如果x.equals(y)返回“false”，那么x和y的hashCode()有可能相等，也有可能不等。
3 HashMap中的hash()
hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置.
key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么要这么干呢？ 这个与HashMap中table下标的计算有关。

n = table.length;
index = （n-1） & hash;

当 length 总是 2 的倍数时，h & (length-1)将是一个非常巧妙的设计：
假设 h=5,length=16, 那么 h & length - 1 将得到 5；
如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……
如果 h=15,length=16, 那么 h & length - 1 将得到 15；
但是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了；
当 h=17 时 , length=16 时，那么 h & length - 1 将得到 1 了……
这样保证计算得到的索引值总是位于 table 数组的索引之内。

a.jpg

HashMap的初始大小和扩容都是以2的次方来进行的，换句话说length-1换成二进制永远是全部为1，比如容量为16，则length-1为1111，大家知道位运算的规则是两个1才得1，遇0的0，也就是说length-1中的某一位为1，则对应位置的计算结果才取决于h中的对应位置（h中对应位取0,对应位结果为0，h对应位取1，对应位结果为1。这样就有两个结果），但是如果length-1中某一位为0，则不论h中对应位的数字为几，对应位结果都是0，这样就让两个h取到同一个结果，这就是hash冲突了，恰恰length-1又是全部为1的数，所以结果自然就将hash冲突最小化了
总之:
1.length（2的整数次幂）的特殊性导致了length-1的特殊性（二进制全为1）
2.位运算快于十进制运算，hashmap扩容也是按位扩容

3 HashTable中的hash()

int hash  = key == null ? 0 : key.hashCode() & 0x7FFFFFFF;
int index = hash % table.length;

4 ConcurrentHashMap中的hash()

// 用于和负数hash值进行 & 运算，将其转化为正数（绝对值不相等），Hashtable中定位hash桶也有使用这种方式来进行负数转正数
 static final int HASH_BITS = 0x7fffffff;
 int hash = spread(key.hashCode());
 int index = (n - 1) & hash;
 static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
  }