Java Tutorials-02-集合

集合类继承关系

Java 核心类库提供了两大类容器, Collection(集合)和 Map, 其中 Collection 接口又派生出 List, Queue, Set 三种接口:

容器顶层接口 Collection/Map 以及主要实现类 & 继承关系:

java.util.Collection [I]
    java.util.List [I]
        ArrayList
        LinkedList*
        Vector
            Stack
    java.util.Queue [I]
        LinkedList*
        PriorityQueue
    java.util.Deque [I]
        LinkedList
    java.util.Set [I]
        TreeSet*
        HashSet*
            LinkedHashSet
java.util.Map [I]
        TreeMap*
        HashMap*
            LinkedHashMap

Collection 接口

Collection 接口方法:

• add(): ArrayList 和 LinkedList 都是 append to end
• remove(Object): 对于 List, remove(obj)是遍历全部元素，找到 obj.equals 的元素并删除，对于 HashSet，remove(obj) 直接调用了 hashmap.remove(obj)
• contains(Object): 对于 List, contains 需要 O(N)遍历, 对于 HashSet, contains 调用的是 hashmap.containsKey()
• containsAll(Collection<?> c): 不是测试是否包含连续的集合, 比如 String.indexOf 那样
• size():
• toArray(): 生成数组
• iterator(): 返回迭代器 Iterator<E>, 它具有 next()方法, 用于每次返回一个元素, 直到循环器中元素穷尽:
• 从 Object 继承的equals(), hashCode()等…

List

List 接口常用方法:

• add(int index, E element):
  Inserts the specified element at the specified position in this list (optional operation).
• addAll(Collection<? extends E> c):
  Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator (optional operation).
• contains(Object o):
  Returns true if this list contains the specified element.
• containsAll(Collection<?> c):
  Returns true if this list contains all of the elements of the specified collection.
• retainAll(Collection<?> c):
  Retains only the elements in this list that are contained in the specified collection (optional operation).
• sort(Comparator<? super E> c):
  Sorts this list according to the order induced by the specified Comparator.
• subList(int fromIndex, int toIndex):
  Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

ArrayList

ArrayList 内部是 Object[] 数组实现, 随机访问性能好, 插入/删除代价较大, iterator 是整数封装.

ArrayList 实现了 List 接口:

• iterator(), listIterator(), listIterator(index)
• add(E), add(index,E), addAll(Collection)
• remove(E), remove(index), removeAll(Collection)
• set(index,E)
• sort(Comparator<? super E> c): 实际调用了Arrays.sort()
• subList(start,end): 返回的并不是 ArrayList ,而是 ArrayList 的一个视图, 对于 SubList 的所有操作最终会反映到原列表上。
• retainAll(Collection) 保留 ArrayList 中和 Collection 中共有的元素(但会改变 ArrayList, 没有在 Collection 中的元素会从 ArrayList 里删除)
• Object[] toArray(): 对该方法返回的数组, 进行操作（增删改查）都不会影响原集合的数据（ArrayList 中 elementData）
• 使用工具类 Arrays 的 asList() 方法把数组转换成集合后, 不能使用该集合的 add / remove / clear 方法, 否则抛出 UnsupportedOperationException 异常。

说明: asList() 的返回对象是一个 Arrays 内部类,并没有实现集合的修改方法。Arrays.asList() 体现的是适配器模式,只是转换接口,后台的数据仍是数组。

➤ add 方法和扩容:

• 如果使用默认构造 ArrayList(), 数组大小是 0, 第一次调用 add，进行第一次扩容，数组容量扩容到 DEFAULT_CAPACITY（10）
• add 方法的逻辑：
  • 先判断 size + 1 （size 是当前 ArrayList 包含的元素个数）是否大于数组容量
  • 如果大于，则先扩容数组，新的数组大小 = 原数组 1.5 倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
  • 新添加的元素放入数组

所以 ArrayList 的扩容机制是：当原数组满了, 下次再 add 时先扩容

