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

迭代器

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

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

通過反復(fù)調(diào)用 next 方法，可以朱哥訪問集合中的每個(gè)元素。但是，如果到達(dá)了集合的末尾，next 方法將拋出一個(gè) NoSuchElementException。因此，需要在調(diào)用 next 之前調(diào)用 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)可以更簡練的表示同樣的操作。編譯器簡單地將其轉(zhuǎn)換為帶有迭代器的循環(huán)
for(String element : c)
{
    // do something with element
}
// 也可以不寫循環(huán)，而是調(diào)用方法并提供一個(gè)Lambda表達(dá)式
Iterator<String> iter = c.iterator();
iterator.forEachRemaining(element -> /* do something with it */ );

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

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

// 如果想刪除兩個(gè)相鄰的元素，不能直接這樣調(diào)用
it.remove();
it.remove()； // ERROR
// 實(shí)際上，需要先next越過將要?jiǎng)h除的元素
it.remove();
it.next();
it.remove(); // OK

集合框架中的接口

集合有兩個(gè)基本接口： Collection 和 Map

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

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

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

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

具體集合

散列碼

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

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

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

樹集

樹集是一個(gè)有序集合，可以以任意順序?qū)⒃夭迦氲郊现小?/p>

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

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

隊(duì)列

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

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

優(yōu)先隊(duì)列

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

無論何時(shí)調(diào)用 remove 方法，總會獲得當(dāng)前優(yōu)先隊(duì)列中最小的元素。優(yōu)先隊(duì)列并沒有對所有元素進(jìn)行排序，而是使用了一個(gè)高效地?cái)?shù)據(jù)結(jié)構(gòu)——堆。堆是一個(gè)可以自組織的二叉樹，其添加與刪除操作可以讓最小的元素移動到根，而無需花費(fèi)時(shí)間對元素進(jìn)行排序。

映射

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

基本映射

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

映射視圖

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

keySet()、values()、entrySet()

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

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

弱散列映射

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

鏈接散列集合映射

LinkedHashMap和LinkedHashSet會記住插入元素項(xiàng)的順序。

枚舉集與映射

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

EnumMap是一個(gè)鍵類型為枚舉類型的映射

標(biāo)識散列映射

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

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

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

最新評論