HashMap源码阅读

HashMap源码分析

一、HashMap的存储结构

​ HashMap是用哈希表实现的，解决冲突的方法是拉链法。具体说来，JDK1.7及以前HashMap是通过数组+链表的方式实现，每个数组单元指向一个链表，链表里存放一系列key的hashCode相同的数据。

​ JDK1.8后采用数组+链表+红黑树实现，为了防止链表过长导致查询效率太低，当链表达到一定长度时(默认8)，将链表转化为红黑树，使查询复杂度从O(n)降低到O(logn)；红黑树的查询速率快但维护代价比较高，所以当红黑树节点数减少到一定值时(默认是6)，将红黑树再转化为链表。

​ 以JDK1.8为例分析。

二、HashMap常用的字段属性

// <--预定义好的常量-->
// 数组的初始化容量，必须是2的n次幂，这里是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 数组的最大容量，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 装载因子，与扩容相关
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表长度的阈值，>=时链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 红黑树节点阈值，减少到6时转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转化为红黑树，除了链表长度达到阈值，还必须要求数组容量必须达到64
// 主要时为了避免，数组扩容与树化阈值的冲突---？？？
static final int MIN_TREEIFY_CAPACITY = 64;

// <--HashMap类重要字段-->
// 存放Node节点的数组
transient Node<K,V>[] table;
// 存放所有的键值对
transient Set<Map.Entry<K,V>> entrySet;
// map中的实际键值对个数，即map中元素个数
transient int size;
// 每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
// 当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;
// 数组扩容阈值,值应该为数组容量*装载因子，当map中的元素个数大于该阈值，会通过resize扩容
int threshold;
// 装载因子
final float loadFactor;

/*
 * 链表节点类定义
 **/
static class Node<K,V> implements Map.Entry<K,V> {
        // key的hash值，put和get时用它来定位数组中的位置
        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;
        }
    }

/*
 * 红黑树节点类定义
 **/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

三、HashMap的构造函数

// 无参构造函数，设置装载因子为默认值0.75
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

// 带有初始容量的构造函数，会调用带初始容量和装载因子的构造函数，注意数组实际容量并不一定是initialCapacity
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

// 带初始容量和装载因子的构造函数，这里需要注意initialCapacity的处理
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 初始化容量大于MAXIMUM_CAPACITY时，指定为MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 装载因子不合法，抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 初始化类loadFactor字段
        this.loadFactor = loadFactor;

        // 初始化容量并不一定就是table数组的长度，实际中table数组长度(tableSizeFor方法返回)是一个
        // 1. 大于等于初始化容量
        // 2. 是2的幂次方
        // 3. 满足1，2最小的正整数
        // 这里数组长度初始化给了threhold字段
        this.threshold = tableSizeFor(initialCapacity);
    }

/**
 * 这个方法返回的就是大于等于当前传入值的最小的一个2的n次幂的值。
 * 实现思路大概如下(00100->00100, 00110->01000)：
 *     1.先减1: 00100->00011(恰好是2的幂), 00110->00101(一般情况)
 *  2. n|= n>>1,2,... 会将有效位全部置为1： 00011->00011, 00101->00111
 *  3.加1： 00011->00100, 00111->01000
 * cap=0时，方法会返回1
*/ 
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;
    }

// 带Map的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

// 将Map中元素复制到当前Map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        // s是待复制Map中的元素个数
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size   设置数组的长度
                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)   // ？？？
                resize();
            // 此时table为null但容量设置好了，或者是table不为null，容量已扩容
            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);
            }
        }
    }

四、put方法详解

/**
 * 1. 通过hash方法得到当前key的一个hash值，用于定位数组位置
 * 2. 调用putVal方法将键值对放入map
 */
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

/**
 * 函数入参分别为：
 *    key的hash值，
 *    键值对<K, V>，
 *    onlyIfAbsent，如果为true，不能修改已存在的值，这里传入false
 *    evict没什么效果
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 判断table是否为空，如果为空，先调用resize进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 根据当前key的hash值找到数组中的下标，判断当前位置是否已经存在元素
        // 如果没有元素，将当前key，value包装成Node节点，添加到此位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {    // 当前位置已经存在元素
            Node<K,V> e; K k;
            // 1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等--首个元素冲突
            // 则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 2.如果当前是红黑树结构，则把它加入到红黑树--交给红黑树添加方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
            // --在链表中插入
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 链表到达末尾，插入新节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 插入后链表长度>=8，转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 在链表中找到了相同的key,跳出循环，到①
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // ①
            // 此时有两种情况
            // 1. 发生了碰撞，e代表旧值，因此节点value需要覆盖
            // 2. 如果插入链表或者红黑树的新节点，此时e为空
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // fail-fast机制
        ++modCount;
        // 如果当前数组中的元素个数超过阈值，则扩容
        if (++size > threshold)
            resize();
        // 同样的空实现
        afterNodeInsertion(evict);
        return null;
    }

四、hash的计算原理

​ 这里，会先判断key是否为空，若为空则返回0。这也说明了hashMap是支持key传 null 的。若非空，则先计算key的hashCode值，赋值给h，然后把h右移16位，并与原来的h进行异或处理。这里实际上做了一个将低16位的值更新为低16位与高16位异或的结果，这样低16位会同时包含高16位的信息。

/**
 * hash的计算原理
 *
 *
 */
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