• 如果用默认构造创建的 ArrayList, 每次扩容后的大小是: 10, 15, 22, 33, 49 …
• 如果在构造 ArrayList 时就指定了初始大小为 N, 每次扩容后大小都是 1.5 倍

@ref: notes/ArrayList源码分析.md at master · wardseptember/notes · GitHub

LinkedList

链表实现, 随机访问性能差, 插入/删除较快, iterator 是引用封装.
LinkedList 同时实现了 List, Queue, Deque 接口:

• add(E), add(index,E), addAll(Collection)
• poll(), offer(E) … 所有 Queue 接口的方法
• addFirst(E), addLast(E), offerFirst(E), offerLast(E) … 所有 Deque 接口的方法

Vector

Vector 类实现了一个动态数组。功能和 ArrayList 很相似，但是两者是不同的：

• Vector 是线程安全，其方法都是 synchronized 修饰
• Vector 包含了许多传统的方法，这些方法不属于 Collection
• Vector 是 @Deprecated 的，如果不需要线程安全可以用 ArrayList 替代，如果读多写少可以用 CopyOnWriteArrayList 替代

Stack

Stack 是栈结构，先入后出

• 主要方法： push() 入栈, pop() 弹出栈顶部元素, peek() 获取栈顶但不弹出顶部元素
• Stack 实际就是对 Vector 包装了一层, 所以也是 synchronized 同步
• Stack 同样也是弃用类，如果要使用栈功能，推荐使用 Deque（双端队列）代替

Queue & Deque

➤ Queue 接口：

• offer , add: 添加元素到队列尾部.
  当队列满时, offer 返回 false, add 抛出异常.
• poll , remove: 返回队列头部的元素, 并移除出这个元素.
  当队列为空时, poll 返回 false, remove 抛出异常.
• peek , element: 返回队列头部的元素但不移除它.
  当队列空时, peek 返回 false, element 抛出异常.

➤ Deque 接口：

• offerFirst, offerLast : 添加元素到队列, 失败返 false
• addFirst, addLast : 添加元素到队列, 失败抛异常
• pollFirst, poolLast : 返回并移出元素, 失败返 false
• removeFirst, removeLast : 返回并移出元素, 失败抛异常
• peekFirst, peekLast : 返回但不移出, 失败返 false
• elementFirst, elementLast : 返回但不移出, 失败抛异常

LinkedList & ArrayDeque

• LinkedList:

  • 内部是一个双向链表, 同时实现了 Deque 和 Queue 接口, 它是唯一一个允许放入 null 的 Queue；
  • 因为是链表实现，所以没有大小限制；
  • LinkedList 不是线程安全的，如果想使 LinkedList 变成线程安全的，可以调用静态类 Collections 类中的 synchronizedList 方法：List list=Collections.synchronizedList(new LinkedList(...));

• ArrayDeque:

  • 以循环数组实现的双向 Queue，使用默认构造函数初始大小是 16，如果构造时指定大小，会指定为大于此长度的最小 2 的幂倍数；注 1
  • ArrayDeque 有 head 和 tail 两个引用，分别用于在队列头 & 队列尾的增/删；
  • 如果队尾的下标追上队头，说明数组所有空间已用完，进行双倍的数组扩容。

旧版本的 ArrayDeque 在构造时，会根据用户的构造大小重新计算数组大小，但新版本 JDK12 中已经不这样做了：

// 找到大于需要长度的最小的2的幂整数
private void allocateElements(int numElements) {
    // MIN_INITIAL_CAPACITY为8
    int initialCapacity = MIN_INITIAL_CAPACITY;

    if (numElements >= initialCapacity) {

        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)    // Too many elements, must back off
            initialCapacity >>>= 1; // Good luck allocating 2^30 elements
    }
    elements = new Object[initialCapacity];
}

PriorityQueue

