Java容器框架源码阅读笔记（四）Map

java.util.Map框架：

HashMap

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

预备知识

• 红黑树是一种特殊的二叉查找树，由平衡二叉查找树进化而来(在AVL中，保持全树的平衡开销太大)，红黑树只是保持局部平衡，即从每个节点向下直到叶子节点的路径中包含的黑色节点数量相同，达到一种”弱平衡”。它可以在 logn 时间内做查找，插入和删除，n是树中节点的数目。特性:
  • 根节点是黑色
  • 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点
  • 叶子节点是不放数据的黑色节点
  • 红色节点不能连续(红色节点的孩子和父亲节点颜色都不能是红色)

介绍

1. 继承自AbstractMap，实现了Cloneable接口但是是浅拷贝，实现了Seriable可以进行序列化，实现了Map。
2. 基于数组(Node) + 链表(Node) + 红黑树(TreeNode)实现，当链表长度达到8时，链表会变为红黑树。在resize()对红黑树进行切割split()时，如果切割后的红黑树大小减少到6就变回链表。
3. 非线程安全，如果需要线程安全需要使用ConcurrentHashMap、Collections.synchronizedMap(new HashMap())、HashTable
4. 可以存一个null key，数组下标默认是0，之后的null key会覆盖原来的。
5. 数据不保证有序（放进去的顺序和拿出来的顺序不一样），如果需要有序可以使用TreeMap、LinkedHashMap
6. 数组长度是2的幂,初始是16,最大值是32。
7. 数组长度是2的幂,这样可以通过位操作(&)代替%提高计算效率，数组.length – 1 使得低位数字全为1 使得 & 数组.length – 1得到的分布比不是2的幂的情况要均匀。
8. 通过用key的hashcode()再次求hash然后通过位运算得出要存的数组下标。
9. 默认加载因子是0.75,当数组中元素的数量超过数组长度的0.75倍会进行扩容。
10. 通过拉链法解决hash冲突，除此之外解决hash冲突的方法还有开放地址法(再散列法)、再哈希法、建立公共溢出区。

部分源码分析

变量/常量

// 数组默认容量，2^4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 数组最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子，如果没指定负载因子，就会用这个默认的。通过负载因子来确定阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表树化阈值，当链表长度达到8就会变为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 红黑树链化阈值，在resize()时，会对红黑树进行分割split(),如果分割后的红黑树元素个数减少到6就会变为链表
static final int UNTREEIFY_THRESHOLD = 6;

// 在变红黑树时，还会判断数组的【长度】是否大于64，如果小于64则直接进行扩容resize()，不会变为红黑树。
static final int MIN_TREEIFY_CAPACITY = 64;

// 求出的阈值，当键值对的数量大于该阈值后，就会进行resize()扩容
int threshold;

// 可以接收指定的负载因子
final float loadFactor;

get(Object key)

/**  
 * 根据key获取value   
 * */  
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**  
 * 基本思路:  
 * 根据提前计算好的hash =>   
 * 计算数组下标(hash & (tab.length - 1)) =>   
 * 判断下标元素是否是查找的节点 =>   
 *    是：直接返回节点  
 *    不是:继续在红黑树 || 单链表中查找  
 * */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 预判断:数组是否为null，数组长度是否为0，求出的下标对应的元素是否为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 求出的下标对应的数组元素就是要获取的目标节点(如果两个key相同，那么hash肯定相同，所在先比较的hash。再就是先判断两个key是否指向同一个对象，如果指向同一个对象，就不用再执行耗时的equals操作)
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 求出的下标对应的数组元素不是要获取的节点
        if ((e = first.next) != null) {
        	// 从红黑树中查找
            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;
}

put(K key, V value)

