集合-有解無憂

原文鏈接http://zhhll.icu/2020/05/11/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/java%E5%9F%BA%E7%A1%80%E4%B9%8B%E9%9B%86%E5%90%88/

有時候需要存盤一組資料，之前使用陣列，但是陣列具有固定的容量，但是在寫程式時并不知道需要多少物件，在java.util包下提供了一套完整的集合類，包含List、Set、Queue、Map，java集合類都可以自動的調整自己的大小，

再創建集合時，經常使用泛型，可以在編譯期防止將錯誤的型別放入到集合中，

集合概念

集合分為兩個基本介面

集合(Collection)：一個獨立元素的序列，List必須已插入順序保存元素，Set不能包含重復元素，Queue按照排隊規則來確定物件產生的順序（一般是插入順序）
映射(Map)：一組成對的"鍵值對"物件，允許使用鍵來查找值，map允許我們使用一個物件來查找另一個物件

Arrays.asList()的輸出是一個List，但是底層實作是陣列，沒法調整大小，
```
List<String> list = Arrays.asList("123","234");
list.add("345");//java.lang.UnsupportedOperationException
```

List

存盤有序，可以重復的元素，相當于動態陣列
集合中元素所在類要重寫equals方法

ArrayList
LinkedList
Vector

兩種型別的list

ArrayList：擅長隨機訪問元素，但在List中間插入和洗掉元素時速度較慢
LinkedList：擅長在List中間進行插入和洗掉操作，提供了優化的順序訪問，對于隨機訪問相對較慢

List特性

允許插入重復元素
允許插入多個null元素
List提供了ListIterator迭代器，可以提供雙向訪問

ArrayList和Vector的異同點

相同點

兩者都是基于索引的，內部使用陣列
兩者維護插入順序，可以根據插入順序來獲取元素
ArrayList和Vector的迭代器實作都是fail-fast的
ArrayList和Vector兩者都允許null值，也可以使用索引值對元素進行隨機訪問

不同點

Vector是同步的，ArrayList不是，但是已過時，使用CopyOnWriteArrayList
ArrayList比Vector快

LinkedList鏈表

LinkedList添加了一些方法，使其可以被用作堆疊，佇列和雙向佇列，方法差異

getFirst()和element()是相同的，都是回傳串列的頭部，而并不洗掉它，如果list為空，則拋出NoSuchElementException例外，peek()方法在串列為空是回傳null
removeFirst()和remove()方法相同，洗掉并回傳串列頭部元素，在串列為空時回傳NoSuchElementException例外，poll()在串列為空時回傳null
addFirst()在串列頭部插入一個元素
offer()和add()和addLast()相同，在串列尾部添加一個元素
removeLast()洗掉并回傳串列的最后一個元素

ArrayList和LinkedList的區別

ArrayList是由陣列支持的基于索引的資料結構，支持對元素的隨機訪問，復雜度為O(1)，但是LinkedList是基于鏈表的，存盤一系列的節點資料，每個節點都與前一個節點和下一個節點相連，雖然存在使用索引獲取元素的方法，但是內部實作是從起始點開始遍歷的，時間復雜度是O(n)
與ArrayList相比，在LinkedList中插入、添加和洗掉一個元素會更快
LinkedList比ArrayList消耗更多記憶體，因為需要存盤前后節點的參考

迭代器Iterators

Iterator

Iterator介面提供了遍歷任何Collection的介面，取代了java集合框架中的Enumeration，迭代器允許呼叫者在迭代程序中移除資料

? iterator只能單向移動

使用iterator()方法使集合回傳一個Iterator，Iterator將準備好回傳序列中的第一個元素，
使用next()方法獲得序列中的下一個元素，
使用hasNext()方法檢查序列中是否還有元素，
使用remove()方法將迭代器最近回傳的那個元素洗掉，

Enumeration和iterator的區別

Enumeration的速度是Iterator的兩倍，使用記憶體也少，但是iterator更加安全，使得一個集合在遍歷時，會阻止其他執行緒去修改集合，Iterator允許移除元素
Iterator支持fail-fast機制，而Enumeration不支持，Iterator遍歷時，當其他執行緒修改集合內容時，迭代器會立馬感知到，引起快速失敗，拋出ConcurrentModificationException例外
Enumeration本身不支持同步，只是在Vector和hashtable實作Enumeration時，添加了同步