• PriorityQueue 是用二叉堆实现的优先级队列，出队列的顺序不是按照 FIFO , 而是最小的元素先出队（小顶堆）。插入的元素必须实现 Comparable, 或者在 PriorityQueue 构造器传入 Comparator；
• 因为需要对元素进行比较，所以 PriorityQueue 不允许 null 元素；
• PriorityQueue 的方法：
  • 入队：add、offer 方法，如果失败，add 抛异常，offer 返回 false，复杂度 O(logN)
  • 获取队头：element、peek 返回堆顶最小的元素，但不删除队头（堆顶），复杂度 O(1)
  • 出队：remove、poll 返回并删除队头（堆顶）最小的元素，复杂度 O(logN)
• PriorityQueue 是通过数组实现二叉堆，数组可以自动扩容，可以认为是无界队列

PriorityQueue 的实现 @ref: Java中PriorityQueue详解 - geekerin - 博客园

线程安全的队列

J.U.C 包提供了线程安全的队列，阻塞/非阻塞 两大类, 详见 Java-并发.05d.JUC-Collections:

• 阻塞：ArrayBlockingQueue, LinkedBlockingQueue, LinkedBlockingDeque；
• 非阻塞： ConcurrentLinkedQueue , ConcurrentLinkedDeque；

Set

Set 是不能包含重复的元素的集合, Set 接口常用方法:

• add(E e)
• addAll(Collection<? extends E> c)
• contains(Object o)
• containsAll(Collection<?> c)
• retainAll(Collection<?> c)
• toArray()

HashSet

HashSet 是一个没有重复元素的集合. 元素并没有以某种特定顺序来存放,
HashSet 内部实现是使用了 HashMap 的transient HashMap<E,Object> map, add(E)方法实际调用的是hashMap.put(e,PRESENT)

@ref: Java 集合系列16之 HashSet详细介绍(源码解析)和使用示例

LinkedHashSet

LinkedHashSet 可以按照插入顺序对元素进行遍历.
LinkedHashSet 继承了 HashSet, 内部是基于 LinkedHashMap 来实现的. 可以在 LinkedHashSet 构造器看出来：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

TreeSet

TreeSet 是基于 TreeMap 实现的（TreeMap 基于红黑树 ）.

TreeSet 中的元素支持 2 种排序方式：Item 实现 Comparable 接口, 或者根据创建 TreeSet 时提供的 Comparator 进行排序. 这取决于使用的构造方法.

TreeSet 的 add、remove 和 contains 方法的时间复杂度是 O(logn).

class Item implements Comparable<Item> {
    int val;
    public int compareTo(Item t) {
        /*
        return 0; 相等
        return 1; this 大
        return -1; 比较的更大
        */
        if(this.val > t.val) return 1;
        else if(this.val < t.val) return -1;
        else return 0;
    }
}

public class TreeSetTest {
    public static void main(String[] args) {
        Set<Teacher> treeSet = new TreeSet<Item>();
        treeSet.add(new Item(3));
        treeSet.add(new Item(1));
        treeSet.add(new Item(2));
        //遍历输出:
        Iterator itTSet = treeSet.iterator();
        while(itTSet.hasNext())
            System.out.print(itTSet.next() + "\t");
    }
}

@ref: Java 集合系列17之 TreeSet详细介绍(源码解析)和使用示例

Iterator: 迭代器

• Iterator 接口的方法
  • hasNext: 返回 true 或 false
  • next: 迭代器后移一次之后, 回迭代器前面的元素
  • remove: 删除上次 next()返回的, 所以新创建迭代器之后, 必须先 next 一次才能 remove. 一次 remove 之前必须有一次 next, 不能连续调用 remove;
  • add: Iterator 接口没有 add, 但 ArrayList 和 LinkedList 的内部 Itr 都实现了 add. 在当前迭代器之前插入. 如果创建了迭代器后立刻 add, 则是插入到首位.
