23-集合(下)

1. Map 概述

• Map 与 Collection 并列存在，用于保存具有映射关系的数据：key-value
• Map 中的 key 和 value 都可以是任何引用类型的数据 // 常用 String 作为 Map 的“键”
• Map 中的 key 用 Set 来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode() 和 equals()
• key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value
• Map<I> 的常用实现类：HashMap、TreeMap、LinkedHashMap 和 Properties。其中，HashMap 是 Map 接口使用频率最高的实现类
  
  • HashMap 线程不安全，效率高；可以存储 null 值的 key 和 value；JDK 7实现方式是 {数组 + 链表}，JDK 8实现方式是 {数组 + 链表 + 红黑树}
  • LinkedHashMap 是通过 {双向链表} 和 {散列表} 这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是 {双向链表}，并非指 {用链表法解决散列冲突}
  • TreeMap 保证按照添加的 key-value 进行排序（按 key 排序），实现有序遍历；底层使用 {红黑树}
  • Hashtable 作为古老的实现类；线程安全，效率低；不能存储 null 值的 key 和 value
  • Properties 常用来处理配置文件；key 和 value 都是 String 类型
• key-value 的特点
  
  • key：无序的，不可重复的，使用 Set 存储所有的 key
  • value：无序的，可重复的，使用 Collection 存储所有的 value
  • Entry<key, value>：一个 key-value 构成了一个 Entry 对象

2. HashMap

2.1 概述

• HashMap 是 Map<I> 使用频率最高的实现类
• 允许使用 null键 和 null值，与 HashSet 一样，不保证映射的顺序
• 所有的 key 构成的集合是 Set：无序的、不可重复的。所以，key 所在的类要重写：equals() 和 hashCode()
• 所有的 value 构成的集合是 Collection：无序的、可以重复的。所以，value 所在的类 要重写：equals()
• 一个 key-value 构成 一个entry，所有的 entry 构成的集合是Set：无序的、不可重复的
• HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true， hashCode 值也相等
• HashMap 判断两个 value 相等的标准是：两个 value 通过 equals() 方法返回 true

2.2 源码

2.2.1 JDK 7

public class HashMap<K,V> extends AbstractMap<K,V> 
                implements Map<K,V>, Cloneable, Serializable {

    // The default initial capacity - MUST be a power of two.
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    // The load factor used when none specified in constructor.
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    transient Entry<K,V>[] table;

    // The number of key-value mappings contained in this map.
    transient int size;

    // The next size value at which to resize (capacity * load factor).
    int threshold;

    final float loadFactor;

    // Constructs an empty HashMap with the default initial capacity (16)
    // and the default load factor (0.75).
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    // Constructs an empty HashMap with the specified initial capacity
    // and the default load factor (0.75).
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity!
        int capacity = 1;
        while (capacity < initialCapacity) capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        return h & (length-1); // A % B = A & (B-1) 除留取余
    }

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            // 每次都扩原size的2倍
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        // Creates new entry.
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    }

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash); // 原数组数据传输到新数组上
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    // Transfers all entries from current table to newTable.
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity); // 计算节点在新hashTab中的索引
                e.next = newTable[i]; // 新来的节点都往链表头插，原首节点作为新节点的next
                newTable[i] = e;
                e = next; // go on
            }
        }
    }
}

2.2.2 JDK 8

