第6章 - Java 集合

作者：vwFisher
時間：2019-09-04
GitHub代碼：https://github.com/vwFisher/JavaBasicGuide

目錄

• 1 Java集合類(集合框架)
  • 1.1 集合類概述
  • 1.2 Iterable留攒、Iterator享扔、ListIterator
    • 1.2.1 Iterable
    • 1.2.2 Iterator - 迭代器
    • 1.2.3 ListIterator
  • 1.3 Collection - 單列集合
    • 1.3.1 List - 列表
      • 1.3.1.1 ArrayList類
      • 1.3.1.2 LinkedList類
      • 1.3.1.2 Vector類
      • 1.3.1.4 ArrayList和LinkedList的區(qū)別
      • 1.3.1.5 RandomAccess接口
    • 1.3.2 Set接口的常用方法
      • 1.3.2.1 HashSet類
      • 1.3.2.2 LinkedHashSet類(HashSet的子類)
      • 1.3.2.3 TreeSet類
    • 1.3.3 Collection泛型
      • 1.3.3.4 使用Collection技巧
  • 1.4 Map - 雙列集合
    • 1.4.1 Map接口的實現(xiàn)類
      • 1.4.1.1 HashMap類
      • 1.4.1.2 TreeMap類
      • 1.4.1.3 Hashtable類
      • 1.4.1.4 Properties(Hashtable子類)
      • 1.4.1.5 LinkedHashMap(HashMap子類)
    • 1.4.2 遍歷Map數(shù)據(jù)總結(jié)
  • 1.3 Collections(集合框架工具類)

1 Java集合類(集合框架)

1.1 集合類概述

對象用于封裝特有數(shù)據(jù)管行，對象多了需要存儲娶靡，如果對象的個數(shù)不確定描焰。就使用集合容器進行存儲。Java語言的java.util包中提供了一些集合類东亦，這些集合類又被稱為容器(數(shù)組也是個容器)

集合類特點：主要是用來存儲對象容器，長度是可變的扒披，不可以存儲基本數(shù)據(jù)類型值

與數(shù)組對比：集合長度可變，用來存放對象圃泡。而數(shù)組長度固定碟案，用來存放基本類型的數(shù)據(jù)

常見的集合有List集合、Set集合颇蜡、 Map集合价说、其中List與Set實現(xiàn)了Collection接口，來看看類結(jié)構(gòu)圖

集合結(jié)構(gòu)圖.png

如圖所示:

一风秤、集合接口: 8個接口(短虛線表示), 表示不同集合類型, 是集合框架的基礎(chǔ)

Iterator, ListIterator,
Collection, List, Set, Map
SortedSet, SortedMap

二鳖目、抽象類: 5個抽象類(長虛線表示), 對集合接口的部分實現(xiàn), 可擴展為自定義集合類

AbstractCollection, AbstractList, AbstractSet, 
AbstractMap、AbstractSequentialList

三缤弦、實現(xiàn)類: 13個實現(xiàn)類(實線表示), 對接口的具體實現(xiàn)

Vector, Stack, ArrayList, LinkedList
HashSet, TreeSet, LinkedHashSet
HashMap, LinkedHashMap, TreeMap, Hashtable, Properties
WeakHashMap, IdentityHashMap

四领迈、接口詳解

1. Collection接口 是一組允許重復(fù)的對象
2. Set接口 繼承 Collection。但不允許重復(fù)碍沐。使用自己內(nèi)部的一個排列機制
3. List接口 繼承 Collection狸捅。允許重復(fù)，以元素插人的次序來放置元素累提，不會重新排列
4. Map接口 是一組成對的鍵－值對象薪贫。即所持有的是 key-value (鍵值對)。Map中不能有重復(fù)的key刻恭。擁有自己的內(nèi)部排列機制

五瞧省、關(guān)于null對象

1. 可以包括null：ArrayList、LinkedList鳍贾、Verctor鞍匾、HashSet、LinkedHashSet骑科、HashMap橡淑、LinkedHashMap

2. 不可以包括null：TreeSet、TreeMap咆爽、Hashtable(鍵和值)

六梁棠、集合的特點對比

1.接口對比

• Set子接口：無序，不允許重復(fù)斗埂。檢索元素效率低, 刪除和插入效率高, 插入和刪除不會引起元素位置改變. <對應(yīng)類有 HashSet, TreeSet>
• List子接口：有序符糊，可以有重復(fù)元素。和數(shù)組類似, List可以動態(tài)增長, 查找元素效率高, 插入刪除元素效率低, 因為會引起其他元素位置改變. <相應(yīng)類有 ArrayList, LinkedList, Vector>

2.實例比較

• HashSet: 以哈希表的形式存放元素, 插入刪除速度很快.
• TreeSet: 以二叉樹的形式存放元素
• ArrayList: 動態(tài)數(shù)組
• LinkedList: 鏈表呛凶、隊列男娄、堆棧
• Vector是一種老的動態(tài)數(shù)組：是線程同步的, 效率很低, 一般不贊成使用

七、Java容器的線程安全與非線程安全?

1.談?wù)勀男┦蔷€程安全的容器, 哪些非線程安全的容器.

• 線程安全：Vector、HashTable模闲、StringBuffer
• 非線程安全：ArrayList建瘫、LinkedList、HashMap尸折、TreeMap啰脚、StringBuilder

2.線程安全有什么好處, 有什么壞處

線程安全即在多線程操作同一個 Vector 或 HashTable 對象時不會有任何問題. 但是線程安全必須要使用很多 synchronized 關(guān)鍵字來同步控制, 所以必然會導(dǎo)致性能的降低. Java后續(xù)版本出才出現(xiàn)了眾多非線程安全的容器

3.安全與性能如何取舍.

如果是多個線程操作同一個對象, 那么使用線程安全的Vector; 否則, 就使用效率更高的ArrayList

4.補充說明, 非線程安全 != 不安全.

有人在使用過程中有一個不正確的觀點: 我的程序是多線程的, 不能使用ArrayList要使用Vector, 這樣才安全. 非線程安全并不是多線程環(huán)境下就不能使用. 注意我上面有說到: 多線程操作同一個對象. 注意是同一個對象. 如果是每個線程中new一個ArrayList, 而這個ArrayList只在這一個線程中使用, 那么肯定是沒問題的

1.2 Iterable、Iterator实夹、ListIterator

1.2.1 Iterable

一個集合對象要表明自己支持迭代橄浓，能有使用foreach語句的特權(quán)，就必須實現(xiàn)Iterable接口收擦，表明是可迭代的贮配！然而實現(xiàn)Iterable接口，就必需為foreach語句提供一個迭代器塞赂。來看看接口定義內(nèi)容