• ArrayList 的 Iterator:
  • 属性int cursor和int lastRet分别用来记录”下次 next 方法要返回的元素位置” 和”上次 next 方法返回的”, 初始值分别是 0和-1;
  • 创建迭代器:
    • 方法 1: ArrayList.iterator()
    • 方法 2: ArrayList.listIterator(), 返回的迭代器有add(Ele)方法用于插入新元素;

How to iterate collection

// 1
for(Iterator<String> itr = collection.iterator(); i.hasNext();) {
    System.out.print(itr.next());
}

// 2
for(int i = 0; i<list.size(); i++){
}

集合泛型算法

区别 Collection & Collections & Arrays 常用的几种 package：

• java.util.Collection<E> 是一个泛型接口;
• java.util.Collections 是一个集合工具类, 提供一些操作 Collection 集合的通用方法;
• java.utils.Arrays 也是一个集合工具类, 提供操作数组的通用方法, 例如 merge, sort 等;
• java.lang.reflect.Array 类提供了数组的反射方法;

图-Collection 类 vs Collections 类:

排序操作（主要针对 List 接口相关）

• reverse(List list)：反转指定 List 集合中元素的顺序
• rotate(List list, int distance)：将所有元素向右移位指定长度, 如果 distance 等于 size 那么结果不变
• shuffle(List list)：对 List 中的元素进行随机排序（洗牌）,实现很简单：遍历 list 每个元素，每次生成一个随机数，将当前元素换入随机数对应的下标，需要 list 继承自 RandomAccess 接口才可以 shuffle（ArrayList 可，LinkedList 不可）
• sort(List list)：对 List 里的元素根据自然升序排序，JDK 里没有使用快排，而是 merge sort 或 tim sort（稳定排序）
• sort(List list, Comparator c)：自定义比较器进行排序
• swap(List list, int i, int j)：将指定 List 集合中 i 处元素和 j 出元素进行交换

如果要使用 Collections.sort, 则要求集合内存放的类型必须实现 Comparable 接口

查找和替换（主要针对 Collection 接口相关）

• binarySearch(List list, Object key)：使用二分搜索法, 以获得指定对象在 List 中的索引, 前提是集合已经排序
• fill(List list, Object obj)：使用指定对象填充
• frequency(Collection Object o)：返回指定集合中指定对象出现的次数
• max(Collection coll)：返回最大元素
• max(Collection coll, Comparator comp)：根据自定义比较器, 返回最大元素
• min(Collection coll)：返回最小元素
• min(Collection coll, Comparator comp)：根据自定义比较器, 返回最小元素
• replaceAll(List list, Object old, Object new)：替换

Map 接口

Map 不是继承 Collection 接口, 也没有继承 Iterable 接口, Map 接口提供的方法:

• put(k,v), get(k), containsKey(k), containsValue(v)
• remove(k), replace(k,v 1,v 2)

HashMap

• HashMap 是一个散列表, 它存储的内容是键值对(key-value)映射.
• HashMap 继承于 AbstractMap, 实现了 Map、Cloneable、java.io.Serializable 接口.
• HashMap 的实现不是同步的, 这意味着它不是线程安全的. 它的 key、value 都可以为 null. 此外, HashMap 中的映射不是有序的.

初始化

HashMap 几个重要成员:

Node[] table;     // 桶
float loadFactor; // 负载因子
int threshold;    // 等于 table.length x loadFactor,  所能容纳的 key-value 对极限
int modCount;     // 记录 HashMap 内部结构发生变化的次数
int size;         // HashMap 当前容纳键值对的数量

• length: 桶数组长度 (默认值是16)
• loadFactor：为负载因子(默认值是0.75)，所以默认构造创建的 HashMap threshold = 12，超过这个数就要扩容

初始化桶数组：

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; // 判断是否超过最大容量
}

入参cap即构造时指定的初始大小，cap-1之后使用了无符号右移，然后进行或运算，将n-1得到的值转成2进制之后，从1的最高位开始将低位全部转化为1，再加1之后就可以得到一个2^n的数（初始桶数组是2的N次幂）