/**  
 * 将key，value插入到HashMap中
 * */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**  
 * 基本思路:  
 * 根据提前计算的hash =>  
 * 计算要插入的数组下标(hash & (tab.length - 1)) =>  
 * 根据是链表还是红黑树插入目标节点  
 * */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 指向当前数组
    Node<K,V>[] tab; 
    // 指向数组下标为 "hash与数组长度取模后((n - 1) & hash)" 的元素
    Node<K,V> p; 
    // n是数组长度，i是元素要插入的下标((n - 1) & hash)
    int n, i;
    // 如果数组为null，代表数组还没有初始化。需要执行resize()初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果求出的数组下标对应的元素为null，代表该下标还没有元素，则直接在该下标添加元素
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果求出的数组下标已经存在元素，判断是红黑树还是链表
    else {
        // 找到HashMap中该key对应的元素，然后让e指向该元素。当然也可能不存在该key对应的元素，从而找不到，使得e为null。  
        // 后续通过判断e是否为null来决定此次put是更新操作还是插入操作。  
        // 如果e为null，说明HashMap中并不存在key对应的元素，直接执行的插入操作  
        // 如果e不为null，说明HashMap中存在该key对应的元素，并且让e指向了该元素，需要执行更新操作，更新key对应元素的value。  
        Node<K,V> e; 
        K k;
        // 如果是求出的数组下标的元素key和hash与新传进来的key和hash相同(传过来的key已经存在于数组中)
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            // 注意此时并没有更新节点值，只是将e指向该节点(此时e不为null)，最后会判断e是否为null，决定是否更新。
            e = p;
        // 如果数组元素类型是红黑树 => 将新节点插入/更新到红黑树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        // 数组元素是单链表，进行尾插
            for (int binCount = 0; ; ++binCount) {
                // 插入到表尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 插入元素后，如果当前链表长度 > 7 则调用treefyBin() "决定是否" 变红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 因为binCount 从0开始，当binCount等于7时，代表链表长度为8。
                        // 将链表改为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // 尾插过程中，如果已经存在此key，将e指向此key，退出。后面进行更新旧值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果是已经存在的key，上面的遍历过程只是找到key对应的节点，并没有更新值
        // 最后需要更新节点旧值
        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();
    // LinkedHashMap通过重写它，执行后续的操作：将这个节点添加到双向链表尾部。
    afterNodeInsertion(evict);
    return null;
}

/**
 * 还会进一步判断数组长度是否小于MIN_TREEIFY_CAPACITY，来决定是否变红黑树
 * */
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);
    }
}

public V remove(Object key)

删除key对应的节点

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;
    // n为数组长度，index为通过key求出的下标
    int n, index;
    // 判断边界条件：数组是否为null、数组长度是否为0、下标对应的元素是否为null
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        // node最终指向要删除的节点
        Node<K,V> node = null, e; 
        K k; V v;
        // 判断下标对应的元素是否就是要删除的元素，如果是，直接将node指向这个元素
        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);
            }
        }
        // 删除node指向的节点(因为执行了上面的代码，如果欲删除的元素在map中，此时node已经指向欲删除的元素)
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            // 如果要删除的节点类型是红黑树，就执行红黑树删除节点的api
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 如果要删除的节点类型是单链表，就执行单链表删除节点操作，下面的p此时是node的前置节点(因为在遍历单链表时，p一直在node前面)
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            // 添加修改次数
            ++modCount;
            // 键值对数量减1
            --size;
            // 执行完删除节点操作以后，会执行LinkedHashMap重写的这个方法(实际上就是执行双向链表的删除节点的操作，因为LinkedHashMap里的是双向链表)
            afterNodeRemoval(node);
            // 返回删除的节点
            return node;
        }
    }
    return null;
}

resize()