public interface Iterable<T> {
    Iterator<T> iterator(); // 返回迭代器Iterator
    default void forEach(Consumer<? super T> action) { // 提供forEach語法糖
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    default Spliterator<T> spliterator() { // 創(chuàng)建并返回一個可分割迭代器
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

1.2.2 Iterator - 迭代器

Iterator就是迭代器泪勒，規(guī)定迭代接口定義。

public interface Iterator<E> {
    boolean hasNext(); // 如果仍有元素可以迭代, 則返回true
    E next(); // 返回迭代的下一個元素
    // 從迭代器指向的collection中移除迭代器返回的最后一個元素(可選操作)宴猾，由子類定義圆存，默認不支持
    default void remove() { 
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

1.2.3 ListIterator

ListIterator也是接口，是對Iterator的接口定義的擴展

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

1.3 Collection - 單列集合

Collection(單列集合)：一次添加一個元素<T>仇哆。它是一個接口沦辙，定義了單列集合接口約束。是單列集合的頂層定義讹剔，List與Set接口都實現(xiàn)Collection油讯，接口定義如下：

Collection實現(xiàn)Iterable接口，即包含提供迭代器方法延欠，也包括forEach語法糖遍歷方法陌兑。

添加：
    boolean add(E e); // 添加一個元素
    boolean addAll(Collection<? extends E> c); // 添加元素集合
刪除：
    boolean remove(Object o);  // 刪除一個元素
    boolean removeAll(Collection<?> c);  // 刪除元素集合
    void clear(); // 清空
判斷：
    boolean contains(Object o);  // 判斷是否包含一個元素
    boolean containsAll(Collection<?> c);  // 判斷是否包含元素集合
    boolean isEmpty(); // 判斷集合是否有元素
    boolean equals(Object o); // 判斷與指定對象，比較方式由子類實現(xiàn)由捎，一般與haseCode函數(shù)相關(guān)
獲取
    int hashCode(); // 獲取該集合對象的hashCode
    int size(); // 獲取該集合元素的大小(數(shù)量)
    Iterator<E> iterator(); // 獲取迭代器對象
    boolean retainAll(Collection<?> c); // 與元素集合C兔综，取交集
轉(zhuǎn)化數(shù)組：
    Object[] toArray(); // 將集合轉(zhuǎn)成Object數(shù)組
    <T> T[] toArray(T[] a); // 將集合轉(zhuǎn)成自定義對象數(shù)組
default方法：
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    @Override
    default Spliterator<E> spliterator() { // 創(chuàng)建并返回一個可分割迭代器
        return Spliterators.spliterator(this, 0);
    }
    default Stream<E> stream() { // 轉(zhuǎn)化成Stream對象
        return StreamSupport.stream(spliterator(), false);
    }
    default Stream<E> parallelStream() { // 轉(zhuǎn)化成并行Stream對象
        return StreamSupport.stream(spliterator(), true);
    }
    AbstractCollection是實現(xiàn)Collection的抽象類，通過結(jié)合Iterator接口約束狞玛，對一些方法的實現(xiàn)软驰。

1.3.1 List - 列表

AbstractList是實現(xiàn)List的抽象類，通過結(jié)合ListIterator接口約束心肪，對一些方法的實現(xiàn)锭亏。

List特點: 有序(存入和取出的順序一致), 元素都有索引(角標), 元素可以重復(fù)

List:(是有序的) 
    |-- ArrayList：內(nèi)部是數(shù)組數(shù)據(jù)結(jié)構(gòu), 是不同步的. 替代了Vector. 查詢的速度快.
    |-- LinkedList：內(nèi)部是鏈表數(shù)據(jù)結(jié)構(gòu), 是不同步的. 增刪元素的速度很快. 
    |-- Vector：內(nèi)部是數(shù)組數(shù)據(jù)結(jié)構(gòu), 是同步的. 增刪, 查詢都很慢

List接口繼承了Collection接口，在Collection基礎(chǔ)上蒙畴，擴展定義列表的接口規(guī)范贰镣。擴展定義的方法：

    void add(int index, E element); // 在索引位置插入元素(索引從0開始)
    boolean addAll(int index, Collection<? extends E> c); // 在指定索引位置插入元素集合
    E set(int index, E element); // 指定元素替換列表中指定索引位置的元素, 返回被替換的元素
    E remove(int index); // 移除指定索引位置的元素, 返回被移除的元素
    E get(int index); // 用于獲取指定索引位置的元素
    int indexOf(Object o); // 返回列表中對象最后一次出現(xiàn)的索引位置, 如果集合中不包含該元素, 則返回-1
    int lastIndexOf(Object o); // 返回列表中對象最后一次出現(xiàn)的索引位置, 如果集合中不包含該元素, 則返回-1 
    ListIterator<E> listIterator(); // 用來獲取一個包含所有對象的ListIterator列表迭代器
    ListIterator<E> listIterator(int index); 
    List<E> subList(int fromIndex, int toIndex); // 獲取子集合列表呜象，從fromIndex -> toIndex
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }

1.3.1.1 ArrayList類

(basic.coll.collection.list.ArrayListDemo)

1. 底層數(shù)據(jù)結(jié)構(gòu)：Object對象類型的數(shù)組膳凝，允許所有元素碑隆，包括null
2. 優(yōu)點：可以根據(jù)索引位置對集合進行快速的隨機訪問
3. 缺點：向指定的索引位置插入對象或刪除對象的速度較慢
4. 使用場景：讀 多于 寫的場景
5. 擴容機制：正常情況下會擴容1.5倍，特殊情況下(新擴展數(shù)組大小已經(jīng)達到了最大值)則只取最大值蹬音。
6. 擴容時機：調(diào)用add()方法的重載時上煤，第一步是檢查容量，如果容量不夠則進行擴容

類定義：

public class ArrayList<E> extends AbstractList<E> 
  implements List<E>, RandomAccess, Cloneable, Serializable

繼承了AbstractList著淆、實現(xiàn)List接口劫狠、支持隨機訪問、拷貝永部、序列化

重要的類屬性：

private static final int DEFAULT_CAPACITY = 10; // 缺省容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空對象數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 缺省空對象數(shù)組
transient Object[] elementData; // 元素數(shù)組(trabsuebt独泞，該變量不包括在序列化的表示中)
private int size; // 實際元素大小，默認為0
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 最大數(shù)組容量

構(gòu)造函數(shù)：

public ArrayList(int initialCapacity)
public ArrayList()
public ArrayList(Collection<? extends E> c)

核心函數(shù)實現(xiàn)分析 add()：

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 取保數(shù)組又合適的大小
        elementData[size++] = e;
        return true;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 修改次數(shù)的記錄：修改加1
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; // 舊容量
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍擴容
        if (newCapacity - minCapacity < 0) // 新容量小于參數(shù)指定容量苔埋，修改新容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity); // 拷貝擴容
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

正常情況下會擴容1.5倍懦砂，特殊情況下（新擴展數(shù)組大小已經(jīng)達到了最大值）則只取最大值。modCount意思是修改次數(shù)组橄，在集合幾個容器中基本上都有荞膘。

其他需要說明的，indexOf()玉工、set()羽资、get()、remove()函數(shù)實現(xiàn)遵班，第一步一般都是檢查索引是否合法屠升。remove移除指定下標的元素，此時會把指定下標到數(shù)組末尾的元素向前移動一個單位狭郑，并且會把數(shù)組最后一個元素設(shè)置為null腹暖，這樣是為了方便之后將整個數(shù)組不被使用時，會被GC

1.3.1.2 LinkedList類

(basic.coll.collection.list.LInkedListDemo)

1. 底層數(shù)據(jù)結(jié)構(gòu)：采用Node對象愿阐，雙向鏈表結(jié)構(gòu)微服，有一個頭結(jié)點和一個尾結(jié)點(JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán))
2. 優(yōu)點：插入缨历、刪除效率比較高以蕴。
3. 缺點：對于隨機訪問集合中的對象, 效率較慢
4. 使用場景：寫 多于 讀的場景。也可以拿來實現(xiàn)堆棧和隊列

類定義：

public class LinkedList<E> extends AbstractSequentialList<E> 
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable

與ArrayList不同的辛孵，主要在于AbstractSequentialListh和Deque丛肮。Deque定義雙向隊列的接口方法。

類的屬性

transient int size = 0; // 容量
transient Node<E> first; // 首節(jié)點
transient Node<E> last; // 尾節(jié)點
private static class Node<E> { // Node節(jié)點的定義
    E item; // 當(dāng)前元素
    Node<E> next; // 前一個節(jié)點指針
    Node<E> prev; // 后一個節(jié)點指針
}

說明：LinkedList的屬性非常簡單魄缚，一個頭結(jié)點宝与、一個尾結(jié)點焚廊、一個表示鏈表中實際元素個數(shù)的變量。都有transient關(guān)鍵字修飾习劫，這也意味著在序列化時該域是不會序列化的咆瘟。

構(gòu)造函數(shù)：

public LinkedList()
public LinkedList(Collection<? extends E> c)

實現(xiàn)的Deque方法說明：

void addFirst(E e)  將指定元素插入此列表的開頭
void addLast(E e)   將指定元素添加到此列表的結(jié)尾
boolean offer(E e)  將指定元素添加到此列表的末尾(最后一個元素)
boolean offerFirst(E e) 在此列表的開頭插入指定的元素
boolean offerLast(E e)  在此列表末尾插入指定的元素
void push(E e)  將元素推入此列表所表示的堆棧
E element() 獲取但不移除此列表的頭(第一個元素)
E getFirst()    返回此列表的第一個元素
E getLast() 返回此列表的最后一個元素
E peek()    獲取但不移除此列表的頭(第一個元素)
E peekFirst()   獲取但不移除此列表的第一個元素; 如果此列表為空, 則返回 null
E peekLast()    獲取但不移除此列表的最后一個元素; 如果此列表為空, 則返回 null
E poll()    獲取并移除此列表的頭(第一個元素)
E pollFirst()   獲取并移除此列表的第一個元素; 如果此列表為空, 則返回 null
E pollLast()    獲取并移除此列表的最后一個元素; 如果此列表為空, 則返回 null
E pop() 從此列表所表示的堆棧處彈出一個元素
E remove()  獲取并移除此列表的頭(第一個元素)
E removeFirst() 移除并返回此列表的第一個元素
boolean removeFirstOccurrence(Object o) 從此列表中移除第一次出現(xiàn)的指定元素(從頭部到尾部遍歷列表時)
E removeLast()  移除并返回此列表的最后一個元素
boolean removeLastOccurrence(Object o)  從此列表中移除最后一次出現(xiàn)的指定元素(從頭部到尾部遍歷列表時)
Iterator<E> descendingIterator()    返回以逆向順序在此雙端隊列的元素上進行迭代的迭代器

核心函數(shù)實現(xiàn)分析 addAll()：

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

addAll會把集合先轉(zhuǎn)化為數(shù)組》汤铮考慮的是2點：

1. 傳入的集合是對象(引用)袒餐，轉(zhuǎn)化數(shù)組toArray，可以避免過程中谤狡，該集合對象被修改
2. 轉(zhuǎn)化成數(shù)組遍歷灸眼，比在集合中遍歷速度要快，因為集合需要轉(zhuǎn)化成迭代器來遍歷

1.3.1.2 Vector類

(示例: basic.coll.collection.list.VectorDemo)

底層實現(xiàn)與ArrayList結(jié)構(gòu)類似墓懂，操作方法大同小異焰宣，不同點在于：

1. Vector的方法都是用了synchronized，即線程安全的列表容器
2. 擴容捕仔，ArrayList是1.5倍擴容匕积，而Vector有個屬性capacityIncrement定義擴容數(shù)量，如果沒有定義默就是2倍擴容

對于Vector的子類Stack逻澳，Stack棧的特點：先進后出闸天，主要實現(xiàn)了一下幾個方法

1.3.1.4 ArrayList和LinkedList的區(qū)別

ArrayList：通過數(shù)組來實現(xiàn)的，讀取性能很高斜做，隨機訪問時間復(fù)雜度為O(1)苞氮，適用于讀大于寫的場景

LinkedList：通過雙向隊列來實現(xiàn)的，更新效率更高瓤逼，寫只需要修改前后兩個節(jié)點的相關(guān)引用笼吟，但是讀取效率比較低，需要最多遍歷一半長度的隊列霸旗，適用與寫大于讀的場景

    public E push(E item) // 向棧頂(數(shù)組末端)放入元素
    public synchronized E pop() // 彈出棧頂贷帮，移除數(shù)組末端元素，并放回
    public synchronized E peek() // 獲取棧頂元素(數(shù)組末端元素)返回诱告，不會移除

1.3.1.5 RandomAccess接口

查看源碼我們發(fā)現(xiàn)實際上 RandomAccess 接口中什么都沒有定義撵枢。所以，在我看來 RandomAccess 接口不過是一個標識罷了精居。標識什么锄禽？ 標識實現(xiàn)這個接口的類具有隨機訪問功能。

在 binarySearch（）方法中靴姿，它要判斷傳入的list 是否 RamdomAccess 的實例沃但，如果是，調(diào)用indexedBinarySearch（）方法佛吓，如果不是宵晚，那么調(diào)用iteratorBinarySearch（）方法

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 實現(xiàn)了 RandomAccess 接口垂攘， 而 LinkedList 沒有實現(xiàn)。為什么呢淤刃？還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)晒他！ArrayList 底層是數(shù)組，而 LinkedList 底層是鏈表钝凶。數(shù)組天然支持隨機訪問仪芒，時間復(fù)雜度為 O(1)唁影，所以稱為快速隨機訪問耕陷。鏈表需要遍歷到特定位置才能訪問特定位置的元素，時間復(fù)雜度為 O(n)据沈，所以不支持快速隨機訪問哟沫。，ArrayList 實現(xiàn)了 RandomAccess 接口锌介，就表明了他具有快速隨機訪問功能嗜诀。 RandomAccess 接口只是標識，并不是說 ArrayList 實現(xiàn) RandomAccess 接口才具有快速隨機訪問功能的孔祸！

對于 list 的遍歷方式選擇：

1. 實現(xiàn)了 RandomAccess 接口的list隆敢，優(yōu)先選擇普通 for 循環(huán) ，其次 foreach,
2. 未實現(xiàn) RandomAccess接口的list崔慧，優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過iterator實現(xiàn)的,）拂蝎，大size的數(shù)據(jù)，千萬不要使用普通for循環(huán)

1.3.2 Set接口的常用方法

Set接口繼承了Collection接口惶室，在Collection基礎(chǔ)上温自，擴展定義Set的接口規(guī)范。擴展定義的方法：

    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }

AbstractSet 是實現(xiàn) Set 的抽象類皇钞，通過結(jié)合 Iterator 接口約束悼泌，對一些方法的實現(xiàn)。

Set:元素不可以重復(fù), 是無序
|-- HashSet：內(nèi)部數(shù)據(jù)結(jié)構(gòu)是哈希表 , 是不同步的. 
    |-- LinkedHashSet：
|-- TreeSet：可以對Set集合中的元素進行排序. 是不同步的.  

由于Set集合中不允許存在重復(fù)值, 因此可以使用Set集合中的addAll()方法, 將Collection集合添加到Set集合中并除掉重復(fù)值

由于Set集合中的對象時無序的, 遍歷Set結(jié)合的結(jié)果與插入Set集合的順序并不相同

一夹界、如何保證該集合的元素唯一性呢馆里？

是通過對象的hashCode和equals方法來完成對象唯一性的.

1. 如果對象的hashCode值不同, 那么不用判斷equals方法, 就直接存儲到哈希表中.
2. 如果對象的hashCode值相同, 那么要再次判斷對象的equals方法是否為true. 如果為true, 視為相同元素, 不存. 如果為false, 那么視為不同元素, 就進行存儲.

記住: 如果元素要存儲到HashSet集合中, 必須覆蓋hashCode方法和equals方法.

一般情況下, 如果定義的類會產(chǎn)生很多對象, 比如人, 學(xué)生, 書, 通常都需要覆蓋equals, hashCode方法.

二、建立對象判斷是否相同的依據(jù)

if (this.hashCode() == obj.hashCode() && this.equals(obj))

三可柿、哈希表確定元素是否相同

1. 判斷的是兩個元素的哈希值是否相同鸠踪。如果相同，在判斷兩個對象的內(nèi)容是否相同趾痘。
2. 判斷哈希值相同慢哈，其實判斷的是對象的hashCode的方法。判斷內(nèi)容相同永票，用的是equals方法卵贱。如果哈希值不同滥沫，就不需要判斷equals

四、判斷元素唯一性的方式

就是根據(jù)比較方法的返回結(jié)果是否是0键俱，是0兰绣，就是相同元素，不存编振。

五缀辩、TreeSet對元素進行排序的 兩種方式

1. 讓元素自身具備比較功能，元就需要實現(xiàn)Comparable接口踪央，覆蓋compareTo方法臀玄。如果不要按照對象中具備的自然順序進行排序。如果對象中不具備自然順序畅蹂。怎么辦健无？
2. 讓集合自身具備比較功能，定義一個類實現(xiàn)Comparator接口液斜，覆蓋compare方法累贤。將該類對象作為參數(shù)傳遞給TreeSet集合的構(gòu)造函數(shù)。

1.3.2.1 HashSet類

(示例: basic.coll.collection.set.HashSetDemo)

底層數(shù)據(jù)結(jié)構(gòu)：采用HashMap的鍵少漆，來作為對象的存儲容器臼膏，允許null。因為Map的key不能重復(fù)示损，所以自然Set就不允許存在重復(fù)的元素渗磅。所以存儲元素的時候, 使用的元素的hashCode方法來確定位置, 如果位置相同, 在通過元素的equals來確定是否相同。

1.3.2.2 LinkedHashSet類(HashSet的子類)

(示例: basic.coll.collection.set.LinkedHashSetDemo)

底層數(shù)據(jù)結(jié)構(gòu)： 與HashSet類似屎媳，除了底層數(shù)據(jù)結(jié)構(gòu)是采用LinkedHashMap夺溢。所以是有序的

1.3.2.3 TreeSet類

(示例: basic.coll.collection.set.TreeSetDemo)

1. 底層實現(xiàn): 紅黑樹(自平衡的排序二叉樹)。底層基于TreeMap的NavigableSet保存數(shù)據(jù), 其中對象作為map的key, 所以不允許存在重復(fù)的鍵, 所以Set不可重復(fù). HashSet集合數(shù)據(jù)結(jié)構(gòu)是哈希表, 所以存儲元素的時候, 使用的元素的hashCode方法來確定位置, 如果位置相同, 在通過元素的equals來確定是否相同烛谊。允許null
2. 優(yōu)點: 刪除和插入效率高
3. 缺點: 檢索元素效率低
4. 語法: TreeSet<Object> list = new TreeSet<Object>();

方法(只列出基于Set擴展的):

構(gòu)造  
TreeSet()   構(gòu)造一個新的空set, 該set根據(jù)其元素的自然順序進行排序
    TreeSet(NavigableMap<E,Object> m)   
    TreeSet(Comparator<? super E> comparator)   構(gòu)造一個新的空TreeSet, 它根據(jù)指定比較器進行排序
    TreeSet(Collection<? extends E> c)  構(gòu)造一個包含指定collection元素的新 TreeSet, 它按照其元素的自然順序進行排序
    TreeSet(SortedSet<E> s) 構(gòu)造一個與指定有序set具有相同映射關(guān)系和相同排序的新TreeSet
獲取
    Iterator<E> descendingIterator()    返回在此set元素上按降序進行迭代的迭代器
    NavigableSet<E> descendingSet() 返回此set中所包含元素的逆序視圖
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)  返回此set的部分視圖, 其元素范圍從fromElement到toElement
    NavigableSet<E> headSet(E toElement, boolean inclusive) 返回此set的部分視圖, 其元素小于(或等于, 如果inclusive為true)toElement
    NavigableSet<E> tailSet(E fromElement, boolean inclusive)   返回此set的部分視圖, 其元素大于(或等于, 如果inclusive為true)fromElement
    SortedSet<E> subSet(E fromElement, E toElement) 返回此set的部分視圖, 其元素從fromElement(包括)到toElement(不包括)
    SortedSet<E> headSet(E toElement)   返回此set的部分視圖, 其元素嚴格小于toElement
    SortedSet<E> tailSet(E fromElement) 返回此set的部分視圖, 其元素大于等于fromElement
    Comparator<? super E> comparator()  返回對此set中的元素進行排序的比較器; 如果此set使用其元素的自然順序, 則返回null
    E first()   返回此set中當(dāng)前第一個(最低)元素
    E last()    返回此set中當(dāng)前最后一個(最高)元素
    E lower(E e)    返回此set中嚴格小于給定元素的最大元素; 如果不存在這樣的元素, 則返回 null
    E floor(E e)    返回此 set 中小于等于給定元素的最大元素; 如果不存在這樣的元素, 則返回 null
    E ceiling(E e)  返回此 set 中大于等于給定元素的最小元素; 如果不存在這樣的元素, 則返回 null
    E higher(E e)   返回此 set 中嚴格大于給定元素的最小元素; 如果不存在這樣的元素, 則返回 null
    E pollFirst()   獲取并移除第一個(最低)元素; 如果此set為空, 則返回null
    E pollLast()    獲取并移除最后一個(最高)元素; 如果此set為空, 則返回 null
    Object clone()  返回TreeSet實例的淺表副本, 淺克隆

