1.前言：數(shù)據(jù)結(jié)構(gòu)——隊(duì)列

隊(duì)列接口先說(shuō)明有哪些功能，但不說(shuō)是如何實(shí)現(xiàn)的，隊(duì)列有兩種實(shí)現(xiàn)方式：

• 循環(huán)數(shù)組
• 鏈表

循環(huán)數(shù)組更加高效，但循環(huán)數(shù)組是個(gè)有界集合，容量有限，如果對(duì)象的數(shù)量沒(méi)有上限，最好用鏈表來(lái)實(shí)現(xiàn)。

一旦構(gòu)建了集合就不需要知道到底使用了哪種實(shí)現(xiàn)。所以可以使用接口類型存放集合的引用

List<String> list = new ArrayList<>();
list.add("abc");

如果我們想修改成另一種實(shí)現(xiàn)，只需要把ArrayList改成LinkedList。

2.Collection 接口

collection接口有兩個(gè)基本方法：

// 如果添加元素確實(shí)改變了集合就返回 true;如果沒(méi)有改變就返回 false，比如添加的元素已經(jīng)存在就不會(huì)改變?cè)?boolean add(E element);

// 迭代器，見(jiàn)下一點(diǎn)
Iterator<E> iterator();

3.迭代器

Iterator接口有4個(gè)方法：

public interface Iterator<E>{
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Student<? super E> stu);
}

反復(fù)調(diào)用 next() 方法，能逐個(gè)訪問(wèn)集合的每個(gè)元素，但如果訪問(wèn)到了集合的末尾，會(huì)拋出一個(gè) NoSuchElementException，所以我們?cè)谡{(diào)用next()前最好使用hasNext()檢查下。

List<String> list = new ArrayList<>();
list.add("abc");
list.add("123");
list.add("qwe");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next()); // abc 123 qwe
}

當(dāng)然，如果要循環(huán)一個(gè)集合，更簡(jiǎn)單的方法是使用forEach:

for (String s : list) {
    System.out.println(s);
}

也可以使用forEachRemaining：

iterator.forEachRemaining(element -> System.out.println(iterator.next()));

順序問(wèn)題：元素被訪問(wèn)的順序取決于集合類型，如果對(duì) ArrayList 進(jìn)行迭代，迭代器將從索引0開(kāi)始，每迭代一次，索引值加1。如果是 HashSet ，每個(gè)元素會(huì)按照某種特定的次序出現(xiàn)，雖然也能訪問(wèn)到所有元素，但順序是隨機(jī)的。

remove()刪除的是上次調(diào)用 next 方法時(shí)返回的元素。所以調(diào)用 remove 之前必須要有 next 方法被調(diào)用。

4.集合中的接口

集合框架的接口

需要注意的是：數(shù)組支持的有序集合因?yàn)榭梢钥焖匐S機(jī)訪問(wèn)，所有最好提供一個(gè)整數(shù)索引來(lái)訪問(wèn)，鏈表最好使用迭代器來(lái)遍歷。

5.Java 庫(kù)中的具體集合

image-20180909112447085

6.鏈表

數(shù)組列表的問(wèn)題：從中間刪除一個(gè)元素之后，該元素后面的元素都需要向前移動(dòng)，在中間插入也是。

鏈表就沒(méi)有這個(gè)問(wèn)題。

鏈表讓我想到了比特幣的區(qū)塊結(jié)構(gòu)，看圖吧

image-20180909122239957

每個(gè) Link 可以看成一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存放著前一個(gè)節(jié)點(diǎn)的引用和后一個(gè)節(jié)點(diǎn)的引用，所以鏈表實(shí)際上都是雙向鏈接的。回到數(shù)組列表的問(wèn)題，當(dāng)我們需要插入一個(gè)元素的時(shí)候，只需要修改該節(jié)點(diǎn)以及其前后節(jié)點(diǎn)的引用就可以了。

但鏈表不支持快速的隨機(jī)訪問(wèn)，如果要查看第100個(gè)元素，就必須從頭開(kāi)始，越過(guò)99個(gè)元素。所以如果程序需要采用整數(shù)索引訪問(wèn)元素時(shí)，通常不選用鏈表。

7.數(shù)組列表

List 接口用于描述一個(gè)有序集合，并且集合中每個(gè)元素的位置十分重要。有兩種訪問(wèn)元素的協(xié)議：

1. 用迭代器
2. 用 get 和 set 方法隨機(jī)訪問(wèn)每個(gè)元素

8.散列集

如果我們想要訪問(wèn)某個(gè)元素，但又忘了它的位置，這時(shí)候就需要散列集。該集運(yùn)用的數(shù)據(jù)結(jié)構(gòu)為散列表（hash table）。散列表會(huì)為每個(gè)對(duì)象計(jì)算一個(gè)整數(shù)，成為散列碼（hash code）。散列碼是由對(duì)象的實(shí)例域產(chǎn)生的。比如下表。

