synchronizedCollection
synchronizedSet
synchronizedSortedSet
synchronizedNavigableSet
synchronizedList
synchronizedMap
synchronizedSortedMap
synchronizedNavigableMap

/**
 * Returns a synchronized (thread-safe) collection backed by the specified
 * collection.  In order to guarantee serial access, it is critical that
 * <strong>all</strong> access to the backing collection is accomplished
 * through the returned collection.<p>
 *
 * It is imperative that the user manually synchronize on the returned
 * collection when traversing it via {@link Iterator}, {@link Spliterator}
 * or {@link Stream}:
 * <pre>
 *  Collection c = Collections.synchronizedCollection(myCollection);
 *     ...
 *  synchronized (c) {
 *      Iterator i = c.iterator(); // Must be in the synchronized block
 *      while (i.hasNext())
 *         foo(i.next());
 *  }
 * </pre>
 * Failure to follow this advice may result in non-deterministic behavior.
 *
 * <p>The returned collection does <i>not</i> pass the {@code hashCode}
 * and {@code equals} operations through to the backing collection, but
 * relies on {@code Object}'s equals and hashCode methods.  This is
 * necessary to preserve the contracts of these operations in the case
 * that the backing collection is a set or a list.<p>
 *
 * The returned collection will be serializable if the specified collection
 * is serializable.
 *
 * @param  <T> the class of the objects in the collection
 * @param  c the collection to be "wrapped" in a synchronized collection.
 * @return a synchronized view of the specified collection.
 */
public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}

static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    private static final long serialVersionUID = 3053995032091335093L;

    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize

    SynchronizedCollection(Collection<E> c) {
        this.c = Objects.requireNonNull(c);
        mutex = this;
    }

    SynchronizedCollection(Collection<E> c, Object mutex) {
        this.c = Objects.requireNonNull(c);
        this.mutex = Objects.requireNonNull(mutex);
    }

    public int size() {
        synchronized (mutex) {return c.size();}
    }
    public boolean isEmpty() {
        synchronized (mutex) {return c.isEmpty();}
    }
    public boolean contains(Object o) {
        synchronized (mutex) {return c.contains(o);}
    }
    public Object[] toArray() {
        synchronized (mutex) {return c.toArray();}
    }
    public <T> T[] toArray(T[] a) {
        synchronized (mutex) {return c.toArray(a);}
    }

    public Iterator<E> iterator() {
        return c.iterator(); // Must be manually synched by user!
    }

    public boolean add(E e) {
        synchronized (mutex) {return c.add(e);}
    }
    public boolean remove(Object o) {
        synchronized (mutex) {return c.remove(o);}
    }

    public boolean containsAll(Collection<?> coll) {
        synchronized (mutex) {return c.containsAll(coll);}
    }
    public boolean addAll(Collection<? extends E> coll) {
        synchronized (mutex) {return c.addAll(coll);}
    }
    public boolean removeAll(Collection<?> coll) {
        synchronized (mutex) {return c.removeAll(coll);}
    }
    public boolean retainAll(Collection<?> coll) {
        synchronized (mutex) {return c.retainAll(coll);}
    }
    public void clear() {
        synchronized (mutex) {c.clear();}
    }
    public String toString() {
        synchronized (mutex) {return c.toString();}
    }
    // Override default methods in Collection
    @Override
    public void forEach(Consumer<? super E> consumer) {
        synchronized (mutex) {c.forEach(consumer);}
    }
    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        synchronized (mutex) {return c.removeIf(filter);}
    }
    @Override
    public Spliterator<E> spliterator() {
        return c.spliterator(); // Must be manually synched by user!
    }
    @Override
    public Stream<E> stream() {
        return c.stream(); // Must be manually synched by user!
    }
    @Override
    public Stream<E> parallelStream() {
        return c.parallelStream(); // Must be manually synched by user!
    }
    private void writeObject(ObjectOutputStream s) throws IOException {
        synchronized (mutex) {s.defaultWriteObject();}
    }
}

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return 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;
    }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final String toString() { return key + "=" + value; }
}