/**  
 * 2倍扩容数组长度  
 * */  
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
    }
    // 通过HashMap(int initialCapacity, float loadFactor) 或者 HashMap(int initialCapacity) 【新】创建的HashMap对象
    // 新创建的HashMap对象的阈值threshold的值是通过初始长度initialCapacity生成的一个2的幂。
    // 然后将阈值赋给newCap的目的是保证最终创建的数组长度是2的幂。
    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);
    }
    // 针对 " else if (oldThr > 0) " 求阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        // 判断要设置数组长度是否超过了允许的最大容量，来决定阈值的值是现在的值((float)newCap * loadFactor)还是Integer.MAX_VALUE
        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;
                // 如果不只一个元素，并且元素类型是TreeNode
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 如果不只一个元素，并且是单链表 => 遍历单链表
                // 保留整个单链表的顺序，然后整体移动到newTab[X ，X如下↓]后面
                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;
                        // 运算结果为0的元素，用loHead记录并连接成新的链表
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 运算结果不为0的元素，用hiHead记录并连接成新的链表
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 参考Q&A
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Q&A

1. JDK8在resize()中，将原先的链表通过if((e.hash & oldCap) == 0)分割成两个子链表，这两个子链表在新数组中的下标为什么是j和j + oldCap？这样在新数组中通过hash & newTab.length - 1能对应上？
   • 对于(e.hash & oldCap) == 0的元素(后面的分析都是基于这个前提) => 在原数组中的下标等于要转移到新数组中的下标。原因：
     • (e.hash & oldCap) == 0?就是判断oldCap高位对应的hash位是否为0。未扩容之前,hash只和oldCap - 1低位做&运算来求在原始数组中的下标,扩容之后本质上还是和oldCap - 1低位做&运算来求在新数组中的下标。
     • 二倍扩容后，新数组的长度newCap为oldCap << 1，之后求元素在新数组中的下标(hash & (newCap - 1))。因为 newCap - 1高位为0,与此同时高位后一个位(也就是oldCap高位)对应的hash位也为0,所以(hash & (newCap - 1))等价于(hash & (oldCap - 1))。举个例子：

假设oldCap值是2^4 = 16,某个元素e的hash是0111 0101。这个元素在原始数组中的下标应该是hash & oldCap - 1 = 5。此时(e.hash & oldCap) == 0,根据结论：如果扩容以后，元素e所在新数组的下标应该还是hash & oldCap - 1 = 5。 事实是这样：hash & newCap - 1 = 5。

变量	二进制值	备注
oldCap	0000 1000	因为是2的幂所以高位为1,低位全为0。
hash	0111 0101	随意选的
oldCap - 1	0000 0111	oldCap - 1的高位为0,低位全为1
newCap	0001 0000	等于2*oldCap，将oldCap左移一位即可

此时hash & oldCap = 0推出oldCap高位对应的hash位一定为0。否则求出的值绝对不是0。
如下图：当通过hash & (newCap - 1)求元素e在新数组中的下标，实际是和最后三位进行&运算，计算结果和hash & (oldCap - 1)一样

变量	二进制值	备注
hash	0111 0101	oldCap高位对应的hash位为0
newCap -1	0000 1111
oldCap - 1	0000 0111

• 对于(e.hash & oldCap) != 0的元素(后面的分析都是基于这个前提) => 扩容后元素e在新数组中的下标等于元素e在原数组中的下标+原数组长度。 原因：（新数组下标计算过程）
  • 新数组下标
    • hash & (newCap - 1)👇
    • hash & (2 * oldCap - 1)👇
    • hash & (oldCap + oldCap -1)👇
    • (hash & oldCap - hash & 1) + hash & oldCap👇
      • 由(e.hash & oldCap) != 0可以推出oldCap高位对应的hash位不为0可以推出hash & oldCap == oldCap
    • hash & (oldCap - 1) + oldCap👇
  • 原数组下标 + 原数组长度数组

变量	二进制值	备注
hash	0111 1101	oldCap高位对应的hash位不为0
newCap -1	0000 1111
oldCap - 1	0000 0111