ListIterator

ListIterator是Iterator的子型別，只能由各種List類生成，
Iterator只能向前移動，ListIterator可以雙向移動，可以生成迭代器在串列中指向位置的后一個和前一個元素的索引，

堆疊stack

堆疊是后進先出(LIFO)，最后壓入(push)堆疊的元素，第一個被彈出(pop)堆疊，

java1.0中有一個stack類，但是設計的不好，Java6添加了ArrayDeque，其中包含了直接實作堆疊功能的方法

push()添加元素到堆疊底
peek()和pop()回傳物件，peek()回傳堆疊頂元素，但不從堆疊頂洗掉，而pop()洗掉并回傳堆疊頂元素

Set

Set不保存重復的元素，查找是Set最重要的操作，選擇HashSet實作，針對快速查找進行了優化，

存盤無序，不可重復
添加Set集合中的元素所在類要重寫equals和hashCode方法

無序性：指的是元素在底層存盤的位置是無序的

HashSet沒有順序，使用散列函式，HashSet維護順序與TreeSet或LinkedHashSet不同，因為它們實作具有不同的元素存盤方式
LinkedHashSet 也使用了散列，使用了鏈表來維護元素的插入順序，結果將按元素的插入順序顯示，元素必須定義hashCode()和equals()方法，遍歷元素時，會按照添加的進去的順序
TreeSet將元素存盤在紅黑樹資料結構，可以從Set中獲取有序序列，其中元素必須實作Comparable介面

要求添加進TreeSet的必須是同一個類的
兩種排序方式
1）自然排序：添加的類要實作Comparable介面，重寫compareTo方法
2）定制排序: 使用TreeSet(Comparator<? super E> comparator) 構造器重寫compare(T o1, T o2);方法

Map

鍵值
key不可重復，一個key-value組成一個entry

map的分類

HashMap專為快速訪問而設計，TreeMap保持鍵始終處于排序狀態，沒有HashMap快，LinkedHashMap按插入順序保存其元素，但使用散列提供快速訪問的能力，

HashMap 基于哈希表的實作，為插入和定位鍵值對提供了常數時間性能，可以通過構造方法調整性能，這些構造方法允許設定哈希表的容量和裝填因子，可以添加key為null，value為null
LinkedHashMap 與HashMap類似，但是當遍歷時，可以按照插入順序或最近最少使用(LRU)順序獲取鍵值對，只比HashMap略慢，一個例外是在迭代時，由于其使用鏈表維護內部順序，所以會更快些，按照添加進Map的順序遍歷
TreeMap 基于紅黑樹實作，當查看鍵或鍵值對時，按排序順序(由Comparable或Comparator確定)，TreeMap的側重點在于按排序順序獲得結果，TreeMap是唯一使用subMap()方法的Map，回傳紅黑樹的一部分，按照key所在類的指定屬性進行排序，要求key是同一個類的物件（同TreeSet）
WeakHashMap 一個具有弱鍵的Map，為了解決某些型別的問題，它允許釋放Map所參考的物件，如果Map外沒有對特定鍵的參考，則可以對該鍵進行垃圾回收
ConcurrentHashMap 不使用同步鎖定的執行緒安全Map
IdentityHashMap 使用==來比較鍵，僅用于解決特殊問題
HashTable 不可添加key為null，value為null的子類Properties 處理屬性檔案

HashMap作業情況

HashMap在Map.Entry靜態內部類實作存盤鍵值對，HashMap使用哈希演算法，在put和get方法中，使用hashCode和equals方法，使用put方法時，使用key的hashcode和哈希演算法來找出存盤鍵值對的索引，Entry存盤在LinkedList中，如果存在entry，使用equals檢查傳遞的key是否存在，如果存在，會覆寫掉value，如果不存在，會創建一個新的entry然后保存，get的時候也是先通過hashcode找到陣列中的索引，然后使用equals找到正確的Entry，在進行取值

HashMap默認初始容量是32，負載因子是0.75，閾值是容量乘以負載因子，當map的大小比閾值大時，HashMap會對map的內容進行重新哈希，

HashMap和HashTable的區別