1.3.3 Collection泛型

JDK1.5 出現(xiàn)的安全機制, 不用 <> 就是 Object 類型

一风响、好處:

1. 將運行時期的問題ClassCastException轉(zhuǎn)到了編譯時期(編寫代碼時期)
2. 避免了強制轉(zhuǎn)換的麻煩

二、泛型<>什么時候用?(泛型類同理)

當(dāng)操作的引用數(shù)據(jù)類型不確定的時候丹禀，就使用<>状勤。將要操作的引用數(shù)據(jù)類型傳入即可，其實<>就是一個用于接收具體引用數(shù)據(jù)類型的參數(shù)范圍

注意在程序中双泪，只要用到了帶有<>的類或者接口持搜，就要明確傳入的具體引用數(shù)據(jù)類型

泛型技術(shù)是給編譯器使用的技術(shù)，用于編譯時期焙矛。確保了類型的安全葫盼。運行時。會將泛型去掉村斟，生成的 class 文件中是不帶泛型的贫导，這個稱為泛型的擦除抛猫，為了兼容運行的類加載器，所以擦除

泛型的補償：在運行時孩灯，通過獲取元素的類型進行轉(zhuǎn)換動作闺金，不用使用者再強制轉(zhuǎn)換了

三、泛型的通配符: ? 未知類型(定義泛型函數(shù)時候)

