HashMap源码阅读

2019-08-23 本文已影响0人 jumper996

1. 什么是HashMap？

image.png

1.1 map的定义

首先你要知道什么是map，map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射。

1.2 Map的特点

1.没有重复的 key（一方面，key用set保存，所以key必须是唯一，无序的；另一方面，map的取值基本上是通过key来获取value，如果有两个相同的key，计算机将不知道到底获取哪个对应值；这时候有可能会问，那为什么我编程时候可以用put（）方法传入两个key值相同的键值对？那是因为源码中，传入key值相同的键值对，将作为覆盖处理）

2.每个 key 只能对应一个 value, 多个 key 可以对应一个 value（这就是映射的概念，最经典的例子就是射箭，一排射手，一排箭靶，一个射手只能射中一个箭靶，而每个箭靶可能被不同射手射中。这里每个射手只有一根箭，不存在三箭齐发还都中靶这种骚操作。将射手和射中的靶子连线，这根线加射手加靶子就是一个映射）

3.key,value 都可以是任何引用类型（包括 null）的数据（只能是引用类型）

1.3 HashMap

HashMap在JDK1.8中是基于（数组+链表）+红黑树的一个Map容器

2. HashMap解读

2.1 静态属性（默认值）

   /**
     *  如果没有给容量初始化值得话，就用这个作为初始化值，16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * Map容量最大值
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     *  负载因子，用来判断扩容量的
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 当Node的长度达到8的时候就转换成红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 当Node的长度被remove到6的时候就从红黑树转成链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

   /**
    * 容器可以树化的最小容量。
    *（否则，如果bin中的节点太多，则会调整表的大小。）
    * 应至少为4 * TREEIFY_THRESHOLD，以避免调整
    * 大小和树化阈值之间的冲突。
    */
    static final int MIN_TREEIFY_CAPACITY = 64;

2.2 HashMap实例的属性

    /**
     * HashMap底层数据结构是一个Node数组，可以是红黑树树，也可以是链表，默认是链表
     */
    transient Node<K,V>[] table;

    /**
     * Map中存储元素的数量
     */
    transient int size;

    /**
     * 要调整大小的下一个大小值（容量*加载因子）
     * 此外，如果尚未分配表数组，则此字段保存初始数组容量
     * put一个元素进Map的时候，都会判断添加后的size和这个
     * threshold比较，如果大于了这个值，就扩容。
     */
    int threshold;

    /**
     * 哈希表的加载因子
     * 这个就是为了计算出threshold的，下面会说
     */
    final float loadFactor;

2.3 HashMap初始化

HashMap总共定义了四个构造函数。

2.3.1 // 传入初始化容量，和负载因子进行初始化

    // 传入初始化容量，和负载因子
    public HashMap(int initialCapacity, float loadFactor) {
        // 如果初始化容量小于0，则抛出异常。
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 如果大于最大的容量，就设置成最大容量。
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 如果负载因子小于0，或者不是个数字则，抛出异常。
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // 这里进行第一次计算初始化容量
        this.threshold = tableSizeFor(initialCapacity);
    }

刚刚上面看到了第一次计算容量用的是tableSizeFor(); 这个方法，我们现在来看一下这个方法。

   /**
     * 返回的大小一定是2的幂
     * 意思就是，你传的初始化容量大小，取比这个数最大的2的n次方的值
     * 打比方：
     * 传1那么容量就是2的0次方，那么容量就是1
     * 传入的是2那么就是2的1次方，那么容量就是2
     * 传入的是3那么就是2的2次方，那么容量就是4
     * 传入的是4那么就是2的3次方，那么容量就是8 
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

2.3.2 传一个初始化容量大小初始化

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

2.3.3 默认构造函数

 public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

2.3.4 传一个Map进行初始化

刚刚介绍的三种构造函数可以看出来，都没有给HashMap进行初始化，但是这个构造函数，会给出初始化。

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
// 将传入的Map的值都添加进目前初始化的HashMap
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
            // 传入的Map大小
            int s = m.size();
            if (s > 0) {
                    if (table == null) { 
                        // 如果table是空的就计算容量，容量大小就是 (size/loadFactor) + 1.0F
                        float ft = ((float)s / loadFactor) + 1.0F;
                        int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                        // 如果容量大于了扩容标准，就计算新的扩容的标准大小。
                        if (t > threshold)
                              threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                // 如果size大于了扩容标准，调用进行resize()扩容
                resize();
            // 循环put进去
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 新增元素的方法
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

从上面可以看到主要是两个方法，resize(); 扩容方法，和putVal(); put一个元素到容器的方法，我们继续来看看putVal();方法
JDK1.7是通过hash%cap得出存储数据位置，就是hash值模上数组length得出位置
JDK1.8是通过容量大小与key值进行hash的算法在开始的时候只会对低位进行计算，虽然容量的2进制高位一开始都是0，但是key的2进制高位通常是有值的，因此先在hash方法中将key的hashCode右移16位在与自身异或，使得高位也可以参与hash，更大程度上减少了碰撞率。先是jdk1.8的图解