从put()分析HashMap

数据结构：数组+链表。Node<K,V>[] table。（源码参考put()方法），允许null键/值。

数组+链表有什么优点：

若是数组，数组缺点：需要连续内存空间；删除需要移动其他元素位置
若是链表，链表缺点：查找复杂度高。
时间复杂度：O(1)。常量时间（假设能正确分散）。

一、如何确定key的数组索引位置，为什么？

1、得到混合key.hashCode()高低位的hash值。

static final int hash(Object key) {
    int h;
    // 将key的hashCode与其hashCode无符号右移(低位丢弃高位补零)16位进行异或运算(XOR运算同0异1)。
    // 实际上是把key的hashCode的低16位和高16位做XOR运算
    // int类型，4字节，32位
    // 混合高位和低位，可以增加低位的随机性，减少碰撞。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // key==null，hash为0，所以key可以为null。
}

2、在数组table（桶）中的索引下标为：index =hash & (n-1)，n为桶长度，n为2的幂。

n为2的幂，n-1用二进制表示，低位以连续1表示（如00001111），hash & (n-1)结果范围为 [0,1]，取决于hash的低位。

当hash与(n-1)做位与&运算时，hash只会有低位参与运算（取决于n-1尾端1的位数量），这也是计算hash时key的hashCode的低16位和高16位做XOR运算的原因，能增加低位的随机性。

用位与&运算，比传统的取模%操作效率更高；索引值不会超过数组长度；

二、为什么容量capacity必须为2的幂？

体现在根据key分配到哪个桶中。跟计算索引位置index = hash & (n-1)相关。

当n为2的幂，hash&(n-1)结果范围为 [0,1]，取决于hash的低位。保证位运算和取余的结果相等，但效率更高。

能减少哈希碰撞，避免不同hash值被分配到同一位置，在计算key的哈希值，hash = key.hashCode()) ^ (h >>> 16，高16位与低16位异或运算，减少冲突。

三、默认容量多少？若指定时不为2的幂呢？

默认初始容量：16（1<<4），负载因子：0.75f。

若指定initialCapacity时，不为2^n，hashMap的tableSizeFor()处理后能保证容量总为2的幂。

static final int MAXIMUM_CAPACITY = 1 << 30;
static final int tableSizeFor(int cap) {
    // cap=17,n=16
    // n转换成二进制00010000
    int n = cap - 1;
    n |= n >>> 1; // n=00010000|00001000=00011000
    n |= n >>> 2; // n=00011000|00000110=00011110
    n |= n >>> 4; // n=00011110|00000001=00011111
    n |= n >>> 8; // n=00011111|00000000=00011111
    n |= n >>> 16;// n=00011111|00000000=00011111  n=31
    // 返回n+1=32，2的5次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

四、put()源码

put方法：

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//static final int TREEIFY_THRESHOLD = 8;
//transient Node<K,V>[] table;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K, V>[] tab;// 存放链表头结点的链表数组
    Node<K, V> p;// 某一节点
    int n;// 数组 tab 的长度
    int i;// 数组 tab 的下标值
    // 1.当table为null或空时，resize()方法，初始化一个默认16的tab
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 位与运算计算出插入点在数组的下标，结果范围在[0,n-1]，
    // 2.如果tab中此下标位置为null，放入此节点，节点的next指向null
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 3.table中此下标位置已有节点，发生碰撞
    else {
        Node<K, V> e;// 暂时存放键值对的节点
        K k;// 暂时存放key
        // 3.1判断跟数组头结点是否是同一个key。这里没有使用key对象直接比较，而是hash相同，且通过==或equals比较也相等
        // 因为数组下标碰撞，hash可能不同，&&具有短路功能，可以不用每次直接比较key对象
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;// 与头结点p的key重复，将头结点p赋给e，用于更换value值
        // 3.2判断p是否是TreeNode的实例。一个bucket中大于8个节点时，会转成红黑树存储
        else if (p instanceof TreeNode)
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        // 3.3数组下标碰撞后，与此bucket中头结点key不重复，且此时此bucket中节点数<8
        else {
            // 循环此bucket中节点，直到找到插入位置跳出循环
            for (int binCount = 0; ; ++binCount) {
                // 3.3.1找到链表末尾节点，链到其后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //当此节点为第8个元素时，转红黑树存储
                        treeifyBin(tab, hash);
                    break;
                }
                // 3.3.2若遇到相同key，break
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 3.4.桶中存在相同key
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)// onlyIfAbsent默认为false
                e.value = value;// 替换value
            afterNodeAccess(e);// LinkedHashMap 继承 HashMap, 此方法在 LinkedHashMap 中被重写。在这里没什么用，但是在 LinkedHashMap 中此处调用此方法将节点链接到有序链表的最后.
            return oldValue; //存在相同key时，返回原value
        }
    }
    // 4.判断是否扩容
    ++modCount;
    // 插入新节点后，若size（hashMap中key-value数量） > 阈值，(capacity * load factor)时，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);// 此方法在 LinkedHashMap 中被重写
    return null;
}

五、hashMap什么时候扩容？