• ? extends E：接收E類型或者E的子類型對象(上限). 一般存儲對象的時候用. 比如 添加元素 addAll
• ? super E：接收E類型或者E的父類型對象(下限). 一般取出對象的時候用. 比如 比較器

1.3.3.4 使用Collection技巧

需要唯一嗎?
    |-- 需要: set
        |-- 需要制定順序嗎?
            |-- 需要: TreeSet
            |-- 不需要: HashSet, 但是想要一個和存儲一致的順序(有序) : LinkedHashSet
    |-- 不需要: List
        |-- 需要頻繁增刪嗎峰档？
            |-- 需要: LinkedList
            |-- 不需要: ArrayList

1. 前綴名: 集合的數(shù)據(jù)結(jié)構(gòu): Array败匹、Linked、Hash讥巡、Tree
2. 后綴名: 集合所屬的體系: List掀亩、Set

一、記憶方法

1. array: 數(shù)組尚卫；查詢快归榕，有角標
2. linked: 鏈表；增刪快吱涉，add、get外里、remove + first last 方法
3. hash: 哈希表怎爵；唯一性，元素需要覆蓋 hashcode 方法和 equals 方法
4. tree: 二叉樹盅蝗；排序鳖链，兩個接口: Comparable、Comparator

而且通常這些常用的集合容器都是不同步的