HashMap允許key和value為null，HashTable不允許
HashTable是同步的，HashMap不是
HashMap可以轉為LinkedHashMap，使得遍歷有序，HashTable的順序無法預知
HashMap提供對key的set進行遍歷，所以是fail-fast的，HashTable提供對key的Enumeration進行遍歷，不支持fail-fast
HashTable應該被CocurrentHashMap替代

佇列

佇列操作

佇列是一個先進先出(FIFO)集合，LinkedList實作了Queue介面，并且提供了一些方法支持佇列行為

offer()在佇列尾部插入一個元素
peek()和element()回傳佇列頭而不洗掉它，如果佇列為空，element()拋出NoSuchElementException，而peek()回傳null
poll()和remove()都洗掉并回傳隊頭元素，如果佇列為空，poll()回傳null，remove()拋出NoSuchElementException

PriorityQueue優先級佇列

優先級佇列宣告下一個彈出的元素是最需要的元素，

BlockingQueue佇列

是concurrent包下的類，在進行檢索或移除一個元素的時候，會等待佇列變成非空；當添加一個元素的時候，會等待佇列中的可用空間，主要用于實作生產者-消費者模式

Collections工具類

unmodifiableCollection方法

Collections.unmodifiableCollection(list)；Collections.unmodifiableList(list)；使用該方法會創建一個只讀集合，所有改變集合的操作都會拋出UnsupportedOperationException

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
        return new UnmodifiableCollection<>(c);
}

synchronizedCollection方法

Collections.synchronizedCollection(list)方法可以創建一個執行緒安全的集合

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}

問題

1、遍歷時移除List中的元素

使用forEach和Iterator

在使用forEach遍歷時，實際上是使用的Iterator，使用的核心方法是hasNext()和next()，但是使用的是list.remove，來看個例子

//原始碼
public class TestList {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("J");
        list.add("A");
        list.add("V");
        list.add("A");
        for (String s: list) {
            list.remove(s);
        }
    }
}

//編譯之后
public class TestList {
    public TestList() {
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList();
        list.add("J");
        list.add("A");
        list.add("V");
        list.add("A");
        Iterator var2 = list.iterator();
        while(var2.hasNext()) {
            String s = (String)var2.next();
            list.remove(s);
        }
    }
}

之前說過，Iterator在遍歷時，不允許其他執行緒對該集合進行操作，看一下ArrayList的iterator是怎么實作的

public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = https://www.cnblogs.com/life-time/archive/2021/01/24/ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

在每次獲取下一個元素時，都會比較modCount 和 expectedModCount

然后在呼叫的list的remove方法會導致modCount增加（modCount表示被修改次數）

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = https://www.cnblogs.com/life-time/archive/2021/01/24/elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

此時iterator的next方法中兩個變數就不一致了，就會拋出ConcurrentModificationException例外

再看一下如果使用iterator的remove方法

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

iterator在remove之后會將modCount的值賦給expectedModCount，就不會出現兩個變數不等的情況了

不使用forEach遍歷

使用普通for回圈，有兩種方式，第一種是使用正序遍歷，但是進行remove操作之后要把遍歷的索引進行修正減一，否則在移除下一個的時候就會出錯，第二種就是使用倒序遍歷

// 正序遍歷
for (int i = 0; i < list.size(); i++) {
    String s = list.remove(i);
    i = i - 1;
    System.out.println(s);
}

//倒序遍歷
for (int i = list.size() - 1; i >= 0; i--) {
    String s = list.remove(i);
    System.out.println(s);
}

2、fail-fast和fail-safe

java.util包中集合類被設計為fail-fast的，而java.util.concurrent中集合為fail-safe的，fail-fast迭代器拋出ConcurrentModificationException，而fail-safe迭代器從不拋出ConcurrentModificationException

3、Arrays.asList

這個方法回傳的是一個ArrayList，不過這個ArrayList是Arrays類的內部類，在呼叫add方法的時候會直接報錯

UnsupportedOperationException這是運行時例外

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

由于本身的博客百度沒有收錄，博客地址http://zhhll.icu

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/251958.html

標籤：其他

上一篇：Mybatis-plus表中欄位自動填充

下一篇：模塊一 Go語言基礎知識-作業區和GOPATH