1、put方法步骤1，如果初始化后第一次添加元素，进行resize。hashMap初始化时，并没有对table进行赋值。resize()方法中才有Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

2、put方法步骤4，加入新key/value后，若hashMap中key-value数量大于阈值，即hashMap.size > threshold时，进行扩容。

/**
 * Returns the number of key-value mappings in this map.
 *
 * @return the number of key-value mappings in this map
 */
public int size() {
    return size;
}

3、put方法步骤3.3.1，treeifyBin()转成红黑树中

1
2
3

//MIN_TREEIFY_CAPACITY = 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//64
    resize();

六、关于负载因子及阈值threshold？

负载因子loadFactor的默认值是0.75。

阈值threshold取决于loadFactor。实例化hashMap时，若指定HashMap.table的长度（initialCapacity），此时将tableSizeFor(initialCapacity)赋值给threshold（在resize时threshold用于新table长度，threshold会重新计算得出）。

在扩容resize()方法中，不管table是否被创建，threshold=oldCap*loadFactor。table长度若未指定，默认为16。loadFactor若未指定，默认为0.75f。

threshold针对的是hashMap中key-value的数量，HashMap.size，并非table.size。

七、扩容resize()源码

扩容核心 (e.hash & oldCap)，=0时索引没变，!=0时原索引+oldCap

//int threshold;
//static final int MAXIMUM_CAPACITY = 1 << 30;
//static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//static final float DEFAULT_LOAD_FACTOR = 0.75f;
//final float loadFactor;
//transient Node<K,V>[] table; 
//static final int UNTREEIFY_THRESHOLD = 6;
final Node<K,V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //第一部分：计算 新数组长度newCap,新阈值newThr（保证newCap<2^30）
    // 1.如果oldTab中已经有元素，oldTab!=null
    if (oldCap > 0) {
        // 1.1 如果达到最大容量2^30，不再扩容，阈值设置为整数最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 1.2 数组长度直接扩容2倍。阈值扩容2倍的条件是(newCap<2^30，且原数组长度>=16）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 2.oldTab=null或没有元素，但有oldThr>0：表示实例化HashMap时调用带参构造方法，构造方法中将capacity赋值给了threshold（this.threshold = tableSizeFor(initialCapacity);）
    // 则newCap=原阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 3.oldTab=null或没有元素，且原阈值oldThr=0：表示实例化HashMap时调用无参默认构造方法，则newCap为默认容量16，newThr阈值为16*0.75 = 12
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 4.如果新阈值=0（可能是1.2步骤或2步骤判断为false造成），根据newCap重新计算新阈值
    if (newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                (int) ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // 第二部分：新数组
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍历原数组每个bucket
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 1.如果该bucket只有一个节点，直接hash & (n - 1)计算新索引
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 2.如果原来的这个节点已经转换成红黑树。split()方法也是根据e.hash & oldCap计算新索引。若同一索引节点数<=6，则untreeify不使用红黑树，若>6，则转换成红黑树。
                else if (e instanceof TreeNode)
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                // 3.哈希冲突，bucket链表的情况。
                /**扩容核心 (e.hash & oldCap)，=0时索引没变，!=0时原索引+oldCap**/
                    // 若oldCap=16(00010000），则newCap=32。此处二进制位只展示低8bit
                    // oldCap-1=00001111，newCap-1=00011111（容量翻倍，而容量又为2的幂，即新容量下的n-1相当于oldCap-1向高位移动1位且低位补1）
                    // 则新旧索引的关键点在于：newCap-1二进制中1的最高位bit处，对应的hash二进制bit是 0还是 1 。此bit的位置刚好是oldCap二进制中1的最高位bit位置。（此bit位置假设称为关键bit位置）
                    // 若e.hash关键bit处为0，则索引没变；否则，新索引=原索引+oldCap

                    // 已知e.hash & 00001111为原索引
                    // 若是e.hash & 00010000 = 0
                    // 则  e.hash & 00011111（新索引），与原索引结果相同

                    // 总结：因为oldCap为2的幂，oldCap的二进制高位总为1（如00010000)，
                    // 若(e.hash & oldCap) == 0，说明e.hash关键bit处则为0（0&1=0），此时索引不变
                    // 若(e.hash & oldCap) != 0，说明e.hash关键bit处则为1（1&1=1），此时相对于原索引，增加了关键bit处为1低位为0的长度（即oldCap)
                else { // preserve order
                    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);
                    // 此处没有在bucket链表各节点的循环中，因为新索引要么是原索引位置，要么是原索引+oldCap位置，只可能在这两处，则直接放入头结点
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

八、扩容时HashMap如何确定index？

JDK7中是每次都int i = indexFor(e.hash, newCapacity)重新计算。

JDK8进行了优化，不需要每次都重新计算。若原数组某索引处只有一个节点时，直接hash & (newCap - 1)计算新索引。

若多于一个节点（即原索引处发生哈希冲突），新索引位置hash & (newCap - 1)的结果只会有两种。通过节点的hash值与原数组长度位与运算的结果来判断，e.hash & oldCap，=0时索引没变，否则原索引+oldCap。