集合–HashMap

基于JDK 1.8 版本，会有与以前版本的比较

HashMap 使我们非常常用的一个存储 key value 的数据结构，是由数组和链表组合构成。在JDK 8 中对 HashMap 进行了优化引入了红黑树，哈希冲突的解决办法 —— 冲突链表法。

（这里借用帅丙几张图）

在我们执行 put 的方法时比如 put（ “帅丙”, 520 ），就是往这个数组中取填通过 HashMap 的 hash 方法对 key 进行计算得出下标，hash("帅丙")=2

hash函数 & 计算下标公式：

static final int hash(Object key) {
    int h;
    //hash函数返回的是 key 的 hashCode 与高十六位进行异或，又称二次扰动
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//下标计算公式
index = HashCode（Key） & （Length - 1）//等价于 HashCode（Key）% length

数组的长度是有限的，而且利用哈希算法计算下标也是会发生冲突的，上面介绍过解决冲突的办法是冲突链表法，当两个 key 的下标计算一样时就会发生冲突，这时我们会通过头插法（JDK1.8以前是这样的，JDK1.8改为尾插法）形成链表。

像这样每一个 key value 结构在 JDK 1.8 中叫做 Node（实现了 Map.Entry 接口），以前的版本叫做 Entry，结构源码如下：

Node结构

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

在JDK 1.8 中引入的红黑树巧妙的将时间复杂度从O(n)降到了O(logn)，在链表长度达到 8 时就会将链表转换成红黑树，结点从 Node 都转变为 TreeNode，如果链表长度降为 6 那么会转变回链表结构，7 的话就保持原状。这是根据泊松分布计算得出的，在负载因子为 0.75 的时候，单个 hash 槽内的个数为 8 的概率小于百万分之一，所以将 7 作为一个分水岭。

通过上面的介绍应该对 HashMap 有了个基本的认识，接下来介绍一些基本的知识点

为什么 HashMap 的容量都是 2 的幂次方

因为 2 的幂次方时，我们在求下标的时候进行减一处理后，二进制的表示都是 1 ，这样的话 index 的值就取决于 hashCode 的值，只要 hashCode 是均匀的那么 index 就是均匀，这就是为了实现均匀分布。

HashMap 扩容机制（resize）

Capacity：HashMap当前长度。
LoadFactor：负载因子，默认值0.75f。

HashMap 的初始大小是 16，负载因子为 0.75，源码中有一句话The next size value at which to resize (capacity * load factor).它是通过对比当前 map 中的 size 大小和容量 * 负载因子进行对比，如果大了就扩容。就比如说容量为 100，在我存入第 76 个时就会发生扩容。

扩容分为两步：

扩容创建一个新的 Entry 或者叫 Node 新数组，长度是原来的两倍
ReHash：遍历原 Entry 数组，并把所有 Entry 重新 Hash 一遍到新数组中

为什么要重新 Hash 呢？

因为我们上面已经讲过了下标的算法，index = hash(key) & length -1，这里也是经过优化的在数组长度为 2 的指数时，hash(key) % length 对长度取模结果和 & 运算一样，但是位运算的效率更高这也是为了性能考虑。在这里我们可以看到数组扩容了那么长度也会发生改变，这时我们就需要重新 hash 存到数组中。

为什么以前使用头插法后来改为了尾插法，目的是什么？

头插法原本是作者考虑热点数据的，他认为后来的可能用到的概率更大。但是后来发现会出现死循环的问题，在多个线程下进行 resize 时，当线程调节完后可能就会形成一个环形链表。而尾插法的话在扩容完后还会元素原本的顺序，就不会出现成环的情况了。

那既然解决了多线程下的死循环，那是不是JDK8的HashMap就能用在多线程的环境下了呢？

源码中看到方法中都没有进行同步，那么可能造成的现象就是，无法保证读取的值我们下一秒操作时还是原来的值。或者上一秒 put 的值，下一秒我们 get 时还是原值，所以线程安全还是无法保证。

为什么 hash 函数计算 hash 值的时候要无符号右移 16 位再异或？

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

还是上面的那段代码这里有好多种解释，其中有种解释是这样的因为我们平常的 map 长度也不会超过 2 的十六次方即 65536 这么长，那么计算下标时只会和低十六位进行 & 运算，这样高位就很少进入运算。其实总的方向就是为了使全部的 hash 值参与运算使 hash 分布的更平均。

为什么下标 index 计算要取模运算？

如果直接把上面 hash 函数计算后的值当做下标，范围为 -2147483648到2147483648 ，大约 40 亿空间。确实如果映射均匀很难碰撞但是，这么大的范围是没办法存入内存中的所以采用了 hash % length 这种格式，即 hash & length -1

HashMap 在 put 时是如何计算下标和判断对象是同一对象？

在计算下标时首先判断对象是不是 null，如果是 null 则 hashCode 为 0 ，如果不是则正常计算。判断同一对象首先判断他们的 hash 值是否相同，如果相同则再调用 equals 方法判断是否真正相同。

拿 HashMap 举例，为什么重写 equals 时还得重写 hashCode 方法？

比如说 hashMap，我们是通过 hash 函数计算出 index 去寻找对象的位置，但是如果像上面说的可能会冲突后在后边形成链表，那么这时该如何区分对象。equals！这时就该我们大 equals 出场来判断了，如果你不吧这两个方法一块重写的话，遇见这种情况就没有办法找到真正的对象了。