建議79：集合中的哈希碼不要重覆 在一個列表中查找某值是非常耗費資源的，隨機存取的列表是遍歷查找，順序存儲的列表是鏈表查找，或者是Collections的二分法查找，但這都不夠快，畢竟都是遍歷嘛，最快的還要數以Hash開頭的集合(如HashMap、HashSet等類)查找，我們以HashMap為例， ...
建議79：集合中的哈希碼不要重覆
在一個列表中查找某值是非常耗費資源的，隨機存取的列表是遍歷查找，順序存儲的列表是鏈表查找，或者是Collections的二分法查找，但這都不夠快，畢竟都是遍歷嘛，最快的還要數以Hash開頭的集合(如HashMap、HashSet等類)查找，我們以HashMap為例，看看是如何查找key值的，代碼如下：
1 public class Client79 { 2 public static void main(String[] args) { 3 int size = 10000; 4 List<String> list = new ArrayList<String>(size); 5 // 初始化 6 for (int i = 0; i < size; i++) { 7 list.add("value" + i); 8 } 9 // 記錄開始時間，單位納秒 10 long start = System.nanoTime(); 11 // 開始查找 12 list.contains("value" + (size - 1)); 13 // 記錄結束時間,單位納秒 14 long end = System.nanoTime(); 15 System.out.println("List的執行時間：" + (end - start) + "ns"); 16 // Map的查找時間 17 Map<String, String> map = new HashMap<String, String>(size); 18 for (int i = 0; i < size; i++) { 19 map.put("key" + i, "value" + i); 20 } 21 start = System.nanoTime(); 22 map.containsKey("key" + (size - 1)); 23 end = System.nanoTime(); 24 System.out.println("map的執行時間：" + (end - start) + "ns"); 25 } 26 }
兩個不同的集合容器，一個是ArrayList，一個是HashMap，都是插入10000個元素，然後判斷是否包含最後一個加入的元素。邏輯相同，但是執行時間差別卻非常大，結果如下：
HahsMap比ArrayList快了兩個數量級！兩者的contains方法都是判斷是否包含指定值，為何差距如此巨大呢？而且如果數據量增大，差距也會非線性增長。
我們先來看看ArrayList，它的contains方法是一個遍歷對比，這很easy，不多說。我們看看HashMap的ContainsKey方法是如何實現的，代碼如下：
public boolean containsKey(Object key) { //判斷getEntry是否為空 return getEntry(key) != null; }
getEntry方法會根據key值查找它的鍵值對（也就是Entry對象）,如果沒有找到，則返回null。我們再看看該方法又是如何實現的，代碼如下：
1 final Entry<K,V> getEntry(Object key) { 2 //計算key的哈希碼 3 int hash = (key == null) ? 0 : hash(key); 4 //定位Entry、indexOf方法是根據hash定位數組的位置的 5 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 6 e != null; 7 e = e.next) { 8 Object k; 9 //哈希碼相同，並且鍵值也相等才符合條件 10 if (e.hash == hash && 11 ((k = e.key) == key || (key != null && key.equals(k)))) 12 return e; 13 } 14 return null; 15 }
註意看上面代碼中紅色字體部分，通過indexFor方法定位Entry在數組table中的位置，這是HashMap實現的一個關鍵點，怎麼能根據hashCode定位它在數組中的位置呢？
要解釋此問題，還需要從HashMap的table數組是如何存儲元素的說起，首先要說明三點：
- table數組的長度永遠是2的N次冪。
- table數組的元素是Entry類型
- table數組中的元素位置是不連續的
table數組為何如此設計呢？下麵逐步來說明，先來看HashMap是如何插入元素的，代碼如下：
1 public V put(K key, V value) { 2 //null鍵處理 3 if (key == null) 4 return putForNullKey(value); 5 //計算hash碼，並定位元素 6 int hash = hash(key); 7 int i = indexFor(hash, table.length); 8 for (Entry<K, V> e = table[i]; e != null; e = e.next) { 9 Object k; 10 //哈希碼相同，並且key相等，則覆蓋 11 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 12 V oldValue = e.value; 13 e.value = value; 14 e.recordAccess(this); 15 return oldValue; 16 } 17 } 18 modCount++; 19 //插入新元素，或者替換哈希的舊元素並建立鏈表 20 addEntry(hash, key, value, i); 21 return null; 22 }
註意看，HashMap每次增加元素時都會先計算其哈希碼值，然後使用hash方法再次對hashCode進行抽取和統計，同時兼顧哈希碼的高位和低位信息產生一個唯一值，也就是說hashCode不同，hash方法返回的值也不同，之後再通過indexFor方法與數組長度做一次與運算，即可計算出其在數組中的位置，簡單的說，hash方法和indexFor方法就是把哈希碼轉變成數組的下標，源代碼如下：
1 final int hash(Object k) { 2 int h = 0; 3 if (useAltHashing) { 4 if (k instanceof String) { 5 return sun.misc.Hashing.stringHash32((String) k); 6 } 7 h = hashSeed; 8 } 9 10 h ^= k.hashCode(); 11 12 // This function ensures that hashCodes that differ only by 13 // constant multiples at each bit position have a bounded 14 // number of collisions (approximately 8 at default load factor). 15 h ^= (h >>> 20) ^ (h >>> 12); 16 return h ^ (h >>> 7) ^ (h >>> 4); 17 }
1 /** 2 * Returns index for hash code h. 3 */ 4 static int indexFor(int h, int length) { 5 return h & (length-1); 6 }
順便說一下，null值也是可以作為key值的，它的位置永遠是在Entry數組中的第一位。
現在有一個很重要的問題擺在前面了：哈希運算存在著哈希衝突問題，即對於一個固定的哈希演算法f(k)，允許出現f(k1)=f(k2)，但k1≠k2的情況，也就是說兩個不同的Entry，可能產生相同的哈希碼，HashMap是如何處理這種衝突問題的呢？答案是通過鏈表，每個鍵值對都是一個Entry，其中每個Entry都有一個next變數，也就是說它會指向一個鍵值對---很明顯，這應該是一個單向鏈表，該鏈表是由addEntity方法完成的，其代碼如下：
1 void addEntry(int hash, K key, V value, int bucketIndex) { 2 if ((size >= threshold) && (null != table[bucketIndex])) { 3 resize(2 * table.length); 4 hash = (null != key) ? hash(key) : 0; 5 bucketIndex = indexFor(hash, table.length); 6 } 7 8 createEntry(hash, key, value, bucketIndex); 9 }
void createEntry(int hash, K key, V value, int bucketIndex) { //取得當前位置元素 Entry<K,V> e = table[bucketIndex]; //生成新的鍵值對，併進行替換，建立鏈表 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }
這段程式涵蓋了兩個業務邏輯，如果新加入的元素的鍵值對的hashCode是唯一的，那直接插入到數組中，它Entry的next值則為null；如果新加入的鍵值對的hashCode與其它元素衝突，則替換掉數組中的當前值，並把新加入的Entry的next變數指向被替換的元素，於是一個鏈表就產生了，如下圖所示：
HashMap的存儲主線還是數組，遇到哈希碼衝突的時候則使用鏈表解決。瞭解了HashMap是如何存儲的，查找也就一目瞭然了：使用hashCode定位元素，若有哈希衝突，則遍歷對比，換句話說，如果沒有哈希衝突的情況下，HashMap的查找則是依賴hashCode定位的，因為是直接定位，那效率當然就高了。
知道HashMap的查找原理，我們就應該很清楚：如果哈希碼相同，它的查找效率就與ArrayList沒什麼兩樣了，遍歷對比，性能會大打折扣。特別是哪些進度緊張的項目中，雖重寫了hashCode方法但返回值卻是固定的，此時如果把哪些對象插入到HashMap中，查找就相當耗時了。
註意：HashMap中的hashCode應避免衝突。
建議80：多線程使用Vector或HashTable
Vector是ArrayList的多線程版本，HashTable是HashMap的多線程版本，這些概念我們都很清楚，但我們經常會逃避使用Vector和HashTable,因為用的少，不熟嘛！只有在真正需要的時候才會想要使用它們，但問題是什麼時候真正需要呢？我們來看一個例子，看看使用多線程安全的Vector是否可以解決問題，代碼如下：
1 public class Client80 { 2 public static void main(String[] args) { 3 // 火車票列表 4 final List<String> tickets = new ArrayList<String>(100000); 5 // 初始化票據池 6 for (int i = 0; i < 100000; i++) { 7 tickets.add("火車票" + i); 8 } 9 // 退票 10 Thread returnThread = new Thread() { 11 @Override 12 public void run() { 13 while (true) { 14 tickets.add("車票" + new Random().nextInt()); 15 } 16 17 }; 18 }; 19 20 // 售票 21 Thread saleThread = new Thread() { 22 @Override 23 public void run() { 24 for (String ticket : tickets) { 25 tickets.remove(ticket); 26 } 27 } 28 }; 29 // 啟動退票線程 30 returnThread.start(); 31 // 啟動售票線程 32 saleThread.start(); 33 34 } 35 }
模擬火車站售票程式，先初始化一堆火車票，然後開始出售，同時也有退票產生，這段程式有木有問題呢？可能會有人看出了問題，ArrayList是線程不安全的，兩個線程訪問同一個ArrayList數組肯定會有問題。
沒錯，確定有問題，運行結果如下：
運氣好的話，該異常馬上就會拋出，也會會有人說這是一個典型錯誤，只須把ArrayList替換成Vector即可解決問題，真的是這樣嗎？我們把ArrayList替換成Vector後，結果依舊。仍然拋出相同的異常，Vector應經是線程安全的，為什麼還會報這個錯呢？
這是因為它混淆了線程安全和同步修改異常，基本上所有的集合類都有一個快速失敗(Fail-Fast)的校驗機制，當一個集合在被多個線程修改並訪問時，就可能出現ConcurrentModificationException異常，這是為了確保集合方法一致而設置的保護措施，它的實現原理就是我們經常提到的modCount修改計數器：如果在讀列表時，modCount發生變化(也就是有其它線程修改)則會拋出ConcurrentModificationException異常，這與線程同步是兩碼事，線程同步是為了保護集合中的數據不被臟讀、臟寫而設置的，我們來看看線程安全到底用在什麼地方，代碼如下：
1 public static void main(String[] args) { 2 // 火車票列表 3 final List<String> tickets = new ArrayList<String>(100000); 4 // 初始化票據池 5 for (int i = 0; i < 100000; i++) { 6 tickets.add("火車票" + i); 7 } 8 // 10個視窗售票 9 for (int i = 0; i < 10; i++) { 10 new Thread() { 11 public void run() { 12 while (true) { 13 System.out.println(Thread.currentThread().getId() 14 + "----" + tickets.remove(0)); 15 if (tickets.size() == 0) { 16 break; 17 } 18 } 19 }; 20 }.start(); 21 } 22 }
還是火車站售票程式，有10個視窗在賣火車票，程式列印出視窗號(也就是線程號)和車票編號，我們很快就可以看到這樣的輸出：
註意看，上面有兩個線程在賣同一張火車票，這才是線程不同步的問題，此時把ArrayList修改為Vector即可解決問題，因為Vector的每個方法前都加上了synchronized關鍵字，同時知會允許一個線程進入該方法，確保了程式的可靠性。
雖然在系統開發中我們一再說明，除非必要，否則不要使用synchronized，這是從性能的角度考慮的，但是一旦涉及到多線程(註意這裡說的是真正的多線程，並不是併發修改的問題，比如一個線程增加，一個線程刪除，這不屬於多線程的範疇)，Vector會是最佳選擇，當然自己在程式中加synchronized也是可行的方法。
HashMap的線程安全類HashTable與此相同，不再贅述。
建議81：非穩定排序推薦使用List
我們知道Set和List的最大區別就是Set中的元素不可以重覆(這個重覆指的是equals方法的返回值相等)，其它方面則沒有太大區別了，在Set的實現類中有一個比較常用的類需要瞭解一下：TreeSet，該類實現了預設排序為升序的Set集合，如果插入一個元素，預設會按照升序排列(當然是根據Comparable介面的compareTo的返回值確定排序位置了)，不過，這樣的排序是不是在元素經常變化的場景中也適用呢?我們來看看例子：
1 public class Client81 { 2 public static void main(String[] args) { 3 SortedSet<Person> set = new TreeSet<Person>(); 4 // 身高180CM 5 set.add(new Person(180)); 6 // 身高175CM 7 set.add(new Person(175)); 8 for (Person p : set) { 9 System.out.println("身高：" + p.getHeight()); 10 } 11 } 12 13 static class Person implements Comparable<Person> { 14 // 身高 15 private int height; 16 17 public Person(int _height) { 18 height = _height; 19 } 20 21 public int getHeight() { 22 return height; 23 } 24 25 public void setHeight(int height) { 26 this.height = height; 27 } 28 29 // 按照身高排序 30 @Override 31 public int compareTo(Person o) { 32 return height - o.height; 33 } 34 35 } 36 }
這是Set的簡單用法，定義一個Set集合，之後放入兩個元素，雖然175後放入，但是由於是按照升序排列的，所以輸出結果應該是175在前，180在後。
這沒有問題，隨著時間的推移，身高175cm的人長高了10cm，而180cm卻保持不變，那排序位置應該改變一下吧，代碼如下：
1 public static void main(String[] args) { 2 SortedSet<Person> set = new TreeSet<Person>(); 3 // 身高180CM 4 set.add(new Person(180)); 5 // 身高175CM 6 set.add(new Person(175)); 7 set.first().setHeight(185); 8 for (Person p : set) { 9 System.out.println("身高：" + p.getHeight()); 10 } 11 }
找出身高最矮的人，也就是排在第一位的人，然後修改一下身高值，重新排序了？我們看下輸出結果：
很可惜，竟然沒有重現排序，偏離了我們的預期。這正是下麵要說明的問題，SortedSet介面(TreeSet實現了此介面)只是定義了在給集合加入元素時將其進行排序，並不能保證元素修改後的排序結果，因此TreeSet適用於不變數的集合數據排序，比如String、Integer等類型，但不使用與可變數的排序，特別是不確定何時元素會發生變化的數據集合。
原因知道了，那如何解決此類重排序問題呢？有兩種方式：
(1)、Set集合重排序：重新生成一個Set對象，也就是對原有的Set對象重新排序，代碼如下：
set.first().setHeight(185); //set重排序 set=new TreeSet<Person>(new ArrayList<Person>(set));
就這一行紅色代碼即可重新排序，可能有人會問，使用TreeSet<SortedSet<E> s> 這個構造函數不是可以更好的解決問題嗎？不行，該構造函數只是原Set的淺拷貝，如果裡面有相同的元素，是不會重新排序的。
(2)、徹底重構掉TreeSet，使用List解決問題
我們之所以使用TreeSet是希望實現自動排序，即使修改也能自動排序，既然它無法實現，那就用List來代替，然後使用Collections.sort()方法對List排序，代碼比較簡單，不再贅述。
兩種方式都可以解決我們的問題，如果需要保證集合中元素的唯一性，又要保證元素值修改後排序正確，那該如何處理呢？List不能保證集合中的元素唯一，它是可以重覆的，而Set能保證元素唯一，不重覆。如果採用List解決排序問題，就需要自行解決元素重覆問題(若要剔除也很簡單，轉變為HashSet，剔除後再轉回來)。若採用TreeSet，則需要解決元素修改後的排序問題，孰是孰非，就需要根據具體的開發場景來決定了。
註意：SortedSet中的元素被修改後可能會影響到其排序位置。
建議82：由點及面，集合大家族總結
Java中的集合類實在是太豐富了，有常用的ArrayList、HashMap,也有不常用的Stack、Queue，有線程安全的Vector、HashTable，也有線程不安全的LinkedList、TreeMap，有阻塞式的ArrayBlockingQueue，也有非阻塞式的PriorityQueue等，整個集合大家族非常龐大，可以劃分以下幾類：
(1)、List：實現List介面的集合主要有：ArrayList、LinkedList、Vector、Stack，其中ArrayList是一個動態數組，LinkedList是一個雙向鏈表，Vector是一個線程安全的動態數組，Stack是一個對象棧，遵循先進後出的原則。
(2)、Set：Set是不包含重覆元素的集合，其主要實現類有：EnumSet、HashSet、TreeSet，其中EnumSet是枚舉類型專用Set，所有元素都是枚舉類型；HashSet是以哈希碼決定其元素位置的Set，其原理與HashMap相似，它提供快速的插入和查找方法；TreeSet是一個自動排序的Set，它實現了SortedSet介面。
(3)、Map：Map是一個大家族，他可以分為排序Map和非排序Map，排序Map主要是TreeMap類，他根據key值進行自動排序；非排序Map主要包括：HashMap、HashTable、Properties、EnumMap等，其中Properties是HashTable的子類，它的主要用途是從Property文件中載入數據，並提供方便的操作，EnumMap則是要求其Key必須是某一個枚舉類型。
Map中還有一個WeakHashMap類需要說明， 它是一個採用弱鍵方式實現的Map類，它的特點是：WeakHashMap對象的存在並不會阻止垃圾回收器對鍵值對的回收，也就是說使用WeakHashMap裝載數據不用擔心記憶體溢出的問題，GC會自動刪除不用的鍵值對，這是好事。但也存在一個嚴重的問題：GC是靜悄悄的回收的(何時回收，God，Knows！)我們的程式無法知曉該動作，存在著重大的隱患。
(4)、Queue：對列，它分為兩類，一類是阻塞式隊列，隊列滿了以後再插入元素會拋出異常，主要包括：ArrayBlockingQueue、PriorityQueue、LinkedBlockingQueue，其中ArrayBlockingQueue是一個以數組方式實現的有界阻塞隊列；另一類是非阻塞隊列，無邊界的，只要記憶體允許，都可以持續追加元素，我們經常使用的是PriorityQuene類。
還有一種隊列，是雙端隊列，支持在頭、尾兩端插入和移除元素，它的主要實現類是：ArrayDeque、LinkedBlockingDeque、LinkedList。
(5)、數組：數組與集合的最大區別就是數組能夠容納基本類型，而集合就不行，更重要的一點就是所有的集合底層存儲的都是數組。
(6)、工具類：數組的工具類是java.util.Arrays和java.lang.reflect.Array，集合的工具類是java.util.Collections，有了這兩個工具類，操作數組和集合就會易如反掌，得心應手。
(7)、擴展類：集合類當然可以自行擴展了，想寫一個自己的List？沒問題，但最好的辦法還是"拿來主義"，可以使用Apache的common-collections擴展包，也可以使用Google的google-collections擴展包，這些足以應對我們的開發需要。