以后每次需要扩容时，桶数组都 double（桶数组大小仍保证是2的N次幂）

put & get

➤ put(Key, Val) 函数大致的实现为:

• 计算 Key 的 hashCode, 创建新的 Node 对象 new Node(hash, key, value, null) ， Node 是 HashMap 的一个内部类，实现了 Map.Entry 接口，Node 对象中存储存储了 hashCode, Key, Val
• 然后再计算 Node 在数组里的 index （index = table.length-1 & Key.hash）;
• 如果没碰撞(table[index] == null), 把 node 直接放到 table 数组里: table[index]=node；
• 如果碰撞了(table[index] != null), 则判断table[i]的首个元素的 key 是否 hashCode 相同 && key equals 为真;
  • 如果二者的 Key 是 equals 的, 说明 Key 相等，需要覆盖掉旧的 value;
  • 如果二者的 Key 不是 equals 的, 说明这里发生了冲突，Node 插入到 table[i] 的链表里, 所以链表里保存是 “Key 的 hashCode 相同, 但 Key 对象不 equals 的 Node”;
• 如果此处 table[i] 发生多次碰撞, 导致链表过长(大于等于 TREEIFY_THRESHOLD, 8), 就把这条链表转换成红黑树；

• 如果 map 内的元素总数超过 threshold( = table.length x loadFactor), 就要 resize（扩容）

  上面提到了 table[index]在哈希冲突时候, 会把 table[index]处理成链表, 当链表过长的时候, 链表的遍历性能是 O(n), 很差, 所以
  当链表长度>=8 时, 转成查找效率更高的红黑树;

➤ get(k) 函数的实现:

• 省略了从 k 计算出 index 的步骤
• 计算出 index 后，接下来是判断 table[index] 保存的是链表 or 红黑树，然后遍历链表 or 树, 判断 Node.key 是否 equal, 如果是, 则返回该节点;

扩容

扩容后的 HashMap 容量是之前的两倍，扩容后，每个 Node 都要重新确认位置，原来在同一条链表（or 红黑树）上的 Node，可能会分配在 newTable[] 的不同位置上。

解决哈希冲突

上面也提到了，JDK 中的 HashMap 对于冲突的 Node 使用了链表存储（1.8 新增红黑树）；

其他解决哈希表冲突的方式有：开放定址、再哈希、链表：@ref [[../19.Algorithm/Alg.13.数据结构-散列表]]

Set 视图

获取 HashMap 的 Set 视图: Set<Map.Entry<K, V>> entrySet(), 返回类型是 EntrySet extends AbstractSet<Map.Entry<K,V>>,

EntrySet 的方法:

• size(): 直接返回 HashMap 的 size
• forEach: 原型为 forEach(Consumer<? super Map.Entry<K,V>> action)

EntrySet 的用途之一是遍历：

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

其实现在于 nextNode，每个 JDK 版本方法名有变动，但 forEach 的实现都类似：遍历 table[] 数组找到！=null 的节点:

final Node<K,V> nextNode() {  
    Node<K,V>[] t;  
    Node<K,V> e = next;  
    if (modCount != expectedModCount)  
        throw new ConcurrentModificationException();  
    if (e == null)  
        throw new NoSuchElementException();  
    if ((next = (current = e).next) == null && (t = table) != null) {  
        do {} while (index < t.length && (next = t[index++]) == null);  
    }  
    return e;  
}

其他细节

为什么桶数组大小是 2^N？

➤ 为什么 table[] 大小是 2 的 N 次方（一定是合数）？

@ref: Java 8系列之重新认识HashMap - 美团技术团队
在 HashMap 中，哈希桶数组 table 的长度 length 大小必须为2的 n 次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考这篇文章，Hashtable 初始化桶大小为 11，就是桶大小设计为素数的应用（Hashtable 扩容后不能保证还是素数）。
HashMap 采用这种非常规设计（2 的 N 次方，扩容 double），主要是为了在定位哈希桶和扩容时做优化：哈希不再简单用 Obj.hash，而是让 hash 高位也尽量参与运算，定位哈希桶不再简单用 mod 而是位移，这种定位方式也给扩容是的 rehash 带来了更高的效率。