public class HashMap<K,V> extends AbstractMap<K,V>
                implements Map<K,V>, Cloneable, Serializable {
    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始大小 16

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final int TREEIFY_THRESHOLD = 8;
    
    static final int UNTREEIFY_THRESHOLD = 6;

    static final int MIN_TREEIFY_CAPACITY = 64;

    // 桶里元素 <= 6
    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;
        }
    }

    // 桶里元素 >= 8
    // 不仅是一棵红黑树，同时还维护这一个双向链表!
    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);
        }
    }

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

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

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

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

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) { // binCount 记录这条链表上有多少个节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash); // 树化
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    // 扩容！
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        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
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = 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
                        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        TreeNode<K,V> b = this;
        // Relink into lo and hi lists, preserving order
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            else {
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }

        if (loHead != null) {
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else {
                tab[index] = loHead;
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        if (hiHead != null) {
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
}

2.3 源码分析

2.3.1 HashMap 的常量

• DEFAULT_INITIAL_CAPACITY：HashMap 的默认容量，16
• MAXIMUM_CAPACITY：HashMap 的最大支持容量，2^30
• DEFAULT_LOAD_FACTOR：HashMap 的默认加载因子
• TREEIFY_THRESHOLD：Bucket 中链表长度大于该默认值 8，转化为红黑树
• UNTREEIFY_THRESHOLD：Bucket 中红黑树存储的 Node 小于该默认值 6，转化为链表
• MIN_TREEIFY_CAPACITY：桶中的 Node 被树化时最小的 hash 表容量 64（当桶中 Node 的数量大到需要变红黑树时，若 hash 表容量小于 MIN_TREEIFY_CAPACITY 时，此时应执行 resize 扩容操作这个 MIN_TREEIFY_CAPACITY 的值至少是 TREEIFY_THRESHOLD 的 4 倍）
• table：存储元素的数组，总是 2 的 n 次幂 // 原因见《散列表(中)-课后思考》
• entrySet：存储具体元素的集
• size：HashMap 中存储的键值对的数量
• modCount：HashMap 扩容和结构改变的次数
• threshold：扩容的临界值，= 容量 * 填充因子
• loadFactor：填充因子

2.3.2 table 的长度

负载因子值的大小，对 HashMap 有什么影响？

• 负载因子的大小决定了 HashMap 的数据密度。
• 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长，造成查询或插入时的比较次数增多，性能会下降。
• 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性 能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
• 按照其他语言的参考及研究经验(泊松分布)，会考虑将负载因子设置为 0.7~0.75，此时平均检索长度接近于常数。

2.3.2 JDK 7 原理简述

HashMap map = new HashMap() 在实例化以后，底层创建了长度是 16 的一维数组 Entry[] table。

什么时候发生扩容？

// 肯定是放元素的时候发现要扩容的！
public V put(K key, V value) {
    if (key == null) return putForNullKey(value);

    // 找要放的角标位
    int hash = hash(key);
    int i = indexFor(hash, table.length);

    // 数组i位置已经有元素了
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 再根据 equals 判断是不是相同 key
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;

    // 数组i位置是null或者通过equals判断不等，说明还是新元素，插入
    addEntry(hash, key, value, i); // 添加新kv的时候，可能会扩容
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 达到阈值 && 产生hash冲突
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 每次都扩原size的2倍！
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

当 HashMap 中的元素越来越多的时候，hash 冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对 HashMap 底层的数组进行扩容，而在 HashMap 底层的数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置（拢共就俩位置），并放进去，这就是 resize() 要做的事。

如何扩容？

// resize(2 * table.length);
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash); // 原数组数据传输到新数组上
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// Transfers all entries from current table to newTable.
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) { // 遍历数组
        while(null != e) { // 遍历桶中单链表
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 计算节点在新数组中的索引（原位置或原位置+原长度）
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i]; // 头插法
            newTable[i] = e;
            e = next;  // 多线程，可能成环！！！
        }
    }
}

环演示：

2.3.3 JDK 8 原理简述

JDK8 相较于 JDK7 在底层实现方面的不同： new HashMap() 的时候底层没有创建一个长度为 16 的数组（首次调用 put() 时，底层才创建那个长度为 16 的数组）。

JDK7 底层结构只有：数组+链表。JDK8 底层结构：数组+单链表+红黑树（双向链表）