如果是我們自己定義的類，就要實(shí)現(xiàn)這個(gè)類的hashCode()方法，同時(shí)還有equals()方法。

set 類型：set 是沒(méi)有重復(fù)元素的元素集合。set 的 add 方法首先會(huì)集中查找要添加的對(duì)象，如果不存在，就將這個(gè)元素添加進(jìn)去。

9.數(shù)集

TreeSet可以看成一個(gè)有序的散列集。當(dāng)添加的時(shí)候會(huì)比較慢，但查詢會(huì)比散列集快很多。

使用數(shù)集必須能比較元素，所有必須實(shí)現(xiàn) comparable 接口。

10.隊(duì)列與雙端隊(duì)列

隊(duì)列可以讓人們有效的在尾部添加一個(gè)元素，在頭部刪除一個(gè)元素。有兩個(gè)端頭的隊(duì)列，即為雙端隊(duì)列，可以讓人們有效的在頭部和尾部同時(shí)添加或刪除元素。不支持在隊(duì)列中添加元素。Deque 接口由 ArrayDeque 和 LinkedList 實(shí)現(xiàn)。

11.優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)隊(duì)列中的元素可以按照任意的順序插入，卻總是按照排序的順序進(jìn)行索引。也就是說(shuō)，無(wú)論何時(shí)調(diào)用 remove 方法，總是獲得當(dāng)前優(yōu)先級(jí)隊(duì)列中最小的元素。

12.映射的兩個(gè)實(shí)現(xiàn)

• HashMap：散列映射對(duì)鍵進(jìn)行散列。
• TreeMap：樹(shù)映射用鍵的整體順序?qū)υ剡M(jìn)行排序，并將其組織成搜索樹(shù)。

如果不需要按照一定順序訪問(wèn)鍵，就選擇散列，因?yàn)樯⒘懈煲恍?/p>

一些基本的操作：

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
String myName = maps.get("second");
System.out.println(myName); // zyc

鍵必須是唯一的，如果 put 的鍵是重復(fù)的，則會(huì)覆蓋前一個(gè)。而且 put 會(huì)返回被覆蓋的那個(gè)值。

13.迭代

• 利用 forEach 和 lambda 表達(dá)式：

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.forEach((k,v) ->
             System.out.println("key:" + k +",val:" + v));

• 利用迭代器：

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
Iterator<Map.Entry<String,String>> entryIterator = maps.entrySet().iterator();
entryIterator.forEachRemaining(System.out::println);
// entryIterator.forEachRemaining(element -> System.out.println(element));

14.Merge

當(dāng)有這樣一個(gè)需求：需要更新/新增的映射項(xiàng)在映射存在或者不存在的時(shí)候會(huì)進(jìn)行不同的操作，這時(shí)候就需要用上merge 了。具體看代碼吧

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.merge("first","i am new",(oldVal, newVal) -> {
    System.out.println("1執(zhí)行了:" + oldVal + "," + newVal);
    return oldVal;
});
maps.merge("first1","i am new",(oldVal, newVal) -> {
    System.out.println("1執(zhí)行了:" + oldVal + "," + newVal);
    return oldVal;
});

maps.forEach((k,v) ->
             System.out.println("key:" + k +",val:" + v));

/*
    1執(zhí)行了:ethan,i am new
    key:third,val:zyy
    key:first1,val:i am new
    key:first,val:ethan
    key:second,val:zyc
 */

因?yàn)?code>first已經(jīng)存在了，所以會(huì)執(zhí)行后面的函數(shù)，而first1不存在，所以根本就沒(méi)有執(zhí)行后面的值，而是僅僅把i am new設(shè)為first1對(duì)應(yīng)的值。

15.映射視圖

雖然很多數(shù)據(jù)結(jié)構(gòu)認(rèn)為映射屬于集合，但在 java 中，映射并不在集合框架中。不過(guò)映射視圖是實(shí)現(xiàn)了 Collection 的對(duì)象。視圖包括鍵集合、值集合以及鍵值對(duì)集合。并且對(duì)三者進(jìn)行remove操作會(huì)影響原視圖。鍵是不能重復(fù)的，所以直接刪除，但值時(shí)可以重復(fù)的，這里只刪除了其中一個(gè)，不建議以刪除值來(lái)刪除鍵值對(duì)。

Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.put("forth","zyc");
Set<String> keys = maps.keySet();
Collection<String> vals = maps.values();
Set<Map.Entry<String,String>> keyVals = maps.entrySet();
System.out.println(keys);
System.out.println(vals);
System.out.println(keyVals);
keys.remove("first");
vals.remove("zyc");
System.out.println(keyVals);

/*
    [third, forth, first, second]
    [zyy, zyc, ethan, zyc]
    [third=zyy, forth=zyc, first=ethan, second=zyc]
    [third=zyy, second=zyc]
*/