前言：俗話說(shuō)“金三銀四銅五”，不知道我要在這段時(shí)間找工作會(huì)不會(huì)很艱難。不管了，工作三年之后就當(dāng)給自己放個(gè)暑假。

面試當(dāng)中Collection（集合）是基礎(chǔ)重點(diǎn).我在網(wǎng)上看了幾篇講Collection的文章，大多都是以羅列記憶點(diǎn)的形式書(shū)寫(xiě)的，沒(méi)有談?wù)搶?shí)現(xiàn)細(xì)節(jié)和邏輯原理。作為個(gè)人筆記無(wú)可厚非，但是并不利于他人學(xué)習(xí)。希望能通過(guò)這種比較“費(fèi)勁”的講解，幫助我自己、也幫助讀者們更好地學(xué)習(xí)Java、掌握J(rèn)ava.

無(wú)論你跟我一樣需要應(yīng)聘，還是說(shuō)在校學(xué)生學(xué)習(xí)Java基礎(chǔ)，都對(duì)入門和進(jìn)一步啟發(fā)學(xué)習(xí)有所幫助。(關(guān)于Collection已經(jīng)寫(xiě)過(guò)一篇文章，可以在本文最后點(diǎn)擊鏈接閱讀）。

1.3 拒絕重復(fù)內(nèi)容的Set

Set，跟數(shù)學(xué)中的概念“集合”是一樣的，就是沒(méi)有重復(fù)的元素。在JavaSE的Cellection框架里，Set是三大陣營(yíng)之一。根據(jù)“核心框架圖”，我們可以看到它的位置。

同樣一張訂單，已經(jīng)支付過(guò)一次就不能再次支付，否則就是重復(fù)支付。反映在系統(tǒng)當(dāng)中，就是收集對(duì)象時(shí)，如果有相同的對(duì)象，則不再重復(fù)收集。如果有這類需求，我們可以用使用實(shí)現(xiàn)Set接口的類。之前講過(guò)的List和之后會(huì)談到的Queue，都對(duì)是否重復(fù)沒(méi)有要求，這是Set的特性。

1.3.1 如何使用HashSet

除非已經(jīng)是大小牛級(jí)別的人能做到觸類旁通，否則最好在學(xué)習(xí)API的時(shí)候做幾個(gè)簡(jiǎn)單的實(shí)驗(yàn)，不僅可以更實(shí)際地幫助理解，還可以加深印象有助于長(zhǎng)期記憶。

輸入一段英文，經(jīng)過(guò)處理后需要輸出所有不重復(fù)的單詞。HashSet實(shí)現(xiàn)了Set接口，我們不妨就用它來(lái)寫(xiě)一段demo。

 1 import java.util.*; 2  3 /** 4  * HashSet的實(shí)驗(yàn)用例 5  */ 6 public class Words { 7     public static void main(String[] args) { 8         Scanner scanner = new Scanner(System.in); 9         System.out.print("請(qǐng)輸入一段話：");10         String line = scanner.nextLine();11         String[] tokens = line.split(" ");//根據(jù)空格劃分單詞12         Set words = new HashSet();13         for(String token : tokens) {14             words.add(token);//使用HashSet收集單詞15         }16         System.out.printf("不重復(fù)的單詞有：%d 個(gè)： %s%n", words.size(), words);17     }18 }

英語(yǔ)中分詞沒(méi)有中文分詞那么困難，基本上可以按照空格來(lái)劃分單詞。很明顯，輸出的結(jié)果是正確的。

這時(shí)候不知道你是否也有這么一個(gè)疑問(wèn)：HashSet是如何判斷哪些單詞重復(fù)的呢？如果讓你來(lái)做，你會(huì)怎么做？

1.3.2 Java中判斷重復(fù)對(duì)象的規(guī)范

如果對(duì)象是字符串，我們可以采用逐一比較的方式，比較即將收集的字符串和已有的字符串是否相同；如果對(duì)象是數(shù)值，那就更簡(jiǎn)單了?？墒牵酥獾膶?duì)象怎么辦？我們先來(lái)看一個(gè)沒(méi)那么復(fù)雜的例子。

 1 import java.util.*; 2  3 /** 4  * Set測(cè)試用例 5  */ 6     class Student { 7     private String name; 8     private String number; 9 10     Student(String name, String number) {11         this.name = name;12         this.number = number;13     }14 15 16     @Override17     public String toString() {18         return String.format("(%s, %s)", name, number);19     }20 }21 22     public class Students {23         public static void main(String[] args) {24             Set set = new HashSet();25             set.add(new Student("Tom", "001"));26             set.add(new Student("Sam", "002"));27             set.add(new Student("Tom", "001"));28             System.out.println(set);29         }30     }

上面這段demo是在模擬一個(gè)學(xué)生注冊(cè)系統(tǒng)，錄入姓名和學(xué)號(hào)，最后輸出已經(jīng)注冊(cè)了的學(xué)生。由于同一個(gè)學(xué)生不能注冊(cè)兩次，所以使用了HashSet來(lái)收集對(duì)象。

這樣的輸出結(jié)果是否出乎你的意料？顯然，在執(zhí)行過(guò)程中Set并沒(méi)有把重復(fù)的學(xué)生數(shù)據(jù)排除。其實(shí)是我們太一廂情愿了，因?yàn)樵趯?xiě)程序的時(shí)候并沒(méi)有告訴Set，什么樣的Student實(shí)例才算是重復(fù)。要判斷對(duì)象是否重復(fù)，必須實(shí)現(xiàn)hashCode()和equals()方法。在之前的英文分詞例子中，對(duì)象是String，我們可以在源代碼中看到它已經(jīng)實(shí)現(xiàn)了這兩個(gè)方法。

 1 /** 2      * Compares this string to the specified object.  The result is {@code 3      * true} if and only if the argument is not {@code null} and is a {@code 4      * String} object that represents the same sequence of characters as this 5      * object. 6      * 7      * @param  anObject 8      *         The object to compare this {@code String} against 9      *10      * @return  {@code true} if the given object represents a {@code String}11      *          equivalent to this string, {@code false} otherwise12      *13      * @see  #compareTo(String)14      * @see  #equalsIgnoreCase(String)15      */16     public boolean equals(Object anObject) {17         if (this == anObject) {18             return true;19         }20         if (anObject instanceof String) {21             String anotherString = (String)anObject;22             int n = value.length;23             if (n == anotherString.value.length) {24                 char v1[] = value;25                 char v2[] = anotherString.value;26                 int i = 0;27                 while (n-- != 0) {28                     if (v1[i] != v2[i])29                         return false;30                     i++;31                 }32                 return true;33             }34         }35         return false;36     }37 38 /**39      * Returns a hash code for this string. The hash code for a40      * {@code String} object is computed as41      * <blockquote><pre>42      * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]43      * </pre></blockquote>44      * using {@code int} arithmetic, where {@code s[i]} is the45      * <i>i</i>th character of the string, {@code n} is the length of46      * the string, and {@code ^} indicates exponentiation.47      * (The hash value of the empty string is zero.)48      *49      * @return  a hash code value for this object.50      */51     public int hashCode() {52         int h = hash;53         if (h == 0 && value.length > 0) {54             char val[] = value;55 56             for (int i = 0; i < value.length; i++) {57                 h = 31 * h + val[i];58             }59             hash = h;60         }61         return h;62     }