/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * linked node.
 */
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);
    }

    ......

}

/**
 * The default initial capacity - MUST be a power of two.
 * 数组默认初始容量为 16，必须是 2 的 n 次幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 *
 * 数组最大容量，，必须是 2 的 n 次幂，且小于等于 2^30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 默认装载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 *
 * 桶树化时的阈值
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 *
 * 桶非树化时的阈值
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 * 
 * 树化时数组最小容量
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 *
 * 底层数组
 */
transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 *
 * 实际存储的键值对数量
 */
transient int size;

/**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 *
 * 修改次数
 */
transient int modCount;

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * resize 操作的阈值（capacity * load factor）
 */
int threshold;

/**
 * The load factor for the hash table.
 *
 * 装载因子
 */
final float loadFactor;

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
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);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

/**
 * Creates a {@code HashMap} instance, with a high enough "initial capacity"
 * that it <i>should</i> hold {@code expectedSize} elements without growth.
 * This behavior cannot be broadly guaranteed, but it is observed to be true
 * for OpenJDK 1.7. It also can't be guaranteed that the method isn't
 * inadvertently <i>oversizing</i> the returned map.
 *
 * @param expectedSize the number of entries you expect to add to the
 *        returned map
 * @return a new, empty {@code HashMap} with enough capacity to hold {@code
 *         expectedSize} entries without resizing
 * @throws IllegalArgumentException if {@code expectedSize} is negative
 */
public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
  return new HashMap<K, V>(capacity(expectedSize));
}

/**
 * Returns a capacity that is sufficient to keep the map from being resized as
 * long as it grows no larger than expectedSize and the load factor is >= its
 * default (0.75).
 */
static int capacity(int expectedSize) {
  if (expectedSize < 3) {
    checkNonnegative(expectedSize, "expectedSize");
    return expectedSize + 1;
  }
  if (expectedSize < Ints.MAX_POWER_OF_TWO) {
    // This is the calculation used in JDK8 to resize when a putAll
    // happens; it seems to be the most conservative calculation we
    // can make.  0.75 is the default load factor.
    return (int) ((float) expectedSize / 0.75F + 1.0F);
  }
  return Integer.MAX_VALUE; // any large value
}

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// capacity 表示 table.length
int index = hash(key) & (capacity - 1)

int hash(Object key) {
    int h = key.hashCode();
    h = h ^ (h >>> 16);
    return h & (capitity - 1); //capicity 表示散列表的大小
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @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) {
    // tab 表示底层数组
    // p 表示头结点
    // n 表示数组长度
    // i 表示数组下标
    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 {
        // e 表示当前节点
        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) {
                // 找到尾结点
                if ((e = p.next) == null) {
                    // 创建新节点并追加到单链表末尾
                    p.next = newNode(hash, key, value, null);
                    // 如果节点数超过 8 个，则进行树化，避免大量散列冲突导致散列表退化成单链表，导致查询时间复杂度从 0(1) 退化成 0(n)
                    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;
}

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
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);
    }
}

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判断散列表不为空，且通过散列函数（hash % n）得到的头节点存在
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 如是，且头节点散列值、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) {
            // 树节点
            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;
}

/**
 * Implements Map.remove and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
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;
}

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    ...
}

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

@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

/**
 * Copies all of the mappings from the specified map to this map.
 * These mappings will replace any mappings that this map had for
 * any of the keys currently in the specified map.
 *
 * @param m mappings to be stored in this map
 * @throws NullPointerException if the specified map is null
 */
@Override
public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