什么时候扩容？

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 根据 hash 得到对应数组下标的元素
    if ((p = tab[i = (n - 1) & hash]) == null) // 元素为空，直接添加
        tab[i] = newNode(hash, key, value, null);
    else { // 如果元素不为空
        Node<K,V> e; K k;
        // hash 冲突的情况
        // 1. equals 一样吗
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 相同就覆盖
        else if (p instanceof TreeNode) // 2. 不相同，元素是红黑树里的节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 3. 不相同，元素是单链表中的节点
            for (int binCount = 0; ; ++binCount) { // binCount 记录这条链表上有多少个节点
              if ((e = p.next) == null) { // 使用 “尾插法” 插入元素
                p.next = newNode(hash, key, value, null);
                // 为啥是 8? 泊松分布，一个桶里能装 8 个元素的概率为 0.00000006！
                if (binCount >= TREEIFY_THRESHOLD - 1)
                  treeifyBin(tab, hash); // 树化
                break;
              }
              if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                  break;
              p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;

    // 插入操作完成后，判断是否达到阈值，达到直接扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

// ================================
class Node {
    hash, key, value, next
}

class TreeNode extends Node {
    parent, red, left, right, prev
}
// ================================

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 头节点，tl 上一个节点
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);

        // 双向链表整完，就该树化了~
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

怎么扩容？

如果对应角标的桶里是单向链表，将单链表进行数据迁移。

如果对应角标的桶里是红黑树，将双向链表进行数据迁移（额外的双链表结构就是为数据迁移考虑的）。

注意哈！扩容不是简单的把链表头节点放到新位置，一整个链就跟着过去就完了。你得算每个元素的 hash 值重新放（当然这个重新放也就俩位置，不是原位置，就是原位置+原长度）

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    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
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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) {

        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = 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
                    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; // 尾插法~
                            // lowTail
                            loTail = e; // 更新单链表尾元素
                        } else { // 新位置 = 原位置 + 原长度
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            // highTail
                            hiTail = e;
                        }
                    } while ((e = next) != null);

                    // 链表挂到low桶上
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 链表挂到high桶上
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

// ================================
class Node {
    hash, key, value, next
}

class TreeNode extends Node {
    parent, red, left, right, prev
}
// ================================

// 红黑树的数据迁移（依靠底层的双向链表！）
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) { // 原桶
            // === ↓ 重新构建原桶中的双向链表 ↓ ===
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e; // lowTail 指向最新的尾元素
            // === ↑ 重新构建原桶中的双向链表 ↑ ===
            ++lc; // lowCount，计算桶中元素个数
        }
        else { // 新桶（原位置 + 原tab长度）
            // === ↓ 构建新桶中的双向链表 ↓ ===
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e; // highTail 指向最新的尾元素
            // === ↑ 构建新桶中的双向链表 ↑ ===
            ++hc; // highCount 同理
        }
    }

    if (loHead != null) { // 旧桶
        if (lc <= UNTREEIFY_THRESHOLD) // 不够 6 个，树转单链表
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab); // 重构红黑树
        }
    }
    if (hiHead != null) { // 新桶，同理
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

还有一个问题就是 6 和 8 的选择？6 和 8 之间有一个 7 可以有效防止链表和红黑树频繁转换。假设一下如果设计成 HashMap 中数据超过 8，由链表转换成红黑树。HashMap 中数据少于 8，有红黑树转换成链表。若一个 HashMap 不停的插入，删除。HashMap 中的个数不停的在 8 左右徘徊，就会频繁发生链表转红黑树，红黑树转链表，效率会非常低。

关于 hash 函数 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) 的设计：

• 首先 hashcode 本身是个 32 位整型值，在系统中，这个值对于不同的对象必须保证唯一（JAVA 规范），这也是大家常说的，重写 equals() 必须重写 hashcode() 的重要原因
• 获取对象的 hashcode 以后，先进行移位运算，然后再和自己做异或运算，即：hashcode ^ (hashcode >>> 16)，这一步甚是巧妙，是将「高16位」异或「低16位」，这样计算出来的「低16位」将“具有”高位和低位的性质。
• 最后，用 hash 表当前的容量减去一，再和刚刚计算出来的整型值做位与运算。进行位与运算，很好理解，是为了计算出数组中的位置。但这里有个问题：为什么要用容量减去 1？
  • 因为 A % B = A & (B - 1)，所以，p = tab[i = ((tab = resize()).length - 1) & hash]，可以看出这里本质上是使用了「除留余数法」。这个 & 操作只能用到 hashCode 的低16位
  • 综上，可以看出，hashcode 的随机性，加上移位异或算法，得到一个非常随机的 hash值，再通过「除留余数法」，得到 index。

网上看到过这句话：“当删除元素后，桶中元素个数<=6，会转成单链表结构” 这是错的！UNTREEIFY_THRESHOLD 这个值只在 resize 方法迁移完数据后用到，remove 方法中根本没用到这个值！

2.4 LinkedHashMap

• LinkedHashMap 是 HashMap 的子类
• 在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
• 与 LinkedHashSet 类似，LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致

因为我们的散列表是通过链表法解决散列冲突的，所以每个 Entry 会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将 Entry 串在「双向链表」中，hnext 指针是为了将结点串在「散列表的拉链」中。

JDK 8

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    transient LinkedHashMap.Entry<K,V> head;
    
    transient LinkedHashMap.Entry<K,V> tail;

    final boolean accessOrder;

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
}