2. 为什么长度为6时用链表，为8时用红黑树？中间的7是干嘛的？

   • 因为红黑树查找时间复杂度为O(LogN)，链表查找时间复杂度为O(N)，当链表中节点数量较多时，为了提高查找效率会采用红黑树。又因为红黑树的节点大约是链表节点的两倍，所以为了节省空间，链表转红黑树的阈值不能太小。
   • 对于分布均匀的hash函数来说，桶中冲突元素的数量服从泊松分布，冲突元素数量是8的概率为千万分之一，是一个小概率事件，如果这个小概率事件发生了，说明冲突比较严重，这时就会将链表转为红黑树提高查询效率。

   Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins.

   • 中间隔一个7为了防止链表和红黑树频繁转换影响效率。如果不隔7的话，元素个数频繁从6变到7或者从8变到7，会造成红黑树和链表频繁的进行转换。(个人理解)

3. 为什么不是线程安全的?具体体现在哪儿?

   • 1. 在多线程的情况下，并发执行resize()可能会产生环形链表，从而在get()时可能差生inflate loop。
   • 2. 比如并发插入元素时，会并发修改size。

4. 为什么产生环形链表？

   • 主要是由于转移链表时在新数组中的顺序和原数组顺序不一致导致的。

     • 疫苗：JAVA HASHMAP的死循环
     • A Beautiful Race Condition(需要科学上网)

5. 为什么求出hashCode()之后要二次hash？

   • 二次hash为了使得哈希码低位元素更加具有随机性。

6. 为什么数组长度是2的幂？

   • 可以通过位操作&代替%进行取模运算提高效率。
   • 可以使得求出的数组下标充分依赖hash码，因为2的幂 - 1保证了低位全为1，做&运算可以完全依赖hash，而hash已经通过二次hash随机性很强，从而使得分布会相对均匀。

7. 为什么加载因子loadFactor默认是0.75？

   • 加载因子太大：空间利用率高，查询效率变低，容易发生冲突。
   • 加载因子太小：不容易产生冲突，查询效率高，空间利用率低，频繁扩容会产生性能影响

     As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in
     the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

8. JDK8和JDK7关于HashMap的区别?

   • JDK7基于数组加链表实现，JDK8引入了红黑树解决了发生hash冲突后，链表过长导致查询效率变低的问题。
   • JDK7采用单链表头插法解决hash冲突，JDK8采用尾插法
   • JDK8 resize()后的链表中元素的相对顺序不变。不会产生环形链表（个人看法，没证明）
   • JDK7数组类型是Entry类型，JDK8改为Node类型都是实现的Map.Entry接口。只是改了个名字

9. HashMap和HashTable的区别？

   • HashMap相对于HashTable可以存nul key 和 null value。 HashTable相对于HashMap是线程安全的。

     The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

10. 为什么key一般用不变对象，比如String、Integer？

    • 如果对象可变，比如User对象的name属性变了则计算出来的hash会变化，导致求出的数组下标会变从而找不到之前User对应的value。建议key尽量是String或者Integer，不应该是可变的对象。

11. 解决hash冲突的方法？

• 开放地址法(再散列法)
  • 线性探测：如果冲突了以后，继续向后查找直到找到一个空位
  • 二次探测：相对于线性探测，它是两步两步的跳着找空位，比较灵活

开放地址法适合存放较少数量的键值对，比如Thread中维护的ThreadLocalMap就是用的开放地址法解决的哈希冲突，因为一般通过ThreadLocal设置的键值对数量比较少。如果存放的数量过多，最坏的时间复杂度可能会达到O(n)

• 链地址法：将冲突的元素，构造成一个单链表
• 再哈希法：提前构造多个hash函数，如果某个hash函数冲突以后，再换别的hash函数，直到找到不冲突的为止
• 建立公共溢出区：将冲突的元素放到溢出区中，和不冲突的元素分开。

参考

• Java：手把手带你源码分析 HashMap 1.7
• Java HashMap.get(Object) infinite loop
• Java 容器源码分析之 HashMap

LinkedHashMap

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

介绍

