漫谈hashcode

概要

对于hashcode,相信很多朋友都不陌生,应为我们很多时候都需要用到这个,比如hashMap中就用到了,根据key的hash值来决定value存放的位置,之后来取得时候直接到指定的位置上那就行了,速度非常的快。今天我们就来看一下,hashcode在Java几个比较重要的类中具体是怎么用的?

什么是hashcode

要了解什么是hashcode,就得先了解什么哈希?

我们看下百度百科是怎么说的?

漫谈hashcode

说白了,哈希就是一个函数,这个函数的实现可以说成是一种算法,通过这个算法我们得到一个值,就是hash值,这个值放哪儿呢?就得说另外一个东东,哈希表,hash值其实就是哈希表中的位置。

哈希算法有很多种的实现,比较常见的像 直接取模,平方取中等。

在Java中,每个对象都有hashcode,因为他们都继承于Object这个父类,它提供了一个native的返回对象哈希码值的方法,返回的是对象引用中存储的对象的内存地址(经过哈希之后在哈希表中的位置),并且有如下规定:

  1.在 Java 应用程序执行期间,在对同一对象多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另              一次执行,该整数无需保持一致。
  2.如果根据 equals(Object) 方法,两个对象是相等的,那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
  3.如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么对这两个对象中的任一对象上调用 hashCode 方法不 要求一定生成不同的整数结果。但是,程序员应该意识到,为不相等的对象生成不同整数结            果可以提高哈希表的性能。

第2点可以看出,如果重写了equals方法,那就需要重写hashcode方法,进而保证相等的对象得到的哈希值是一样的。这个还是很重要的,不然后面集合就没办法玩了。

第3点可以看出,两个对象不相等,但是哈希值却可能相等,这就是哈希碰撞。减少哈希碰撞,我们就要去不断的优化哈希算法,使得不同的对象通过它得到的hashcode是不一样的,也就是在哈希表中分布的比较均匀,而不是几种在某一块区域,这样产生碰撞的可能性就非常大。

下面我们就来看一下,Java几个比较重要的类是怎么来处理的?

String中的hashcode为什么使用31

string中的hashcode方法实现看起来很简单,代码如下:

    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;
}

这个方法是被重写了的,因为string中的equals方法也是被重写了的。按照上面那个for循环,稍微推到下,就可以得出,最后得到的哈希值是这样计算的:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

这里面在计算的时候使用了31这个数,为什么呢?成千上万的数中,为什么偏偏就选中了它呢?真的只是因为多看了一眼?

当然不是,这个还是有根据的,首先,31是一个不大不小的指数,这个不大不小有什么好处呢?好处就在于它既可以保证散列的区间足够,又可以保证数据不会溢出丢失。另外一个,31*i这个通过数学手段的推导,可以得到这样一个结果:31*i=(i << 5) - i,这里面使用了位运算和减法来代替乘法,提高了性能。

hashmap中的hashcode

下面我们再来看一下hashcode在hashmap中的应用,我们先来看下jdk1.8中hashmap的hash方法:

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

这个方法有几个亮点:

1.如果key为空,则返回0

2.如果key不等于空,计算key的哈希值

3.将第二步里面计算得到的值无符号右移16位,高位补0

4.将第二步和第三步得到的结果进行异或运算(两个值相同则为0,相反则为1)

这里面前面两个步骤都比较好理解,按照正常情况,这时候就可以反回了啊,为什么还要进行后面的步骤呢?我们先来看下hashmap的put方法:

 if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
。。。。。。。以下省略。。。。。。

这里我们只要看上面标红的一行就行了,简单的说,你在向hashmap中存放元素的时候,这个元素放在哪边,就是这行代码决定的。我看下这行代码:就是用上面个hash方法返回的数和数组的长度减一之后做与运算,这里可能小伙伴又有疑问了啊,为啥子要进行与运算呢?这个跟我们将String类里面为什么使用31有异曲同工之妙,具体的推导过程我这边就不卖弄了,其实还是为了提升速度,这边这种其实就是最开始我们讲的直接取模 的哈希算法,只不过换了个样子,其实当 lenth = 2n 时,X % length = X & (length - 1),注意这里面的前提条件是不能丢的,少了就不对了,同学们是不是又突然想起来什么呢?

     /**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

看一下hashmap中对默认容量的定义中有这么一句话,必须是2的次方,说到底,就是为了去配合上面那个公式,成就一个完美的哈希算法。知道了后面的这个步骤,我们再来看上面那个无符号右移16位的问题。

假设存在这么一种情况:

对象 A 的 hashCode 为 1000010001110001000001111000000,对象 B 的 hashCode 为 0111011100111000101000010100000,数组的长度是16,运用上面那个公式计算的时候发现得到的结果都是0,冲突了,这是不行的,但是如果我们将hashcode右移16位,在进行异或运算,其实对于高位而言,是没有什么影响的,但是地位就会被打乱,其实真正参与的还是地位的数字,这样的得到的结果就会好很多,这样的设计是不是很厉害,既考虑到了效率,有能解决冲突的问题。

上一篇:gitlab和Django实现push自动更新


下一篇:js new关键字