2.5 常用方法

public void test() {
    Map map = new HashMap();
    map.put("1001", "白世珠");
    map.put("1002", "金敏喜");
    map.put("1003", "刘心悠");

    // 遍历所有key。但要注意！keySet 既不是 HashSet，也不
    // 是 TreeSet，而是实现了 Set<I> 的某个其他类的对象
    Set set = map.keySet();
    Iterator it = set.iterator();
    while(it.hasNext())
        System.out.println(it.next());

    // 遍历所有 value
    Collection c = map.values();
    for(Object o : c)
        System.out.println(o);

    // 遍历 key - value
    Set entrySet = map.entrySet();
    Iterator iterator = entrySet.iterator();
    while(iterator.hasNext()) {
        Map.Entry entry = (Map.Entry)iterator.next();
        System.out.println(entry.getKey() + "-" + entry.getValue());
    }

    // 遍历 key : value
    Set keySet = map.keySet();
    Iterator i = keySet.iterator();
    while(i.hasNext()) {
        Object key = i.next();
        Object value = map.get(key);
        System.out.println(key + ":" + value);
    }
}

3. TreeMap

• TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序
• TreeMap 可以保证所有的 Key-Value 对处于有序状态
• TreeSet 底层使用红黑树结构存储数据
• TreeMap 的 Key 的排序
  • 自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClassCastException
  • 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable<I>
• TreeMap 判断两个 key 相等的标准：两个 key 通过 compareTo() 或者 compare() 返回 0

4. Hashtable

• Hashtable 是个古老的 Map 实现类，JDK1.0 就提供了。不同于 HashMap， Hashtable 是线程安全的
• Hashtable 实现原理和 HashMap 相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用
• 与 HashMap 不同，Hashtable 不允许使用 null 作为 key 和 value
• 与 HashMap 一样，Hashtable 也不能保证其中 Key-Value 对的顺序
• Hashtable 判断两个 key 相等、两个 value 相等的标准，与 HashMap 一致

5. Properties

• Properties 类是 Hashtable 的子类，该对象用于处理属性文件
• 由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型
• 存取数据时，建议使用 setProperty(String key, String value) 和 getProperty(String key)

public void test() {
    FileInputStream fis = null;
    try {
        Properties prop = new Properties();
        fis = new FileInputStream("jdbc.properties");
        prop.load(fis);
        System.out.println(prop.getProperty("name"));
        System.out.println(prop.getProperty("password"));
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        if(fis != null) {
            try {
                fis.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

读取项目下的 jdbc.properties 文件下的内容，抛了 FileNotFoundException，而导致相对路径找不到文件的原因是因为当前执行类的工作目录不是当前项目路径。现作出如下修改：

6. Collections

• Collections 是一个操作 Set、List 和 Map 等集合的工具类
• Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作， 还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
• 常见方法(static)
  • void reverse(List<?> list) 反转指定列表中元素的顺序
  • void shuffle(List<?> list) 使用默认随机源对指定列表进行置换
  • <T extends Comparable<? super T>> void sort(List<T> list) 根据元素的自然顺序 对指定列表按升序进行排序
  • <T> void sort(List<T> list, Comparator<? super T> c) 根据指定比较器产生的顺序对指定列表进行排序
  • void swap(List<?> list, int i, int j) 在指定列表的指定位置处交换元素
  • <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) 根据元素的自然顺序，返回给定 collection 的最大元素
  • <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) 根据指定比较器产生的顺序，返回给定 collection 的最大元素
  • <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) 根据元素的自然顺序返回给定 collection 的最小元素
  • <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) 根据指定比较器产生的顺序，返回给定 collection 的最小元素
  • int frequency(Collection<?> c, Object o) 返回 collection 中满足 (o == null ? e == null : o.equals(e)) 的 e 元素的数量
  • <T> void copy(List<? super T> dest, List<? extends T> src) 将所有元素从一个列表复制到另一个列表。执行此操作后，目标列表中每个已复制元素的索引将等同于源列表中该元素的索引。目标列表的长度至少必须等于源列表。如果目标列表更长一些，也不会影响目标列表中的其余元素
  • <T> boolean replaceAll(List<T> list, T oldVal, T newVal) 使用另一个值替换列表中出现的所有某一指定值
• 同步控制