• LinkedHashMap继承自HashMap，在此基础上，将所有键值对用双向链表链了起来，这样可以实现元素的迭代顺序和元素的插入顺序一致。在HashMap基础上加了钩子函数，可以实现元素的迭代顺序和元素的访问顺序一致(访问一个元素以后就会将元素放到双链表的尾部)，通过这个特性可以实现LRU cache

• LinkedHashMap不是线程安全的，如果需要线程安全需要使用Collections.synchronizedMap(new LinkedHashMap())

• LinkedHashMap继承了HashMap，用到了模板模式。一般的get、put、remove、都用到了HashMap中的操作

部分源码解析

变量

// 双向链表头指针，在LRU中可以理解为最【老】的节点(如果缓存不够最先剔除的节点)
/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

// 双向链表尾指针，在LRU中可以理解为最【新】的节点(如果缓存不够最先剔除的节点)
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

// 如果是true遍历时按访问顺序，false遍历时按插入顺序。
/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

void afterNodeInsertion(boolean evict)

插入元素e后会根据removeEldestEntry(first)这个方法设定的阈值来决定是否要移除最老的元素

// 当向map中插入元素后执行的操作
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 执行HashMap中的删除节点api。 first=head就是最老的节点。(看###变量注释👆)
        removeNode(hash(key), key, null, false, true);
    }
}
// 默认直接返回true，可以定制 return size() > 123; 当键值对的数量大于123时就会删除最老的元素。方便实现LRU cache
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

public V get(Object key)

访问元素e后，如果提前设置了accessOrder为true，就会调用afterNodeAccess(Node<K,V> e)将元素e放到链表的末尾(tail),来实现LRU Cache。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

void afterNodeAccess(Node<K,V> e) { // move node to last
    // 指向每一个
    LinkedHashMap.Entry<K,V> last;
    // 如果设置的访问顺序，也就是accessOrder为true并且链表最后一个节点不是e。就将刚才访问的e这个节点放到最后面
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        // 将节点e的前后节点拼接起来，然后移除e，将e放到链表尾部。
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        // 链表尾指针为空(这是放的第一个元素)，就让head指针指向节点e
        if (last == null)
            head = p;
        // 将这个节点放到链表的尾部
        else {
            p.before = last;
            last.after = p;
        }
        // 将双向链表尾指针指向e(将e放到双向链表最后面)
        tail = p;
        // 修改次数+1
        ++modCount;
    }
}

afterNodeRemoval(Node<K,V> e)

当执行HashMap中的remove(Object key)删除节点key对应的元素e后，会执行双向链表中删除节点的操作

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    // p是头节点
    if (b == null)
        head = a;
    // p不是头节点
    else
        b.after = a;
    // p是尾节点
    if (a == null)
        tail = b;
    // p不是尾节点
    else
        a.before = b;
}

Q&A

1. 实现一个LRU Cache？
   • 设置accessOrder为true，保证最近访问过的元素是最新元素
   • 重写removeEldestEntry(Map.Entry eldest)设置一个缓存大小

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    public static final int CACHE_SIZE = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > CACHE_SIZE;
    }

    public LRUCache() {
        super(CACHE_SIZE,0.75f,true);
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> lru = new LRUCache();
        lru.put(1,"a");
        lru.put(2,"b");
        lru.put(3,"c");
        // 因为是从双向链表头部开始遍历到尾部，结果应该是 [1,2,3]，
        System.out.println(lru.keySet());
        lru.get(2);
        // 因为访问了2，所以会将2放到尾部，从双向链表头开始遍历到尾部，结果应该是[1,3,2]
        System.out.println(lru.keySet());
        lru.put(4,"d");
        // 因为缓存容量设置的是3，所以添加4时 由于缓存已经满了，所以需要删除最老的，就是双向链表头部 1，最后结果应该是[3,2,4]
        System.out.println(lru.keySet());
    }
}

WeakHashMap

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>

预备知识

Java中的四种引用