事實(shí)上不只有HashSet，Java中許多要判斷對(duì)象是否重復(fù)時(shí)，都要求調(diào)用hashCode()與equals()方法，因此官方規(guī)范中建議這兩個(gè)方法必須同時(shí)實(shí)現(xiàn)。如果我們?cè)谥皩W(xué)生注冊(cè)的例子中添加hashCode()與equals()方法的實(shí)現(xiàn)，重復(fù)的數(shù)據(jù)就不會(huì)出現(xiàn)。

 1 import java.util.*; 2  3 /** 4  * Set測(cè)試用例 5  */ 6     class Student { 7     private String name; 8     private String number; 9 10     Student(String name, String number) {11         this.name = name;12         this.number = number;13     }14 15     /**16      * 重載equals()和hashcode()17      */18     @Override19     public boolean equals(Object obj) {20         if(obj == null) {21             return false;22         }23         if(getClass() != obj.getClass()) {24             return false;25         }26         final Student other = (Student) obj;27         return true;28     }29 30     @Override31     public int hashCode() {32         int hash = 5;33         hash = 13 * hash + (this.name != null ? this.name.hashCode() : 0);34         hash = 13 * hash + (this.number != null ? this.number.hashCode() : 0);35         return hash;36     }37 38 39     @Override40     public String toString() {41         return String.format("(%s, %s)", name, number);42     }43 }44 45     public class Students {46         public static void main(String[] args) {47             Set set = new HashSet();48             set.add(new Student("Tom", "001"));49             set.add(new Student("Sam", "002"));50             set.add(new Student("Tom", "001"));51             System.out.println(set);52         }53     }

