Java 最初版本只為常用的數(shù)據(jù)結(jié)構(gòu)提供了很少的一組類(lèi)：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);
}

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

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

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

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

集合框架中的接口

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

List 是一個(gè)有序集合。可以采用兩種方式訪問(wèn)元素：迭代器訪問(wèn)，或者使用一個(gè)整數(shù)索引來(lái)訪問(wèn)。后面這種方法稱(chēng)為隨機(jī)訪問(wèn)，因此這樣可以按任意順序訪問(wèn)元素。與之不同，使用迭代器訪問(wèn)時(shí)，必須順序地訪問(wèn)元素。

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

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

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

具體集合

散列碼

散列碼可以用于快速第查找對(duì)象

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

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

樹(shù)集

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

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

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

隊(duì)列

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

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

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

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

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

映射

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

基本映射

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

映射視圖

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

keySet()、values()、entrySet()

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

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

弱散列映射

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

鏈接散列集合映射

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

枚舉集與映射

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

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

標(biāo)識(shí)散列映射

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

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

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

最新評(píng)論