不同的引用类型体现了对垃圾回收的影响，并且可以在一定程度上允许我们干涉自动垃圾回收器。在Java中主要有四种引用类型：

强引用(StrongReference)

强引用是通过赋值运算符=将所引用的对象obj关联起来。比如Object obj = new Object()。如果一个对象的强引用还在，该对象就不会被JVM回收。

软引用(SoftReference)

软引用通过SoftReference将所引用的对象obj👆关联起来。比如SoftReference sr = new SoftReference(obj)。在内存不足要发生内存溢出OOM之前，会被JVM回收。

• 如果SoftReference注册了引用队列ReferenceQueue，当回收软引用关联的对象之后，会将该软引用加入到ReferenceQueue。
• 和软引用关联的对象有用但不是必需的，所以软引用可以做缓存。当JVM内存不足时，会将这部分缓存回收掉。比如用户打开了多个图片，就需要加载多个图片内容到内存中，每个图片内容(字节数组)可以和软引用关联当作缓存，如果内存不足时就会清除内存中缓存的图片内容(字节数组)。不过要注意:当要再次查看图片时每次都要判断图片内容是否已经被回收(判断引用队列中是否有引用了)，如果被回收需要重新加载到内存。

// 一个Image相当于一个图片，如果打开多个图片等价于创建多个Image对象
public class Image {
    // 图片路径
    private String path;
    // 通过字节数组存放图片内容
    private byte[] data;
    // 要和Image对象关联的软引用
    private SoftReference<byte[]> softReference;
    // 构造图片
    Image(String path) {
        this.path = path;
        // 将图片加载进来
        data = readImageByPath(path);
        softReference = new SoftReference<>(data);
    }

    private byte[] readImageByPath(String path) {
        // 为了方便，没有具体实现,一次1MB_
        return new byte[1024 * 1024];
    }

    public byte[] getData() {
        byte[] dataArray = softReference.get();
        // 判断data是否已经被回收了，如果被回收了需要重新读取图片内容到内存中
        if (dataArray == null || dataArray.length == 0) {
            dataArray = readImageByPath(path);
            softReference = new SoftReference<>(dataArray);
        }
        return dataArray;
    }
    
    public static void main(String[] args) {
        // 同时打开100张图片
        for (int i = 100; i > 0; i++) {
            Image image = new Image(i + ".jpg");
        }
    }

}

弱引用(WeakReference)

• 弱引用通过WeakReference将所引用的对象obj关联起来。比如WeakReference sr = new WeakReference(obj),和弱引用关联的对象在垃圾回收时，会被JVM回收。
  • 如果WeakReference注册了引用队列ReferenceQueue，当回收弱引用关联的对象之后，会将该弱引用加入到ReferenceQueue。
  • 和弱引用关联的对象不是必需的，弱引用多用在哈希表中，比如WeakHashMap通过WeakReference可以回收每一个被回收的key对象所关联的Entry(详细见下面源码分析👇)

软引用、弱引用基本上没有本质上的区别，仅仅是软引用对象比弱引用对象的命更长一些罢了。(参考链接)
因此，软引用、弱引用都适合用来实现内存敏感的高速缓存，具体使用哪种引用，这里给几条参考：
1) 如果只是想避免 OutOfMemory 的发生，则可以使用软引用；如果对于性能更在意，想尽快回收一些占用内存比较大的对象，则可以使用弱引用。
2) 如果对象可能会经常使用的，就尽量用软引用；如果对象不被使用的可能性更大些，就可以用弱引用。

幽灵引用(PhantomReference)