重載的hashCode()和equals()方法定義了“如果學(xué)生的姓名與學(xué)號(hào)相同，那就是重復(fù)的對(duì)象”。當(dāng)然，你也可以根據(jù)自己的理解，改寫(xiě)成“如果學(xué)號(hào)相同，即為重復(fù)”。

1.3.3 Set小結(jié)

Set收集對(duì)象時(shí)，如果發(fā)現(xiàn)有重復(fù)的數(shù)據(jù)，會(huì)不再收集該對(duì)象。如果要實(shí)現(xiàn)這一點(diǎn)，必須告知符合什么樣的條件才算是“重復(fù)”。

Java規(guī)范中通過(guò)重載hashCode()和equals()方法來(lái)判斷是否重復(fù)。如果你要收集的對(duì)象不屬于String或Integet之類API已經(jīng)提供好的類，務(wù)必要記得實(shí)現(xiàn)這兩個(gè)方法。

通過(guò)學(xué)習(xí)Set和閱讀源代碼，不僅可能更好地掌握常用API的用法，同時(shí)也會(huì)Java規(guī)范有了意料之外情理之中的深入了解。無(wú)論是對(duì)Java的學(xué)習(xí)，還是日常的開(kāi)發(fā)維護(hù)工作，都有不小的幫助。 

1.4 支持隊(duì)列操作的Queue

什么是隊(duì)列？它是最常用的數(shù)據(jù)結(jié)構(gòu)之一，只允許在隊(duì)列的前端（front)進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。

顧名思義，只要是需要“排隊(duì)”的應(yīng)用場(chǎng)景，都可以考慮使用隊(duì)列，例如餐廳的排隊(duì)系統(tǒng)，醫(yī)院的器官輪候系統(tǒng)等。

1.4.1 Queue的實(shí)現(xiàn)規(guī)范

在介紹完List、Set之后，我們來(lái)看看Collection的最后一大塊Queue. 

Queue定義了自己特有的offer()、poll()和peek()等方法。建議優(yōu)先使用offer()方法，而不是add()方法來(lái)收集對(duì)象。同樣地，pool()和peek()方法建議優(yōu)先于remove()、element()方法使用。他們最主要的區(qū)別在于，add()、remove()、element()方法出錯(cuò)時(shí)會(huì)拋出異常，offer()、poll()、peek()方法則會(huì)返回特定值。