二墩莫、顯示數(shù)據(jù)的2種方式

1).迭代器: Iterator(3個方法) [Collection子類用的]

    Iterator<String> lts = s.iterator();
    while (lts.hasNext()) {
        System.out.println(lts.next());
    }

2).枚舉: Enumeration(2個方法) [Vector使用的]

    1).boolean hasMoreElements()        
    2).Object nextElement()
        Enumeration<String> en = v.elements();
        while(en.hasMoreElements()){
            System.out.println("en.nextElement(): " + en.nextElement());
        }

3).Iterator 和 Enumeration 的區(qū)別

Iterator 是用來替代 Enumeration 的芙委，Enumeration 中只定義了兩個方法，不具備刪除功能狂秦。

4).調(diào)用 next() 方法后才可以調(diào)用 remove() 方法

而且每次調(diào)用 next() 后最多只能調(diào)用一次 remove() 方法灌侣，否則拋出IllegalStateException異常。

1.4 Map - 雙列集合

Map一次添加一對元素<K,V>裂问，存儲的是鍵值對侧啼，保證鍵的唯一性。Map接口提供了將鍵映射到值得對象堪簿，一個映射不能包含重復(fù)的鍵痊乾，每個鍵最多只能映射到一個值。Map是雙列集合的頂層定義椭更，HashMap與TreeMap都實現(xiàn)Map

Map常用的子類
    |-- Hashtable：內(nèi)部結(jié)構(gòu)是哈希表, 是同步的. 不允許null作為鍵, null作為值. 
        |-- Properties：用來存儲鍵值對型的配置文件的信息, 可以和IO技術(shù)相結(jié)合.  
    |-- HashMap：內(nèi)部結(jié)構(gòu)是哈希表, 不是同步的. 允許null作為鍵, null作為值. 無序
        |-- LinkedHashMap：有序哈希Map
    |-- TreeMap：內(nèi)部結(jié)構(gòu)是二叉樹, 不是同步的. 可以對Map集合中的鍵進行排序. 

接口定義如下：

添加：
    V put(K key, V value)   向集合中添加指定的key與value的映射關(guān)系
    void putAll(Map<? extends K, ? extends V> m)    添加一個map集合進去
刪除：
    V remove(Object key)    根據(jù)指定的key刪除這個鍵值對
    boolean remove(Object key, Object value)    JDK1.8, 子類實現(xiàn)
    void clear()    清空map集合
判斷：
    boolean containsKey(Object key) 如果此映射包含指定鍵的映射關(guān)系, 則返回true
    boolean containsValue(Object value) 如果此映射將一個或多個鍵映射到指定值, 則返回true
    boolean equals(Object o)    比較的是元素是否相同
    boolean isEmpty()   判斷集合是否有元素
獲饶纳蟆：
    int size()  獲取鍵值對的個數(shù)
    V get(Object key)   如果存在指定的鍵對象, 則返回該對象對應(yīng)的值, 否則返回null
    default V getOrDefault(Object key, V defaultValue)
    Set<K> keySet() 返回該集合中的所有鍵對象組成的Set集合
    Collection<V> values()  返回該集合中所有值對象形成的Collection集合
    Set<Map.Entry<K, V>> entrySet() 
    default void forEach(BiConsumer<? super K, ? super V> action)
JDK1.8：子類實現(xiàn)  
    default V replace(K key, V value)   
    default boolean replace(K key, V oldValue, V newValue)  
    default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 
    default V putIfAbsent(K key, V value)   
    default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)  
    default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)  
    default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)   
    default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)    
Map的內(nèi)部接口Entry定義：
interface Entry<K,V> {
    K getKey();
    V getValue();
    V setValue(V value);
    boolean equals(Object o);
    int hashCode();
    
    public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
        return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getKey().compareTo(c2.getKey());
    }
    public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
        return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getValue().compareTo(c2.getValue());
    }
    public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
        Objects.requireNonNull(cmp);
        return (Comparator<Map.Entry<K, V>> & Serializable)  (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
    }
    public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
        Objects.requireNonNull(cmp);
        return (Comparator<Map.Entry<K, V>> & Serializable)  (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
    }
}

1.4.1 Map接口的實現(xiàn)類

Map 接口常用的實現(xiàn)類有 HashMap 和 TreeMap，通常建議使用 HashMap 實現(xiàn)類實現(xiàn) Map 集合虑瀑，因為由 HashMap 類實現(xiàn)的 Map 集合對于添加和刪除映射關(guān)系效率更高湿滓。

HashMap 是基于哈希表的Map接口的實現(xiàn)畏腕，HashMap 通過哈希嗎對其內(nèi)部的映射關(guān)系進行快速查找。由 HashMap 類實現(xiàn)的 Map 集合對于添加或刪除映射關(guān)系效率較高茉稠。而 TreeMap 中的映射關(guān)系存在一定的順序描馅，如果希望 Map 集合中的對象存在一定的順序，應(yīng)該使用 TreeMap 類實現(xiàn) Map 集合而线。

1.4.1.1 HashMap類

(basic.coll.map.HashMapDemo)

該類基于哈希表的Map接口的實現(xiàn)铭污，此實現(xiàn)提供所有可選的映射操作，并允許使用 null值 和 null鍵膀篮，但必須保證鍵的唯一性嘹狞。 HashMap通過哈希對其內(nèi)部的映射關(guān)系進行快速查找，此類不保證映射的順序誓竿，特別是不保證該順序恒久不變(無序)磅网。

1. 底層實現(xiàn): Node<K, V> implements Map.Entry<K,V> 內(nèi)置對象實現(xiàn)(鏈表) + 數(shù)組的方式。JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的筷屡，數(shù)組是HashMap的主體涧偷，鏈表則是主要為了解決哈希沖突而存在的(拉鏈法解決沖突)。JDK1.8 以后在解決哈希沖突時有了較大的變化毙死，當(dāng)鏈表長度大于閾值(默認為8)時燎潮，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間
2. 語法: HashMap<K, V> list = new HashMap<K, V>()

方法(只列出基于Map擴展的扼倘，JDK1.8方法均由該類實現(xiàn))：

構(gòu)造
    HashMap()   構(gòu)造一個具有默認初始容量(16)和默認加載因子(0.75)的空HashMap
    HashMap(int initialCapacity)    構(gòu)造一個帶指定初始容量和默認加載因子(0.75)的空HashMap
    HashMap(int initialCapacity, float loadFactor)  構(gòu)造一個帶指定初始容量和加載因子的空HashMap
    HashMap(Map<? extends K, ? extends V> m)    構(gòu)造一個映射關(guān)系與指定Map相同的新HashMap