• 幽灵引用通过PhantomReference将所引用的对象obj关联起来。比如PhantomReference sr = new PhantomReference(obj)，和幽灵引用关联的对象等价于没有被引用，随时可能被回收。所以如果不给幽灵引用注册引用队列，那这个幽灵引用就没有意义。
  • 如果PhantomReference注册了引用队列ReferenceQueue，当回收幽灵引用关联的对象之前(finalize()之后)，会将该幽灵引用放到引用队列中。
  • 因为每个对象在回收之前，还会执行继承自Object的finalize()用来做一些资源清理的操作，但是JVM什么时间执行finalize()不是确定的。考虑一个场景，在要分配内存创建新的对象时，要确定某个对象要被回收才能分配。此时可以通过幽灵引用结合引用队列实现，当执行了finalize()会将要回收的对象关联的幽灵引用放到引用队列中。此时可以确定这个对象马上要被回收，可以分配内存。

public class PhantomBuffer {

    private byte[] data = new byte[0];

    private ReferenceQueue<byte[]> queue = new ReferenceQueue<byte[]>();

    private PhantomReference<byte[]> ref = new PhantomReference<byte[]>(data, queue);

    public byte[] get() {
        // 会阻塞直到队列 非空。非空以后说明已经执行了要被回收的对象的finalize()，可以分配新的内存
        queue.remove();  
        // 幽灵引用不会自动清空，要手动运行 
        ref.clear(); 
        ref = null;
        // 分配内存
        data = new byte[111];
        // 重新关联
        ref = new PhantomReference<byte[]>(data, queue);

        return data;
    }
}

介绍

WeakHashMap中的Entry内部的key指向的对象可能会被GC回收，即使没有手动调用remove()或者clear()方法。因为WeakHashMap中的Entry继承自WeakReference，把key引用的对象和弱引用关联起来(Entry继承了WeakReference，也就是将key和Entry关联起来)在JVM进行垃圾回收时会将key引用的对象回收。每次执行get、put、resize()等操作时会根据引用队列提前判断key所引用的对象是否被回收来决定是否清除该key关联的Entry以及Entry中的value指向的对象,来尽量避免内存泄漏。

部分源码分析

Entry结构

Entry继承了WeakReference，此时Entry也是一个虚引用。每次创建新的Entry时会将key和Entry关联，并且中。当回收了key所引用的对象以后,会将Entry放到引用队列queue中。所以在每次操作时都会从引用队列中取一个Entry释放掉。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;

    /**
     * Creates new entry.
     */
    Entry(Object key, V value,
          ReferenceQueue<Object> queue,
          int hash, Entry<K,V> next) {
        // 将key和Entry关联，并且给Entry注册一个引用队列queue
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
    // 后续没写
}

public V get(Object key)

根据key获取value，当调用gettable()时会调用expungeStaleEntries()，然后从引用队列中取出Entry,释放掉Entry以及Entry中的value。
在WeakHashMap定义的增、删、改、查方法中，都要调用gettable()。

public V get(Object key) {
    // 如果传入的key是null就用Object代替
    Object k = maskNull(key);
    // 求hash值确定下标
    int h = hash(k);
    // 获取原始数组，并且执行getTable()还会调用expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    // 获取下标
    int index = indexFor(h, tab.length);
    // 找value
    Entry<K,V> e = tab[index];
    while (e != null) {
        // e.get()返回和Entry关联的key
        if (e.hash == h && eq(k, e.get()))
            return e.value;
        e = e.next;
    }
    return null;
}

private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}

// 从引用队列中取出Entry释放掉Entry以及Entry中的value
private void expungeStaleEntries() {
    // 从引用队列中取出Entry
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);
            // 释放Entry(类似删除单链表节点)以及Entry中的value(将e.value=null)
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    // 释放Entry中的value
                    e.value = null; // Help GC
                    // 键值对数量减1
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

参考

• Java 深度历险（四）——Java 垃圾回收机制与引用类型
• Java 4种引用类型
• WeakHashMap
• Java集合框架源码解读(4)——WeakHashMap

TreeMap

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

介绍

• TreeMap是基于红黑树实现的一种Map，对于get、put、remove时间复杂度是log(n)。元素是有序的，顺序是按照key的自然顺序或者是定义的Comparator。