前一篇介紹List的文章就介紹過(guò)LinkedList。從反復(fù)提及的核心架構(gòu)圖中可以看出，其實(shí)它不僅實(shí)現(xiàn)了List，同時(shí)也是一種Queue。我們不妨就用LinkedList來(lái)寫(xiě)一段demo，試著使用隊(duì)列。

 1 import java.util.*; 2  3 /** 4  * Queue實(shí)驗(yàn)用例 5  */ 6 interface Request { 7     void execute(); 8 } 9 10 public class RequestQueue {11 12     public static void main(String[] args) {13         Queue requests = new LinkedList();14         // 模擬將請(qǐng)求加入隊(duì)列15         for (int i = 1; i < 6; i++) {16             requests.offer(new Request() {17                public void execute() {18                    System.out.printf("處理數(shù)據(jù) %f%n", Math.random());19                }20             });21         }22         process(requests);23     }24 25     // 處理隊(duì)列中的請(qǐng)求26     private static void process(Queue requests) {27         while(requests.peek() != null) {28             Request request = (Request) requests.poll();29             request.execute();30         }31     }32 }

由于是隨機(jī)產(chǎn)生的數(shù)字，所以幾乎每一次實(shí)驗(yàn)結(jié)果都會(huì)不一樣，不過(guò)這并不重要。

1.4.2 既是隊(duì)列又是棧的Deque

有的時(shí)候，我們會(huì)想對(duì)隊(duì)列的前端與尾端進(jìn)行操作，能在前端加入對(duì)象、取出對(duì)象，也能在尾端加入對(duì)象和取出對(duì)象。Queue的子接口Deque可以滿足這個(gè)需求，我們?cè)诤诵目蚣軋D上可以很容易找到它的位置。

Queue的行為和Deque的行為有所重復(fù)，有幾個(gè)方法是等義的，例如前者的add()等于后者的addLast()方法，建議感興趣的朋友自行查看源代碼或API說(shuō)明文檔。

java.util.ArrayDeque實(shí)現(xiàn)了Deque接口，我們可以通過(guò)寫(xiě)一段操作容量有限的堆棧的demo來(lái)看看如何使用它。

 1 import java.util.*; 2  3 /** 4  * Deque實(shí)驗(yàn)用例 5  */ 6 public class Stack { 7     private Deque deque = new ArrayDeque(); 8     private int capacity; 9 10     public Stack(int capacity) {11         this.capacity = capacity;12     }13 14     public boolean push(Object o) {15         if(deque.size() + 1 > capacity) {16             return false;17         }18         return deque.offerLast(o);19     }20 21     public Object pop() {22         return deque.pollLast();23     }24 25     public Object peek() {26         return deque.peekLast();27     }28 29     public int size() {30         return deque.size();31     }32 33     public static void main(String[] args) {34         Stack stack = new Stack(5);35         stack.push("小明");36         stack.push("小花");37         stack.push("小光");38         System.out.println(stack.pop());39         System.out.println(stack.pop());40         System.out.println(stack.pop());41     }42 }

堆棧結(jié)構(gòu)的特性是先進(jìn)后出，所以運(yùn)行結(jié)果是先顯示小光，最后顯示小明。

一道思考題：從核心框架圖中可以看出LinkedList也實(shí)現(xiàn)了Deque接口，不過(guò)在這個(gè)demo里面，使用ArrayDeque速度上要比LinkedList快。這是為什么？

1.4.3 Quque小結(jié)

隊(duì)列是一種常見(jiàn)而且重要的數(shù)據(jù)結(jié)構(gòu)，JavaSE中Collection的三大分支之一Quque提供了相應(yīng)的實(shí)現(xiàn)。

Deque是一種雙向隊(duì)列，同時(shí)也是Queue的一個(gè)子接口。它們之間既有等義的方法，也有不同的實(shí)現(xiàn)，具體情況需要閱讀API說(shuō)明文檔或直接查看源代碼。

我們?cè)趯W(xué)習(xí)之前，不妨可以先試著用Java基本語(yǔ)法實(shí)現(xiàn)隊(duì)列、堆棧等數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)操作方法。在此基礎(chǔ)上再閱讀相應(yīng)的源代碼（例如LinkedList)，會(huì)格外發(fā)現(xiàn)代碼的邏輯之美和整潔之美。

 相關(guān)文章推薦：

JavaSE中Collection集合框架學(xué)習(xí)筆記(1)——具有索引的List

如果你喜歡我的文章，可以掃描關(guān)注我的個(gè)人公眾號(hào)“李文業(yè)的思考筆記”。

http://www.cnblogs.com/levenyes/p/7120267.html

延伸閱讀

• 珊珊老師——北京IT機(jī)構(gòu)十年一線教學(xué)經(jīng)驗(yàn) 2024-08-28
• 告別“老頑固” 2023-04-18
• 時(shí)光飛逝 2024-03-26
• 會(huì)當(dāng)凌絕頂，一覽眾山小 2023-04-18
• 自豪 2023-04-18
• 綻放 2023-04-18
• 畢業(yè)有感 2023-04-18
• 投入六個(gè)月的經(jīng)歷，收獲了整個(gè)人生 2023-04-18
• 非常響亮的名字 2023-04-18
• 不可磨滅的力量 2023-04-18

珊珊老師——北京IT機(jī)構(gòu)十年一線教學(xué)經(jīng)驗(yàn)