1. JDK8 HashMap 示意图

image.png

2. HashMap的构造方法

不带参的构造函数

public HashMap() {
// 加载因子等于默认的加载因子 0.75f
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

带参数构建hashmap
@param loadFactor是一个不小于等于0的float
@param initialCapacity需要初始化转换为不小于输入值的最小的2的幂次方值

public HashMap(int initialCapacity, float loadFactor) {
// 桶数组的大小小于0时抛异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
                                               
        // 如果桶数组的大小超过最大值，则简单的将桶容量修改为最大值2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        //这个意思是根据桶数组的大小求一个“极限值threshold”，当桶中的键值队个数超过这个大小就进行扩容
    //tableSizeFor方法求得的数字是刚超过initialCapacity的一个2的n次方的数，例如initialCapacity是1000，那么得到的threshold就是1024
        this.threshold = tableSizeFor(initialCapacity);
    }

initialCapacity的转换方法：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        // 本质上是将n最大位及以后的每一位都置为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;
}

3. HashMap的get方法

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 如果现在的table数组不为空 且 数组长度大于0 且 hash所在的数组元素不为null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 如果第一个元素就是 则返回第一个元素
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果当前桶的元素数量大于1则继续寻找
            if ((e = first.next) != null) {
                // 如果前桶里是一个红黑树 则调用红黑树的get方法
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 遍历链表
                do {
                    // 如果遇到key相等的，则返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

tips HashMap 的遍历

关于桶内的元素为红黑树时如何遍历元素：
其实hashmap在将桶内元素由链表转为红黑树时树节点类继承自链表节点类，所以红黑树仍然持有链表的next指针，当红黑树增删元素时也会去维护这个指针，所以最终的get方法只需要按照链表的方式即可遍历整个hashmap。

4. HashMap的put方法

先来看看 hashmap 是如何计算key的hash值：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果 key == null 
    返回0 
否则
    key的hashcode值 异或 key的hashcode值无符号右移16位

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key  key的hash值
     * @param key the key  key 值
     * @param value the value to put  value 值
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
*/
     
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为空，则进行必要的初始化工作
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果根据hash值确定的下标的table所对应的节点为空，则直接创建新节点并赋值到这个节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        // 处理hash碰撞
            Node<K,V> e; K k;
            // 如果发生碰撞的元素与当前节点的hash值 key值相等的话，用新值替换旧值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果当前table节点是红黑树的话，调用红黑树的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            // 循环这个链表
                for (int binCount = 0; ; ++binCount) {
                    // 当p遍历到当前链表的最后一个节点时，则新建一个Node赋值为p.next即可
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 当前节点序号值 >= 8+1 既当前链表总长度 >=9 时，将此链表转换为红黑树 
                        // (当前链表长度 = binCount + 1（bitCount从0开始遍历） + 1(新增加的元素))
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果当前元素与要新增的元素hash值 key值 分别相等，则break，在后面进行覆盖
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 即使更新p为下一个元素
                    p = e;
                }
            }
            // 如果需要值覆盖操作
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // 判断是否需要覆盖   如果不要覆盖那么老值为null时也会覆盖
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 回调 以允许 LinkedHashMap等后置操作
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 增加更改操作次数
        ++modCount;
        // 如果现有size大与临界值 触发扩容操作
        if (++size > threshold)
            resize();
        // 回调以允许LinkedHashMap后置操作
        afterNodeInsertion(evict);
        return null;
    }

5. HashMap的resize方法

// 定义数组的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

final Node<K,V>[] resize() {
        // 获取现有的table
        Node<K,V>[] oldTab = table;
        // 获取现有table的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 现有的扩容临界值
        int oldThr = threshold;
        // 定义新的数组长度和扩容临界值
        int newCap, newThr = 0;
        
        // 如果原来的table不为空
        if (oldCap > 0) {
            // 如果现有table数组的长度大于等于 1 << 30 = 2 ^ 30
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 设置扩容临界值为 2 ^ 31
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 否则进行扩容 数组长度扩大为原来的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        // 原来的table为空
        // threshold > 0  则已初始化过threshold 新数组长度=threshold
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 否则 新数组长度 = 16 新的threshold = 16 * 0.75 = 12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        // 如果新的threshold等于0
        if (newThr == 0) {
            // 设置新的threshold = 新的数组大小 * loadFactor
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 更新临界值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            // 新建一个Node数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 如果扩容之前的数组不为空那么需要调整红黑树或者链表的指向
        if (oldTab != null) {
            // 遍历旧table
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // 如果当前table节点不为空
                if ((e = oldTab[j]) != null) {
                    // 当亲节点赋值给e 老数组当前节点置为null
                    oldTab[j] = null;
                    // 如果当前节点的next为null既当前节点只有一个节点，则将当前元素赋值到新数组的对应下表
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 如果是红黑树，则调用红黑树调整方法
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 链表调整
                    else { // preserve order
                        // 链表调整 分别设置两个链表的头尾节点 
                        // 节点重新hash只有两种情况， 新的下标 = 老的下标 ｜ 新的下标 = 老的下标 + 老的数组长度
                        // 取决于新的hash计算后新增加的高位是否为0
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 循环当前链表
                        do {
                            next = e.next;
                            // 此元素的新下标等于老下标
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            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;
                        }
                    }
                }
            }
        }
        // 返回新的table
        return newTab;
    }