獲取
    V getOrDefault(Object key, V defaultValue)  JDK1.8
    void forEach(BiConsumer<? super K, ? super V> action)   JDK1.8
刪除
    boolean remove(Object key, Object value)    JDK1.8
JDK1.8  V replace(K key, V value)   
    boolean replace(K key, V oldValue, V newValue)
    void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
    V putIfAbsent(K key, V value)   
    V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
    V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
    V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
    V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)
克隆
    Object clone()  淺克隆

1.4.1.2 TreeMap類

(basic.coll.map.TreeMapDemo)

1. 底層實現(xiàn)：紅黑樹（自平衡的排序二叉樹）

該類不僅實現(xiàn)了Map接口确封，還實現(xiàn)了 java.util.SortedMap 接口。因此集合中的映射關(guān)系具有一定的順序再菊。但在添加爪喘、刪除和定位映射關(guān)系上，TreeMap類比HashMap性能差一點纠拔。

由于 TreeMap 類實現(xiàn)的 Map集合 中的映射關(guān)系是根據(jù)鍵對象按照一定的順序(字典排序)排列的秉剑，因此 不允許鍵對象 是 null

可以通過HashMap類創(chuàng)建Map集合，當(dāng)需要順序輸出時绿语，再創(chuàng)建一個完成相同映射關(guān)系的TreeMap類實例
方法(只列出基于Map擴展的秃症，JDK1.8方法均由該類實現(xiàn))：

構(gòu)造
    TreeMap ()  使用鍵的自然順序構(gòu)造一個新的、空的樹映射
    TreeMap(Comparator<? super K> comparator)   構(gòu)造一個新的吕粹、空的樹映射, 該映射根據(jù)給定比較器進行排序
    TreeMap(Map<? extends K, ? extends V> m)    構(gòu)造一個與給定映射具有相同映射關(guān)系的新的樹映射, 該映射根據(jù)其鍵的自然順序進行排序
    TreeMap(SortedMap<K, ? extends V> m)    構(gòu)造一個與指定有序映射具有相同映射關(guān)系和相同排序順序的新的樹映射
獲取
    Map.Entry<K,V> firstEntry() 返回一個與此映射中的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系; 如果映射為空, 則返回null
    K firstKey()    返回此映射中當(dāng)前第一個(最低)鍵
    Map.Entry<K,V> lastEntry()  返回與此映射中的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系; 如果映射為空, 則返回null
    K lastKey() 返回映射中當(dāng)前最后一個(最高)鍵
    Map.Entry<K,V> pollFirstEntry() 移除并返回與此映射中的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系; 如果映射為空, 則返回null
    Map.Entry<K,V> pollLastEntry()  移除并返回與此映射中的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系; 如果映射為空, 則返回null
    Map.Entry<K,V> floorEntry(K key)    返回一個鍵-值映射關(guān)系, 它與小于等于給定鍵的最大鍵關(guān)聯(lián); 如果不存在這樣的鍵, 則返回 null
    K floorKey(K key)   返回小于等于給定鍵的最大鍵; 如果不存在這樣的鍵, 則返回null
    Map.Entry<K,V> ceilingEntry(K key)  返回一個鍵-值映射關(guān)系, 它與大于等于給定鍵的最小鍵關(guān)聯(lián); 如果不存在這樣的鍵, 則返回 null
    K ceilingKey(K key) 返回大于等于給定鍵的最小鍵; 如果不存在這樣的鍵, 則返回null
    Map.Entry<K,V> higherEntry(K key)   返回一個鍵-值映射關(guān)系, 它與嚴格大于給定鍵的最小鍵關(guān)聯(lián); 如果不存在這樣的鍵, 則返回null
    K higherKey(K key)  返回嚴格大于給定鍵的最小鍵; 如果不存在這樣的鍵, 則返回null
    Map.Entry<K,V> lowerEntry(K key)    返回一個鍵-值映射關(guān)系, 它與嚴格小于給定鍵的最大鍵關(guān)聯(lián); 如果不存在這樣的鍵, 則返回null
    K lowerKey(K key)   返回嚴格小于給定鍵的最大鍵; 如果不存在這樣的鍵, 則返回nul
    Comparator<? super K> comparator()  返回對此映射中的鍵進行排序的比較器; 如果此映射使用鍵的自然順序, 則返回null
    NavigableSet<K> navigableKeySet()   返回此映射中所包含鍵的NavigableSet視圖
    NavigableSet<K> descendingKeySet()  返回此映射中所包含鍵的逆序NavigableSet視圖
    NavigableMap<K, V> descendingMap()  返回此映射中所包含映射關(guān)系的逆序視圖
    SortedMap<K,V> headMap(K toKey) 返回此映射的部分視圖, 其鍵值嚴格小于toKey
    NavigableMap<K,V> headMap(K toKey, boolean inclusive)   返回此映射的部分視圖, 其鍵小于(或等于, 如果inclusive為true)toKey
    SortedMap<K,V> tailMap(K fromKey)   返回此映射的部分視圖, 其鍵大于等于fromKey
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) 返回此映射的部分視圖, 其鍵大于(或等于, 如果inclusive為true)fromKey
    SortedMap<K,V> subMap(K fromKey, K toKey)   返回此映射的部分視圖, 其鍵值的范圍從fromKey(包括)到toKey(不包括)
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)    返回此映射的部分視圖, 其鍵的范圍從fromKey到toKey
    void forEach(BiConsumer<? super K, ? super V> action)   JDK1.8
JDK1.8
    V replace(K key, V value)   
    boolean replace(K key, V oldValue, V newValue)
    void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
克隆
    Object clone()  返回此TreeMap實例的淺表副本,  淺克隆

1.4.1.3 Hashtable類

(basic.coll.map.HashtableDemo)

此類實現(xiàn)一個哈希表种柑，該哈希表將鍵映射到相應(yīng)的值。任何 非null對象 都可以用作鍵或值匹耕。為了成功地在哈希表中存儲和獲取對象聚请，用作鍵的對象必須實現(xiàn) hashCode 方法和 equals 方法。所有方法均加了 synchronized(即同步)

1. 底層實現(xiàn): Node<K, V> implements Map.Entry<K,V> 內(nèi)置對象實現(xiàn)(鏈表) + 數(shù)組的方式

方法(只列出基于Map擴展的，JDK1.8方法均由該類實現(xiàn))：

構(gòu)造
    Hashtable() 用默認的初始容量(11)和加載因子(0.75)構(gòu)造一個新的空哈希表
    Hashtable(int initialCapacity)  用指定初始容量和默認的加載因子(0.75)構(gòu)造一個新的空哈希表
    Hashtable(int initialCapacity, float loadFactor)    用指定初始容量和指定加載因子構(gòu)造一個新的空哈希表
    Hashtable(Map<? extends K, ? extends V> t)  構(gòu)造一個與給定的Map具有相同映射關(guān)系的新哈希表
獲取
    synchronized Enumeration<K> keys()  返回此哈希表中的鍵的枚舉
    synchronized Enumeration<V> elements()  返回此哈希表中的值的枚舉
    synchronized Object clone() 創(chuàng)建此哈希表的淺表副本, 淺克隆
    synchronized String toString()  返回此Hashtable對象的字符串表示形式, 其形式為ASCII字符","(逗號加空格)分隔開的驶赏、括在括號中的一組條目
    synchronized boolean equals(Object o)   按照Map接口的定義, 比較指定Object與此Map是否相等
    synchronized int hashCode() 按照Map接口的定義, 返回此Map的哈希碼值
