Java面试题之HashMap 的 hash 方法原理是什么

HashMap 的 hash 方法原理是什么

在了解HashMap的原理之前, 我们先看看hash散列表是怎么工作的, 他的原理是什么。

散列表的原理是将关键字通过散列函数映射到固定的位置上, 并对原始值进行处理, 最终得到的值就是我们所说的哈希值, 即在HashMap中所表现出来的值。在JDK1.7之前，HashMap的内部实现方式是数组 + 链表，数组的下标就是哈希值，而链表则是解决哈希冲突的方案。而在JDK1.8之后，由于链表会引起频繁的GC，会对性能有影响，而添加了红黑树的设计，对冲突的解决更加高效。

比如在HashMap中，我们put一个新的键值对时，便会对新的key生成一个哈希值(hashCode)，这个hashCode将会指导他在数组中的大致位置， 但有可能会存在相同的hashCode(即hash冲突)，因此会通过拉链法(或者是红黑树)来使链表在当前位置上依次挂起来，这样既能保证查询时的O(1)速度，又能避免产生很多碰撞。

具体来说，当我们使用HashMap的put方法时，HashMap首先会对key进行hash计算，得到一个hash值。然后，HashMap会将这个hash值用来决定key-value存放在数组中的位置。

hash方法的实现原理

接下来是讲解hash方法的实现原理，hash方法是用来计算hashCode的，接下来是hash方法的代码实现：

static final int hash(Object key) {
    int h;
    // key.hashCode()计算出key的哈希值h
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在上面的实现中， 首先对键值调用key.hashCode()方法，确定键值的哈希值h。hashCode()的具体实现可以看做是从对象的物理地址、时间等因素来生成唯一标识。

在key为null的情况下，哈希值设为0。
为什么要进行以下位运算呢，在进行哈希值计算的时候借助到了以下位运算:

h ^ (h >>> 16)

这里是采用了hash分流算法, 具体步骤如下:

• 按照hashcode和右移16的结果做异或，生成新的哈希值
• 将新的哈希值除以容量size的余数，得到下标index
• 如果当前下标没有hash冲突，则直接将其放入slots[index]中；
• 如果当前下标有hash冲突，则将当前的键值对添加到当前下标对应的链表的最后；

然而hash散列并不是完美的算法, 在极端情况下可能出现hash冲突，即不同的两个key所对应的hash值是相同的，这就需要采取一些特殊处理的策略，例如拉链法或者是一些替代性的算法，这些算法都有其优劣性。对于比较简单的key值集合来说，HashMap可以将一个键值的HashCode直接映射为一个下标，这种情况下性能最好。

下面再举个栗子: 我们以五个关键字生成的hashCode为例，说一下在HashMap中如何定位分组的过程。

String s1= "name";
String s2 = "gender";
String s3 = "age";
String s4 = "addr";
String s5 = "phone";
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
System.out.println(s3.hashCode());
System.out.println(s4.hashCode());
System.out.println(s5.hashCode());

//分别输出如下, 
//名字(hashCode)： 3373707
//性别(hashCode)： 1967188755
//年龄（hashCode）：95458899
//地址(hashCode)： 3009914
//电话(hashCode)： 3081039

所以, 当存储出现哈希冲突，我们可以通过维护链表的方式解决。例如, 有两个键值对[key1, value1]和[key2, value2]，他们都对应了相同的哈希值h。那么，HashMap就将其存储在[h]位置的链表的尾部。这样，查询哈希表中任一键值对时，HashMap首先对该键值计算哈希值，然后找到[h]位置并遍历链表，在链表中找到一个哈希值和要查询的键值的哈希值相同的键值对。 haMap的hash方法原理和hash算法通过详细的讲解，我们已经能够对HashMap有了较全面的认识。