为什么将hashCode值要进行这样的操作呢？

​ 答案是可以降低碰撞的概率。

​ 在putVal方法中，根据key的hash值寻找数组中的下标是通过(n-1) & hash得到的。这里的n代表数组的长度，保证是2的n次方。此时，hash % n与(n-1) & hash的结果相同。我们可以这样认为，hash值映射到数组中的下标是hash值中的低位决定的，这样映射时丢失了hash值中的高位信息，容易发生碰撞。而异或运算可以让结果的随机性更大，所以没有使用与或者或。

五、resize()扩容机制

​ 在put方法中，当table数组为空时，会调用resize()方法进行扩容；当map的size大于阈值(threshold)时，也会进行扩容。

/**
 * 初始化或者翻倍table的长度
 *     如果为null, 则根据字段阈值中保留的初始容量目标进行分配。
 *    否则，因为采用二次幂扩展，所以每个桶中元素保持在统一索引，或者在新表中按二次幂偏移
*/
final Node<K,V>[] resize() {
        // 记录旧数组
        Node<K,V>[] oldTab = table;
        // 旧数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 旧数组扩容阈值
        int oldThr = threshold;
        // 新数组长度和扩容阈值
        int newCap, newThr = 0;
        // 1. 当旧数组的长度大于0时，说明之前已经通过resize扩容过
        if (oldCap > 0) {
            // 旧数组长度已经达到最大值，无法扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 数组尝试扩容到之前两倍，数组长度和扩容阈值都变成原来两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        // 2. 这里旧数组长度oldCap<=0,并且旧的扩充阈值oldThr>0,此时是map初始化时，还未调用过resize的
        // 情况，此时的oldThr，是通过tableSizeFor得到的一个值。---
        // 因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2
        // 的n次幂。---
        // 所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值
        // （2的n次幂)--
        // 但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，
        // 这个会在③处理。
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，
        // 于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，
        //因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12），并把它赋值给 threshold
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）
        threshold = newThr;
        // 生成扩容之后的table
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 将原来数组中的元素移动到新数组
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // 取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 1.如果当前元素的下一个元素为空，则说明此处只有一个元素
                    // 则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表--
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并
                    // 判断当前位置的链表是否需要移动到新的位置
                    else { // preserve order
                        // loHead 和 loTail 分别代表链表旧位置的头尾节点
                        Node<K,V> loHead = null, loTail = null;
                        // hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 如果当前元素的hash值和oldCap做与运算为0，则原位置不变
                            // 因为在扩容后的数组中新的映射值(n-1)&hash相同****
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 此时映射值(n-1)&hash会发生变化，节点需要移动到新位置***
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //原位置不变的一条链表，数组下标不变
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //移动到新位置的一条链表，数组下标为原下标加上旧数组的容量
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

​ resize函数中，将旧的元素<k,v>移到扩充后的新数组中时，根据元素key的hash值的第log(oldCap)位的不同有两种情况（）：

​ 当该位是0时，hash&(newCap-1) = hash&(oldCap-1) ，下标值不变；

​ 当改为是1时，hash&(newCap-1) = hash&(oldCap-1) + oldCap，下标值会发生变化。

六、get()方法

​ get()方法比较简单，

/**
* 如果节点为空，则返回null，否则返回节点的value。这也说明，hashMap是支持value为null的。
* 因此，我们就明白了，为什么hashMap支持Key和value都为null
*/
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

/**
* 
*/
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // table不为空，且根据hash值计算出来的数组下标不为空，就开始寻找
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 第一个元素hash值和key都相同，返回第一个元素
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 第一个元素不是，继续寻找
            if ((e = first.next) != null) {
                // 是红黑树的话，用getTreeNode()方法进行寻找
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 是链表的话，遍历寻找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

七、常见问题

1. 为什么HashMap链表会形成死循环

​ 准确的讲应该是 JDK1.7 的 HashMap 链表会有死循环的可能，因为JDK1.7是采用的头插法，在多线程环境下有可能会使链表形成环状，从而导致死循环。JDK1.8做了改进，用的是尾插法，不会产生死循环。

2. HashMap与HashTable的比较

   HashTable使用 synchronized 来进行同步

   HashMap 可以插入键为 null 的 Node

   HashMap 的迭代器是 fail-fast 迭代器

   HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的