JDK1.8  synchronized V getOrDefault(Object key, V defaultValue)
    synchronized void forEach(BiConsumer<? super K, ? super V> action)
    synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
    synchronized V putIfAbsent(K key, V value)
    synchronized boolean remove(Object key, Object value)
    synchronized boolean replace(K key, V oldValue, V newValue)
    synchronized V replace(K key, V value)
    synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
    synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 
    synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
    synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)   

1.4.1.4 Properties(Hashtable子類)

(basic.coll.map.PropertiesDemo)

Properties類表示了一個持久的屬性集炸卑。Properties可保存在流中或從流中加載

特點：

1. 該集合中的鍵和值都是字符串類型
2. 集合中的數(shù)據(jù)可以保存到流中，或從流中獲取

通過該集合用于操作以鍵值對形式存在配置文件

構(gòu)造
    Properties()    創(chuàng)建一個無默認值的空屬性列表
    Properties(Properties defaults) 創(chuàng)建一個帶有指定默認值的空屬性列表
操作
    String getProperty(String key)  用指定的鍵在此屬性列表中搜索屬性
    String getProperty(String key, String defaultValue) 用指定的鍵在屬性列表中搜索屬性
    synchronized Object setProperty(String key, String value)   調(diào)用 Hashtable 的方法 put
獲取
    Enumeration<?> propertyNames()  返回屬性列表中所有鍵的枚舉, 如果在主屬性列表中未找到同名的鍵, 則包括默認屬性列表中不同的鍵
    Set<String> stringPropertyNames()   返回此屬性列表中的鍵集, 其中該鍵及其對應(yīng)值是字符串, 如果在主屬性列表中未找到同名的鍵, 則還包括默認屬性列表中不同的鍵
其他
    synchronized void load(Reader reader)   按簡單的面向行的格式從輸入字符流中讀取屬性列表(鍵和元素對)
    synchronized void load(InputStream inStream)    從輸入流中讀取屬性列表(鍵和元素對)
    void save(OutputStream out, String comments)    已過時, 如果在保存屬性列表時發(fā)生I/O錯誤, 則此方法不拋出IOException. 保存屬性列表的首選方法是通過store(OutputStream out, String comments)方法或storeToXML(OutputStream os, String comment)方法來進行
    void store(Writer writer, String comments)  以適合使用load(Reader)方法的格式, 將此Properties表中的屬性列表(鍵和元素對)寫入輸出字符
    void store(OutputStream out, String comments)   以適合使用load(InputStream)方法加載到Properties表中的格式, 將此Properties表中的屬性列表(鍵和元素對)寫入輸出流
    synchronized void loadFromXML(InputStream in)   將指定輸入流中由XML文檔所表示的所有屬性加載到此屬性表中
    void storeToXML(OutputStream os, String comment)    發(fā)出一個表示此表中包含的所有屬性的XML文檔
    void storeToXML(OutputStream os, String comment, String encoding)   使用指定的編碼發(fā)出一個表示此表中包含的所有屬性的XML文檔
    void list(PrintStream out)  將屬性列表輸出到指定的輸出流
    void list(PrintWriter out)  將屬性列表輸出到指定的輸出流

因為Properties繼承于 Hashtable煤傍，所以可以對 Properties 對象應(yīng)用 put 和 putAll 方法想际。不建議使用這兩個方法持痰，因為它們允許調(diào)用者插入其鍵或值不是 String 的項叫潦，相反應(yīng)該使用 setProperty 方法弟断。如果在不安全的 Properties 對象(即包含 非String 的鍵或值)上調(diào)用 store 或 save 方法，則該調(diào)用將失敗

類似地龄恋，如果在不安全的 Properties 對象(即包含 非String 的鍵)上調(diào)用 propertyNames 或 list 方法疙驾，則該調(diào)用將失敗

load(Reader) / store(Writer, String)方法按下面所指定的、簡單的面向行的格式在基于字符的流中加載和存儲屬性. 除了輸入/輸出流使用ISO 8859-1字符編碼外郭毕，load(InputStream) / store(OutputStream, String) 方法與 load(Reader) / store(Writer, String) 對的工作方式完全相同它碎。可以使用 Unicode 轉(zhuǎn)義來編寫此編碼中無法直接表示的字符显押；轉(zhuǎn)義序列中只允許單個'u'字符扳肛。可使用 native2ascii 工具對屬性文件和其他字符編碼進行相互轉(zhuǎn)換

loadFromXML(InputStream) 和 storeToXML(OutputStream, String, String) 方法按簡單的 XML 格式加載和存儲屬性煮落。默認使用 UTF-8 字符編碼敞峭，但如果需要，可以指定某種特定的編碼蝉仇。XML 屬性文檔具有以下DOCTYPE聲明:

<!DOCTYPE properties SYSTEM "http://java.sun.com/dtd/properties.dtd">

1.4.1.5 LinkedHashMap(HashMap子類)

(basic.coll.map.LinkedHashMapDemo)

1. 底層實現(xiàn): LinkedHashMap 繼承自 HashMa，所以它的底層仍然是基于拉鏈式散列結(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成殖蚕。另外 LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上轿衔，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序睦疫。同時通過對鏈表進行相應(yīng)的操作害驹，實現(xiàn)了訪問順序相關(guān)邏輯。

Map 接口的哈希表和鏈接列表實現(xiàn)蛤育，具有可預(yù)知的迭代順序宛官。此實現(xiàn)與 HashMap 的不同之處在于：該類維護著一個運行于所有條目的雙重鏈接列表，是有序的 HashMap

方法(只列出基于Map擴展的瓦糕，JDK1.8方法均由該類實現(xiàn))：

構(gòu)造
    LinkedHashMap() 構(gòu)造一個帶默認初始容量(16)和加載因子(0.75)的空插入順序LinkedHashMap實例
    LinkedHashMap(int initialCapacity)  構(gòu)造一個帶指定初始容量和默認加載因子(0.75)的空插入順序LinkedHashMap實例
    LinkedHashMap(int initialCapacity, float loadFactor)    構(gòu)造一個帶指定初始容量和加載因子的空插入順序LinkedHashMap實例
    LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)   構(gòu)造一個映射關(guān)系與指定映射相同的插入順序LinkedHashMap實例
    LinkedHashMap(Map<? extends K, ? extends V> m)  構(gòu)造一個帶指定初始容量底洗、加載因子和排序模式的空LinkedHashMap實例

1.4.2 遍歷Map數(shù)據(jù)總結(jié)

一、Collection方法咕娄，只遍歷value

    Collection<String> values = m1.values();
    Iterator<String> it1 = values.iterator();
    while (it1.hasNext()) {
        System.out.println(it1.next());
    }

二亥揖、keySet方法(取出map中的所有元素)

原理：通過 keySet() 獲取 Map 中所有的鍵所在的 Set 集合，再通過 Set 的迭代器獲取到每一個鍵，再對每一個鍵通過 Map 集合的 get(String key) 獲取其對應(yīng)的值即可费变。

    Set<Integer> keySet = m1.keySet();
    Iterator<Integer> its = keySet.iterator();
    while (its.hasNext()) {
        Integer key = its.next();
        String value = m1.get(key);
        System.out.print("{key=" + key + ", value=" + value + "},");
    }

三摧扇、entrySet方法，效率最高

