Java 最初版本只為常用的數(shù)據(jù)結構提供了很少的一組類：Vector、Stack、Hashtable、BitSet 與 Enumeration 接口

迭代器

public interface Collection<E>
{
    boolean add(E element);
    Iterator<E> iterator();
    ...
}

// ITerator 接口包含4個方法
public interface Iterator<E>
{
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemainint(Consumer<? super E> action);
}

通過反復調用 next 方法，可以朱哥訪問集合中的每個元素。但是，如果到達了集合的末尾，next 方法將拋出一個 NoSuchElementException。因此，需要在調用 next 之前調用 hasNext 方法。

Collection<String> c = ...;
// 普通循環(huán)
Iterator<String> iter = c.iterator();
while(iter.hasNext())
{
    String element = iter.next();
    // do something with element
}
// 此外，使用 for-each 循環(huán)可以更簡練的表示同樣的操作。編譯器簡單地將其轉換為帶有迭代器的循環(huán)
for(String element : c)
{
    // do something with element
}
// 也可以不寫循環(huán)，而是調用方法并提供一個Lambda表達式
Iterator<String> iter = c.iterator();
iterator.forEachRemaining(element -> /* do something with it */ );

Java 集合類庫中的迭代器查找操作與位置變更更緊密耦合，查找元素的唯一方法是調用 next，而在執(zhí)行查找操作的同時，迭代器的位置就會隨之向前移動。
因此，可以認為 Java迭代器位于兩個元素之間。當調用 next 時，迭代器就越過下一個元素，并返回剛剛越過的那個元素的引用。

Iterator 接口的 remove 方法會刪除上次調用 next 方法時返回的元素。 next 方法和 remove 方法調用之間存在依賴性。如果調用 remove 之前沒有調用 next，將會拋出一個 IllegalStateException 異常。

// 如果想刪除兩個相鄰的元素，不能直接這樣調用
it.remove();
it.remove()； // ERROR
// 實際上，需要先next越過將要刪除的元素
it.remove();
it.next();
it.remove(); // OK

集合框架中的接口

集合有兩個基本接口： Collection 和 Map

List 是一個有序集合?？梢圆捎脙煞N方式訪問元素：迭代器訪問，或者使用一個整數(shù)索引來訪問。后面這種方法稱為隨機訪問，因此這樣可以按任意順序訪問元素。與之不同，使用迭代器訪問時，必須順序地訪問元素。

**紕漏**：集合框架在這個地方設計得不好。實際上有兩種有序集合，其性能開銷有很大差異。
1. 數(shù)組支持的有序集合，可以快速地隨機訪問，因此適合使用List方法并提供一個整數(shù)索引訪問
2. 鏈表盡管也是有序的，但是隨機訪問**很慢**，所以最好使用迭代器進行遍歷、

為了避免對鏈表完成隨機訪問操作， Java 1.4 引入了一個*標記接口*`RandomAccess`，這個接口不包含任何方法，不過可以用來測試一個特定的集合是否支持高效的隨機訪問：
`  if(c instanceof RandomAccess) { /* use random access algorithm */ }`
`  else { /* use qequential access algorithm */ }`

Set 接口等同于 Collection 接口，不過其方法的行為有更嚴謹?shù)亩x。

具體集合

散列碼

散列碼可以用于快速第查找對象

在 Java 中，散列表用鏈表數(shù)組實現(xiàn)。每個列表被稱為桶。 在 Java 8 中，桶滿時會從鏈表變?yōu)槠胶舛鏄?，以提高性能。標準類庫使用的桶?shù)是 2 的冪，默認值為 16（為表大小提供的任何值都將自動地轉換為 2 的下一個冪值）。

如果散列表太滿，就需要再散列。此時，就需要創(chuàng)建一個桶數(shù)更多的表，并將所有的元素插入到這個新表中，然后丟棄原來的表。裝填因子（默認0.75）可以確定何時對散列表進行散列，新表的桶數(shù)是原來的兩倍。

樹集

樹集是一個有序集合，可以以任意順序將元素插入到集合中。

每次將一個元素添加到樹中，都會將其放置在正確的排序位置上。因此，迭代器總是以有序的順序訪問每個元素。
將一個元素添加到樹中要比添加到散列表中慢。但是，檢查數(shù)組或鏈表中的重復元素時，樹會快很多。

注： 要使用樹集，必須能夠比較元素。這些元素必須實現(xiàn) Comparable 接口，或者構造集時必須提供一個 Comparator。

隊列

隊列允許高校地在尾部添加元素，并在頭部刪除元素。不支持在隊列中間添加元素

Java 6 中引入了 Deque 接口，ArrayDeque 和 LinkedList 類實現(xiàn)了這個接口。

優(yōu)先隊列

優(yōu)先隊列中的元素可以按照任意的順序插入，但會按照有序的順序進行檢索。

無論何時調用 remove 方法，總會獲得當前優(yōu)先隊列中最小的元素。優(yōu)先隊列并沒有對所有元素進行排序，而是使用了一個高效地數(shù)據(jù)結構——堆。堆是一個可以自組織的二叉樹，其添加與刪除操作可以讓最小的元素移動到根，而無需花費時間對元素進行排序。

映射

映射數(shù)據(jù)結構用于存放鍵/值對，知道某些關鍵信息，可以查找與之關聯(lián)的元素。

基本映射

Java類庫我映射提供了兩個通用的實現(xiàn)：HashMap和TreeMap。

映射視圖

集合框架不認為映射本身是一個集合。（其他數(shù)據(jù)結構框架認為映射是一個鍵/值對集合，或者是按鍵索引的值集合）。不過，可以得到視圖——實現(xiàn)了 Collection 接口或某個子接口的對象。

keySet()、values()、entrySet()

注： keySet 不是 HashSet 或 TreeSet，而是實現(xiàn)了 Set 接口的另外某個類的對象。

可以在集視圖中刪除元素，它們將從該映射中刪除，但是不能添加任何元素

弱散列映射

WeakHashMap類使用弱引用保存鍵。WeakReference 對象將包含另一個對象的引用，在這里，就是一個散列表鍵。正常情況下，如果垃圾回收器發(fā)現(xiàn)某個特定的對象已經(jīng)沒有他人引用，就會將其回收。
然而，如果某個對象只能由 WeakReference 引用，垃圾回收器也會將其回收，但會將這個對象的弱引用放進一個隊列。WeakHashMap 將周期性地檢查隊列，以便找出新添加的弱引用。一個若引用進入隊列意味著這個鍵不再被他人使用，并且已經(jīng)回收。于是，WeakHashMap 將刪除相關聯(lián)的映射。

鏈接散列集合映射

LinkedHashMap和LinkedHashSet會記住插入元素項的順序。

枚舉集與映射

EnumSet是一個枚舉類型元素集的高效實現(xiàn)。內部用位序列實現(xiàn)。

EnumMap是一個鍵類型為枚舉類型的映射

標識散列映射

IdentityHashMap類有特殊用途。該類中，鍵的散列值由 System.identityHashCode 計算，是根據(jù)對象的內存地址計算散列碼所使用的方法。因此在比較對象時采用==，不同的鍵對象即使內容相同，也被視為不同的對象。

在實現(xiàn)對象遍歷算法（如對象串行化）時，這個類十分有用，可以用來跟蹤哪些對象已經(jīng)遍歷過。

到此這篇關于Java常用集合與原理解析的文章就介紹到這了,更多相關Java集合與原理內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論