• TreeMap不是线程安全的。如果需要线程安全的TreeMap需要使用SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

• TreeMap实现了NavigableMap间接实现了SortedMap。注意的是SortedMap比较两个key是否相等不是按Map中规定的equals()，而是用自己定义的Comparator中的compareTo()。 参考Java doc：

  This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

使用注意

因为是通过compareTo()比较两个key是否相等，如果compareTo()写错了会出现TreeMap中明明存在该key，并且equals()返回true，但是get()返回null。如下：(下面代码转自廖雪峰大神)

public class Student implements Comparable<Student> {
    final String name;
    final int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, score);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Student) {
            Student o = (Student) obj;
            return Objects.equals(this.name, o.name) && this.score == o.score;
        }
        return false;
    }

    @Override
    public int compareTo(Student o) {
        return this.score < o.score ? -1 : 1;
    }
}

用HashMap测试能正常输出 99 88 77。

Map<Student, Integer> map = new HashMap<>();
map.put(new Student("Michael", 99), 99);
map.put(new Student("Bob", 88), 88);
map.put(new Student("Alice", 77), 77);
System.out.println(map.get(new Student("Michael", 99)));
System.out.println(map.get(new Student("Bob", 88)));
System.out.println(map.get(new Student("Alice", 77)));

用TreeMap测试输出 null null null，因为通过hash确定下标后，通过compareTo()返回值是否为0找到key，但是现在compareTo()不会返回0…..，所以会找不到key，然后返回null。
重写compareTo()，保证当key相等时返回0

public int compareTo(Student o) {
    int result = Integers.compare(this.score,o.score);
    return result != 0 ? result : this.name.compareTo(o.name);
    //return this.score < o.score ? -1 : 1;
}

应用场景

一致性哈希 代码实现思路参照链接

实现负载均衡，因为TreeMap提供了获取第一个大于当前节点的API，ceilingEntry()

1. 建环
2. 构造虚拟节点
3. 接受请求，根据请求定位

   public class ConsitentHash {
       
       // 虚拟节点数量
       private static final int VIRTUAL_NODE_SIZE = 1000;
   
       // 每个物理服务器中虚拟节点的分隔符
       private static final String DILEMMA = "-";
   
       // 哈希策略
       private HashStrategy hashStrategy = new JDKHashCodeStrategy();
   
       public Server select(List<Server> servers, Request request) {
           TreeMap<Integer, Server> hashRing = buildRing(servers);
           return locate(request, hashRing);
       }
   
       private TreeMap<Integer, Server> buildRing(List<Server> servers) {
           TreeMap<Integer, Server> hashRing = new TreeMap<>();
           servers.forEach(server -> {
               for (int i = 0; i < VIRTUAL_NODE_SIZE; i++)
                   hashRing.put(hashStrategy.getHashCode(server.getUrl() + DILEMMA + i), server);
           });
           return hashRing;
       }
   
       private Server locate(Request request, TreeMap<Integer, Server> hashRing) {
           Server server;
           int key = hashStrategy.getHashCode(request.getHashKey());
           Map.Entry<Integer, Server> serverEntry = hashRing.ceilingEntry(key);
           return serverEntry == null ? hashRing.firstEntry().getValue() : serverEntry.getValue();
       }
   
       class Server {
   
           private String url;
   
           public void setUrl(String url) {
               this.url = url;
           }
   
           public String getUrl() {
               return this.url;
           }
   
       }
   
       abstract class HashStrategy {
   
           public abstract int getHashCode(String origin);
   
       }
   
       class JDKHashCodeStrategy extends HashStrategy {
   
           @Override
           public int getHashCode(String origin) {
               return origin.hashCode();
           }
   
       }
   
       class Request {
   
           private String hashKey;
   
           public String getHashKey() {
               return hashKey;
           }
   
           public void setHashKey(String hashKey) {
               this.hashKey = hashKey;
           }
   
       }
   
   }