/**
 * Implements Map.putAll and Map constructor
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    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();
        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);
        }
    }
}

@Override
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}


@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

@Override
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

@Override
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

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

@Override
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

@Override
public void clear() {
    Node<K,V>[] tab;
    modCount++;
    
    // 内部数组不为空，则遍历并清空所有元素
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

Map<String, String> map = ImmutableMap.of("A", "Apple", "B", "Boy", "C", "Cat");

Maps.newHashMapWithExpectedSize(10);

// key 遍历
map.forEach((key, value) -> {});

// key 遍历
for (String key : map.keySet()) {}

// value 遍历
for (String value : map.values()) {}

// entry 遍历
for (Map.Entry<String, String> entry : map.entrySet()) {}

// entry 显式迭代器
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, String> entry = it.next();
}

// foreach 循环增强，不再需要显式迭代器，简化迭代集合操作
for (Map.Entry<String, String> entry : map.entrySet()) {}

/**
 * HashMap 按散列函数（取余运算）后获得的索引顺序进行存储
 *
 * (32, 1), 32 % 16 = 0
 * (16, 2), 16 % 16 = 0
 * (65, 4), 65 % 16 = 1
 * (4, 5),  4 % 16 = 4
 * (15, 3), 15 % 16 = 15
 */
@Test
public void testHashMap() {
    Map<Integer, String> map = new HashMap<>(16);
    map.put(32, "1");
    map.put(16, "2");
    map.put(15, "3");
    map.put(65, "4");
    map.put(4, "5");
    map.forEach((key, value) -> log.info("({}, {}), {} % 16 = {}", key, value, key, key % 16));
}

/**
 * TreeMap 按自然顺序进行排序（红黑树实现，查找的时间复杂度为 O(log(n))）
 * 
 * (4, 5)
 * (15, 3)
 * (16, 2)
 * (32, 1)
 * (65, 4)
 */
@Test
public void testTreeMap() {
    // Map<Integer, String> map = new TreeMap<>((o1, o2) -> o1.compareTo(o2));
    // Map<Integer, String> map = new TreeMap<>(Comparator.naturalOrder());
    Map<Integer, String> map = new TreeMap<>();
    map.put(32, "1");
    map.put(16, "2");
    map.put(15, "3");
    map.put(65, "4");
    map.put(4, "5");
    map.forEach((key, value) -> log.info("({}, {})", key, value));
}

/**
 * LinkedHashMap 大部分构造方法 默认按插入顺序进行排序（accessOrder=false）。底层维护了一个链式队列，可用于实现 FIFO 缓存淘汰策略
 *
 * (32, 1)
 * (16, 2)
 * (15, 3)
 * (65, 4)
 * (4, 5)
 */
@Test
public void testLinkedHashMap() {
    Map<Integer, String> map = new LinkedHashMap<>(16);
    map.put(32, "1");
    map.put(16, "2");
    map.put(15, "3");
    map.put(65, "4");
    map.put(4, "5");
    map.forEach((key, value) -> log.info("({}, {})", key, value));
}

/**
 * LinkedHashMap 唯一一个构造方法 用于按访问顺序进行排序（accessOrder=true）。底层维护了一个链式队列，可用于实现 LRU 缓存淘汰策略
 * (15, 3)
 * (65, 4)
 * (4, 5)
 * (16, 2)
 * (32, 1)
 */
@Test
public void testLinkedHashMap2() {
    Map<Integer, String> map = new LinkedHashMap<>(16, .75F, true);
    map.put(32, "1");
    map.put(16, "2");
    map.put(15, "3");
    map.put(65, "4");
    map.put(4, "5");

    map.get(16);
    map.get(32);

    map.forEach((key, value) -> log.info("({}, {})", key, value));
}

/**
 * (1: one) removed
 * (2: two) removed
 * (3, three) hit
 * (4, four) hit
 * (5, five) hit
 */