通過 Map 轉(zhuǎn)成 Set 就可以迭代挚歧。找到了另一個方法 entrySet()扛稽。該方法將鍵和值的映射關(guān)系作為對象存儲到了Set集合中，而這個映射關(guān)系的類型就是 Map.Entry 類型

    Set<Map.Entry<Integer, String>> entrySet = m1.entrySet();
    Iterator<Map.Entry<Integer, String>> it = entrySet.iterator();
    while (it.hasNext()) {
        Map.Entry<Integer, String> me = it.next();
        Integer key = me.getKey();
        String value = me.getValue();
        System.out.print("{key=" + key + ", value=" + value + "},");
    }

四滑负、JDK1.8 新特性在张，forEach方法

    m1.forEach((key, value) -> {
        System.out.print("{key=" + key + ", value=" + value + "},");
    });

1.3 Collections(集合框架工具類)

(basic.coll.CollectionsDemo)

此類完全由在 collection 上進行操作或返回 collection 的靜態(tài)方法組成。它包含在collection上操作的多態(tài)算法橙困，即包裝器瞧掺，包裝器返回由指定 collection 支持的 新collection，以及少數(shù)其他內(nèi)容

方法(均為static靜態(tài)方法)    說明
<T extends Comparable<? super T>> void sort(List<T> list)
    根據(jù)元素的自然順序, 對指定列表按升序進行排序
<T> void sort(List<T> list, Comparator<? super T> c)
    根據(jù)指定比較器產(chǎn)生的順序?qū)χ付斜磉M行排序
    
<T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
    使用二分搜索法搜索指定列表, 以獲得指定對象
<T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
    使用二分搜索法搜索指定列表, 以獲得指定對象
    
void reverse(List<?> list)    反轉(zhuǎn)指定列表中元素的順序
void shuffle(List<?> list)    使用默認隨機源對指定列表進行置換
void shuffle(List<?> list, Random rnd)    使用指定的隨機源對指定列表進行置換
void swap(List<?> list, int i, int j)     在指定列表的指定位置處交換元素

<T> void fill(List<? super T> list, T obj)
    使用指定元素替換指定列表中的所有元素
    
<T> void copy(List<? super T> dest, List<? extends T> src)
    將所有元素從一個列表復(fù)制到另一個列表
    
<T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
    根據(jù)元素的自然順序, 返回給定collection的最小元素

<T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
    根據(jù)指定比較器產(chǎn)生的順序, 返回給定collection的最小元素
    
<T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
    根據(jù)元素的自然順序, 返回給定collection的最大元素

<T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
    根據(jù)指定比較器產(chǎn)生的順序, 返回給定collection的最大元素

void rotate(List<?> list, int distance)
    根據(jù)指定的距離輪換指定列表中的元素

<T> boolean replaceAll(List<T> list, T oldVal, T newVal)
    使用另一個值替換列表中出現(xiàn)的所有某一指定值

int indexOfSubList(List<?> source, List<?> target)
    返回指定源列表中第一次出現(xiàn)指定目標列表的起始位置; 如果沒有出現(xiàn)這樣的列表, 則返回 -1
int lastIndexOfSubList(List<?> source, List<?> target)
    返回指定源列表中最后一次出現(xiàn)指定目標列表的起始位置; 如果沒有出現(xiàn)這樣的列表, 則返回 -1

<T> Collection<T> unmodifiableCollection(Collection<? extends T> c)
    返回指定collection的不可修改視圖
<T> Set<T> unmodifiableSet(Set<? extends T> s)
    返回指定set的不可修改視圖
<T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)
    返回指定有序set的不可修改視圖
<T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s)
<T> List<T> unmodifiableList(List<? extends T> list)
    返回指定列表的不可修改視圖
<K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m)
    返回指定映射的不可修改視圖
<K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m)
    返回指定有序映射的不可修改視圖
<K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m)    

<T> Collection<T> synchronizedCollection(Collection<T> c)
    返回指定collection支持的同步(線程安全的)collection
<T> Set<T> synchronizedSet(Set<T> s)
    返回指定set支持的同步(線程安全的)set
<T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
    返回指定有序 set 支持的同步(線程安全的)有序set
<T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s)
<T> List<T> synchronizedList(List<T> list)
    返回指定列表支持的同步(線程安全的)列表
<K,V> Map<K,V> synchronizedMap(Map<K,V> m)
    返回由指定映射支持的同步(線程安全的)映射
<K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
    返回指定有序映射支持的同步(線程安全的)有序映射
<K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m)

<E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)
    返回指定collection的一個動態(tài)類型安全視圖
<E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type)
<E> Set<E> checkedSet(Set<E> s, Class<E> type)
    返回指定set的一個動態(tài)類型安全視圖
<E> SortedSet<E> checkedSortedSet(SortedSet<E> s, Class<E> type)
    返回指定有序set的一個動態(tài)類型安全視圖
<E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s, Class<E> type)
<E> List<E> checkedList(List<E> list, Class<E> type)
    返回指定列表的一個動態(tài)類型安全視圖
<K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType)
    返回指定映射的一個動態(tài)類型安全視圖
<K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, Class<K> keyType, Class<V> valueType)
    返回指定有序映射的一個動態(tài)類型安全視圖
<K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K, V> m, Class<K> keyType, Class<V> valueType) 

<T> Iterator<T> emptyIterator() 
<T> ListIterator<T> emptyListIterator() 
<T> Enumeration<T> emptyEnumeration()   
<T> Set<T> emptySet()             返回空的set(不可變的)
<E> SortedSet<E> emptySortedSet()   
<E> NavigableSet<E> emptyNavigableSet() 
final <T> List<T> emptyList()      返回空的列表(不可變的)
final <K,V> Map<K,V> emptyMap() 返回空的映射(不可變的)
final <K,V> SortedMap<K,V> emptySortedMap()
final <K,V> NavigableMap<K,V> emptyNavigableMap()

<T> Set<T> singleton(T o)         返回一個只包含指定對象的不可變set
<T> List<T> singletonList(T o)  返回一個只包含指定對象的不可變列表
<K,V> Map<K,V> singletonMap(K key, V value)
    返回一個不可變的映射, 它只將指定鍵映射到指定值
    
<T> List<T> nCopies(int n, T o)
    返回由指定對象的n個副本組成的不可變列表
    
<T> Comparator<T> reverseOrder()
    返回一個比較器, 它強行逆轉(zhuǎn)實現(xiàn)了Comparable接口的對象collection的自然順序
<T> Comparator<T> reverseOrder(Comparator<T> cmp)
    返回一個比較器, 它強行逆轉(zhuǎn)指定比較器的順序
    
<T> Enumeration<T> enumeration(final Collection<T> c)
    返回一個指定collection上的枚舉
    
<T> ArrayList<T> list(Enumeration<T> e)
    返回一個數(shù)組列表, 它按返回順序包含指定枚舉返回的元素
    
int frequency(Collection<?> c, Object o)
    返回指定collection中等于指定對象的元素數(shù)
boolean disjoint(Collection<?> c1, Collection<?> c2)
    如果兩個指定collection中沒有相同的元素, 則返回true
    
<T> boolean addAll(Collection<? super T> c, T... elements)
    將所有指定元素添加到指定collection中
    
<E> Set<E> newSetFromMap(Map<E, Boolean> map)
    返回指定映射支持的 set
    
<T> Queue<T> asLifoQueue(Deque<T> deque)
    以后進先出(Lifo) Queue的形式返回某個Deque的視圖