图片.png

HashMap由数组+链表+红黑树组成的。

• HashMap的主体是一个数组。

数组的每个元素可能只是一个Node节点。
也可能是由Node节点串起来的链表（该数组位置产生冲突且链表节点数没有超过8时）。
也可能是红黑树（该数组位置产生冲突且链表节点数超过8时）。

• 链表和红黑树则是主要为了解决哈希冲突而存在的。

如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组位置包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，通过key对象的equals方法逐一比对查找是否存在，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

刚说了，hashMap中的链表出现越少，性能才会越好。那只要散列够均匀，那么链表出现就会越少或者链表长度越短。
所以问题来了，

怎么样才能保证散列到数组位置够均匀呢？

在java中是将对象的HashCode的高16位，和原HashCode作异或运算；

(h = key.hashCode()) ^ (h >>> 16)

然后与(length-1)作且运算。

i = (length - 1) & hash]

这两步是怎么让散列更均匀的呢？

先来看第一步。我们做一个简单演练

图片.png
将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算，可以将高低位二进制特征混合起来。
从上文可知高区的16位与原hashcode相比没有发生变化，低区的16位发生了变化。
我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？
我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算，计算公式：(length - 1) & hash，假如这时数组槽位有16个，则槽位计算如下：
图片.png
仔细观察上图不难发现，高区的16位很有可能会被数组槽位数的二进制码锁屏蔽，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征。
也许你可能会说，即使丢失了高区特征不同hashcode也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现。

再来看第二步。
在讲第二步之前，我们需要知道，length必须是2的幂次。就是因为length是2的幂次导致散列更均匀。为什么length是2的幂次可以导致散列更均匀呢？看下图

图片.png

经过第一步之后，假设得到两个hash，分别是010101和010111，如果此时length-1是111101，那么它们的索引都是010101，换算成十进制就是21，这样就产生冲突了，散列就没那么均匀。但是如果length-1是111111，那对应就是21和23，散列到不同位置，更均匀。
同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。

所以最终存储位置的确定流程是这样的：

图片.png

这个流程会产生冲突的地方在于length - 1) & hash这一步。

两个拥有不一样hashcode的对象，hashcode和自身高16位进行异或运算后不可能一样。

图片.png
hashcode右移16位后，高16位必定是0。根据异或运算规律，运算结果高16位取决于hashcode的高16位。运算结果低16位取决于hashcode的低16位。所以不一样hashcode，和自身高16位进行异或运算后不可能一样。
虽然两个对象的不同hashcode和自身高16位经过异或运算后，结果也是必定不一样的。但是在第二步(length - 1) & hash计算数组下标时有可能一样。

重写equals方法需同时重写hashCode方法的原因

最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题

package com.travelsky.trp.usercenter.userprofile.controller;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: wenbaipei
 * @Date: 2020/1/10 11:47
 * @Version 1.0
 */
public class Student {
    int number ;
    String name;

    public int getNumber() {
        return number;
    }

    public String getName() {
        return name;
    }

    public Student(int number, String name) {
        this.number = number;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        Student student = (Student)obj;
        if(this.number == ((Student) obj).getNumber() && this.name.equals(student.getName())){
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        Map<Student,String> map = new HashMap<>();
        Student wbp = new Student(1,"温佰培");
        System.out.println(wbp.hashCode());
        map.put(wbp,"放进去第一个温佰培");
        Student wbpCopy = new Student(1,"温佰培");
        System.out.println(wbpCopy.hashCode());
        map.put(wbpCopy,"放进去第二个逻辑上相等的温佰培");
        System.out.println(map.get(wbp));
        System.out.println(map.get(wbpCopy));
    }
}

结果

图片.png

分析：
equals()方法是用来判断逻辑相等还是物理相等，取决于你是否重写equals()方法。但是无论你是哪种相等，map中不允许key重复。
上述两个Student对象，值都一样，被认为是逻辑相等。但是没有重写hashcode方法，被散列到两个不同的数组下标。
或者被散列到同一个数组下标，但是也会因为判断其entry的hash值是否相等，不相等则会用链表链起来了。
外人就会看起来像hashmap能有相同的key。
所以为保证key的唯一性，必须重写hashcode方法。

put操作和get操作中要作e.hash == hash的思考

e.hash==hash和(k = e.key) == key是一样的效果，去掉其一似乎
可以看看如果拿掉e.hash==hash的话会有什么效果呢？

假设这时候来了一个hash值不同但是通过定位index到这个桶的位置的节点，因为hash值不同，那当然k==key也就不同了，那么因为连接条件是||，这个标志意味着还需要接下来判断key.euqals(k)，
但是！如果有e.hash==hash呢？
那也就是说，此时hash值不同的点直接被过滤了，不用进行接下来的equals判断了，这就很省时间和资源了

hashcode究竟是个啥？

hashCode的计算方法是通过和当前线程有关的一个随机数+三个确定值，运用Marsaglia's xorshift scheme随机数算法得到的一个随机数。和对象内存地址无关。

杂录

散列到数组哪个位置用到了hashcode，判断两个对象是否相等用到了equals()和hash
n取2的幂次方，在数值上等于取模运算。即a % (2^n) 等价于 a & (2^n - 1) 。