@Test
public void FIFO() {
    Map<Integer, String> map = new LinkedHashMap<Integer, String>(3, .75F, false) {
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            if (size() > 3) {
                log.info("({}: {}) removed", eldest.getKey(), eldest.getValue());
                return true;
            } else {
                return false;
            }
        }
    };
    map.put(1, "one");
    map.put(2, "two");
    map.put(3, "three");
    map.get(1);
    map.put(4, "four");
    map.get(3);
    map.put(5, "five");
    map.forEach((key, value) -> log.info("({}, {}) hit", key, value));
}

/**
 * (2: two) removed
 * (1: one) removed
 * (4, four) hit
 * (3, three) hit
 * (5, five) hit
 */
@Test
public void LRU() {
    Map<Integer, String> map = new LinkedHashMap<Integer, String>(3, .75F, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            if (size() > 3) {
                log.info("({}: {}) removed", eldest.getKey(), eldest.getValue());
                return true;
            } else {
                return false;
            }
        }
    };
    map.put(1, "one");
    map.put(2, "two");
    map.put(3, "three");
    map.get(1);
    map.put(4, "four");
    map.get(3);
    map.put(5, "five");
    map.forEach((key, value) -> log.info("({}, {}) hit", key, value));
}

private static final Map<String, Integer> IP_STATS = new HashMap<>();

// 老版本
public synchronized int oldIpStats(String ip) {
    if (!IP_STATS.containsKey(ip)) {
        IP_STATS.put(ip, 1);
    } else {
        IP_STATS.put(ip, IP_STATS.get(ip) + 1);
    }
    return IP_STATS.get(ip);
}

// 新版本
public synchronized int newIpStats(String ip) {
    return IP_STATS.compute(ip, (key, oldValue) -> {
        if (oldValue == null) {
            return 1;
        } else {
            return oldValue + 1;
        }
    });
}

// result is 1
log.info("result is {}", newIpStats("127.0.0.1"));
// result is 2
log.info("result is {}", newIpStats("127.0.0.1"));
// result is 3
log.info("result is {}", newIpStats("127.0.0.1"));

/**
 * 统计 N 个随机数中最热门的 K 个
 */
@Test
public void topK() {
    int N = 100;
    // 「键值对」底层实现使用散列表即可，因为无须有序
    Map<Integer, Integer> numStats = Maps.newHashMapWithExpectedSize(N);

    Random random = new Random();
    for (int i = 0; i < N; i++) {
        int num = random.nextInt(10);
        // 首先，按「键值对」保存统计数据（key 为关键字，value 为统计次数）
        numStats.compute(num, (key, oldVal) -> {
            if (oldVal == null) {
                return 1;
            } else {
                return oldVal + 1;
            }
        });
    }
    log.info("Before sort:");
    numStats.forEach((key, val) -> log.info("({}, {})", key, val));

    log.info("After sorted by statistics desc:");
    // 然后，按「值」倒序
    List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(numStats.entrySet());
    entries.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));
    // 最后，取 Top K 个「键」
    entries.forEach(entry -> log.info("({}, {})", entry.getKey(), entry.getValue()));
}

// 单端顺序队列
Queue<Integer> queue = new ArrayDeque<>(10);

// 双端顺序队列
Deque<Integer> deque = new ArrayDeque<>(10);

/**
 * The array in which the elements of the deque are stored.
 * The capacity of the deque is the length of this array, which is
 * always a power of two. The array is never allowed to become
 * full, except transiently within an addX method where it is
 * resized (see doubleCapacity) immediately upon becoming full,
 * thus avoiding head and tail wrapping around to equal each
 * other.  We also guarantee that all array cells not holding
 * deque elements are always null.
 */
transient Object[] elements; // non-private to simplify nested class access

/**
 * The index of the element at the head of the deque (which is the
 * element that would be removed by remove() or pop()); or an
 * arbitrary number equal to tail if the deque is empty.
 */
transient int head;

/**
 * The index at which the next element would be added to the tail
 * of the deque (via addLast(E), add(E), or push(E)).
 */
transient int tail;