ConcurrentHashMap 在计算 table 长度（保证为 2 的 n 次方）、计算 Key 在的 index、扩容等等机制是完全一样的

两种 HashMap 的桶数组的 length 都是2 的 N 次方，通过以下函数保证：

private static final int tableSizeFor(int c) {  
        int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);  
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  
    }

桶大小 length = 2 的 N 次方，转换为二进制，都是如 1000 0000 这种形式：高位是 1，其他位为0；

然后计算 key 在桶数组的位置，使用的是 hash & length-1 ，length-1 后，意味着高位是 0，其他位都是 1，

HashMap 的扩容采用 double 桶数组的方式，
所以扩容前 vs 扩容后的 length-1，区别是增加了一个最高位的 1，
对于同一个 hash 值，所以扩容前 vs 扩容后的 hash & length-1 只有 2 种可能：元素的位置要么是在原位置，要么是在原位置再+ oldLength 的位置；

所以扩容后，对每个元素进行 rehash 可以减少很多工作量，只需要判断一下原 hash 对应的高位是 0 还是 1，是0的新位置不变，是1的话，新索引变成“原位置+oldLength”，
下图为16扩充为32的 resize 示意图，可以看到原 index=15上所有的元素，在新数组的位置要么是 15，要么是 15+ 16：

所以这种设计让 rehash 变得更简单，也有利于 ConcurrentHashMap 并发的扩容；

为什么加载因子是 0.75？

➤ 为什么是 loadFactor 是 0.75?

在理想情况下，使用随机哈希码，在扩容阈值（加载因子）为 0.75 的情况下，节点出现在频率在 Hash 桶（表）中遵循参数平均为 0.5 的泊松分布。

@ref 泊松分布和指数分布：10分钟教程 - 阮一峰的网络日志

LinkedHashMap

• LinkedHashMap 继承自 HashMap, 继承了 HashMap 大部分方法的实现，不同的是 LinkedHashMap 的节点（Entry），包含了 before、after 两个引用，以实现双向链表；在 LinkedHashMap 中也有 head 和 tail 两个成员表示双向链表的头和尾；
• LinkedHashMap 还包含一个重要的成员 accessOrder, 如果设置为 true 表示迭代顺序 = 访问顺序，如果设置为 false 表示迭代顺序 = 插入顺序；
  • 访问顺序：get 和 put 操作后，都会把 Entry 插入到队尾
  • 插入顺序：put 操作后，把会把 Entry 插入到队尾
• LinkedHashMap 在保留 HashMap 的查找效率的同时, 保持元素输出的顺序和输入时的顺序相同, 并提供了元素的 LRU 访问（访问顺序）.

参考: LinkedHashMap内部实现 @ref

TreeMap

TreeMap 是一个有序的 key-value 集合, TreeMap 根据 Key 的自然顺序进行排序, 或者根据 TreeMap 构造器提供的 Comparator 进行排序.
内部是基于红黑树（Red-Black tree）的实现.
TreeMap 的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n).

基本用法：

public static void main(String[] args) {
    Map<Item, Integer> map = new TreeMap<>(new Comparator<Item>() {
        public int compare(Item i1, Item i2) {
            if (i1.score == i2.score) return 0;
            return i1.score.compareTo(i2.score);
        }
    });
    map.put(new Item(10), new Object());
    map.put(new Item(12), new Object());
    map.put(new Item(13), new Object());
    for (Item key : map.keySet()) {
        System.out.println(key);
    }

    System.out.println(map.get(new Item(10)));
}
class Item {
    public int score;
}

TreeMap 实现了 SortedMap 接口，意味着它可以对插入的元素进行排序

public interface SortedMap<K,V> extends Map<K,V> {

    //返回元素比较器。如果是自然顺序，则返回null；
    Comparator<? super K> comparator();

    //返回从fromKey到toKey的集合：含头不含尾
    java.util.SortedMap<K,V> subMap(K fromKey, K toKey);

    //返回从头到toKey的集合：不包含toKey
    java.util.SortedMap<K,V> headMap(K toKey);

    //返回从fromKey到结尾的集合：包含fromKey
    java.util.SortedMap<K,V> tailMap(K fromKey);

    //返回集合中的第一个元素：
    K firstKey();

    //返回集合中的最后一个元素：
    K lastKey();

    //返回集合中所有key的集合：
    Set<K> keySet();

    //返回集合中所有value的集合：
    Collection<V> values();

    //返回集合中的元素映射：
    Set<Map.Entry<K, V>> entrySet();
}

TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合

public interface NavigableMap<K,V> extends SortedMap<K,V> {

    //返回小于key的第一个元素：
    Map.Entry<K,V> lowerEntry(K key);

    //返回小于key的第一个键：
    K lowerKey(K key);

    //返回小于等于key的第一个元素：
    Map.Entry<K,V> floorEntry(K key);

    //返回小于等于key的第一个键：
    K floorKey(K key);

    //返回大于或者等于key的第一个元素：
    Map.Entry<K,V> ceilingEntry(K key);

    //返回大于或者等于key的第一个键：
    K ceilingKey(K key);

    //返回大于key的第一个元素：
    Map.Entry<K,V> higherEntry(K key);

    //返回大于key的第一个键：
    K higherKey(K key);

    //返回集合中第一个元素：
    Map.Entry<K,V> firstEntry();

    //返回集合中最后一个元素：
    Map.Entry<K,V> lastEntry();

    //返回集合中第一个元素，并从集合中删除：
    Map.Entry<K,V> pollFirstEntry();

    //返回集合中最后一个元素，并从集合中删除：
    Map.Entry<K,V> pollLastEntry();

    //返回倒序的Map集合：
    java.util.NavigableMap<K,V> descendingMap();

    NavigableSet<K> navigableKeySet();

    //返回Map集合中倒序的Key组成的Set集合：
    NavigableSet<K> descendingKeySet();

    java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                       K toKey, boolean toInclusive);

    java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);

    java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    SortedMap<K,V> subMap(K fromKey, K toKey);

    SortedMap<K,V> headMap(K toKey);

    SortedMap<K,V> tailMap(K fromKey);
}

为什么采用红黑树

[[../19.Algorithm/Alg.12.数据结构-树]]

HashTable

• HashTable 的方法都是采用了synchronized同步.
• 高并发场景下不推荐使用 HashTable, 应该使用java.util.concurrent.ConcurrentHashMap替代.

WeakHashMap

这种 Map 通常用在数据缓存中.它将键存储在 WeakReference 中, 就是说, 如果没有强引用指向键对象的话, 这些键就可以被垃圾回收线程回收, 实现参考 @ref: Java-Tutorials.13.引用(Reference)

How to iterate map

// 1:
for (Map.Entry<String, String> entry : map.entrySet()) {
    // entry.getKey()
    // entry.getValue()
}

// 2
for (String key : map.keySet()) {
    //map.get(key);
}

// 3
Iterator it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry entry = (Map.Entry)it.next();
    // entry.getKey(), entry.getValue()
}

fail-fast

几乎所有的 Java 容器都有 modCount ，这是为了实现 iterator 的 fail-fast，

• 无论是 add()、remove()，还是 clear()，只要涉及到修改集合中的元素个数时，都会改变 modCount 的值。
• 线程 a”创建了 arrayList 的 Iterator，建立 expectedModCount = modCount（当时的 modCount值）
• 当线程 a 检测到 modCount 最新值不等于 expectedModCount，抛出 ConcurrentModificationException，产生fail-fast事件

@ref: http://wangkuiwu.github.io/2012/02/04/collection-04-fail-fast/