# 題記 JDK，Java Development Kit。 我們必須先認識到，JDK只是，僅僅是一套Java基礎類庫而已，是Sun公司開發的基礎類庫，僅此而已，JDK本身和我們自行書寫總結的類庫，從技術含量來說，還是在一個層級上，它們都是需要被編譯成字節碼，在JRE中運行的，JDK編譯后的結果就是jre/lib下的rt.jar，我們學習使用它的目的是加深對Java的理解，提高我們的Java編碼水平。 本系列所有文章基于的JDK版本都是1.7.16。 源碼下載地址：[https://jdk7.java.net/source.html](https://jdk7.java.net/source.html) # 本節內容 在本節中，簡析java.util包所包含的工具類庫，主要是集合相關的類庫，其次還有正則、壓縮解壓、并發、日期時間等工具類。 本篇內容大致、簡單的對于java.util包進行了一個描述，以后會逐漸進行內容補充，本篇文章相當于一個占位符，所謂先有了骨架，才能逐漸豐滿 # 集合類 ### 基本情況 **主要接口及其繼承關系如下：** SortedSet ?--> ?Set --> Collection --> ?Iterable List ?--> ?Collection ?--> ?Iterable SortedMap ?--> ?Map **常用類及其繼承關系如下：** HashSet/LinkedHashSet ?--> Set TreeSet ?--> ?SortedSet ?--> Set ArrayList/LinkedList ?--> ?List HashMap ?--> ?Map TreeMap ?--> ?SortedMap ?--> ?Map 統一稱謂：Collection分支的，我們稱之為“聚集”；Map分支的，我們稱之為“映射”。 Collection繼承自Iterable，所以其下的類都可以用迭代器Iterator訪問，也可以用for(E e:es)形式訪問；Map可以用實現了其內部接口Entry的對象，作為一個元素。 Hashtable和HashMap，他們都實現了Map接口；Hashtable繼承自古老的抽象類Dictionary，是線程安全的；HashMap繼承自較新的抽象類AbstractMap，不是線程安全的。 HashMap允許null的鍵和值，而Hashtable不允許null的鍵和值，這是因為： Hashtable有方法contains方法（判斷是否存在值），如果允許的話，則不論key或者value為null，都會返回null，這容易誤解，所以Hashtable就強制限制了，對于null 鍵和值，直接拋出NullPointerException； HashMap沒有contains方法，分別是containsKey()和containsValues()。 另外JDK5開始，對于線程安全的Map，有一種ConcurrentHashMap，高效，其實現線程安全的過程中，沒有使用synchronized，是一種分段的結構，并用CAS這種無鎖算法實現了線程安全。 ### Hash Object類有兩種方法來推斷對象的標識：equals()和hashCode()。 一般來說，如果您忽略了其中一種，您必須同時忽略這兩種，因為兩者之間有必須維持的至關重要的關系。 特殊情況是根據equals() 方法，如果兩個對象是相等的，它們必須有相同的hashCode()值，Object源碼中對此有要求，盡管這通常不是真的。 [http://blog.sina.com.cn/s/blog_5dc351100101l57b.html](http://blog.sina.com.cn/s/blog_5dc351100101l57b.html) [http://fhuan123.iteye.com/blog/1452275](http://fhuan123.iteye.com/blog/1452275) 關于HashMap的源碼分析，可以參考：[http://github.thinkingbar.com/hashmap-analysis/](http://github.thinkingbar.com/hashmap-analysis/) LinkedHashMap，重寫了HashMap的迭代器、AddEntry、Entry等幾個方法和類，用一個雙向鏈表存儲元素加入的順序；這可以按照訪問順序排序，最近訪問的元素（get/put），會被放在鏈表的末尾，這是LRU算法（Least Recenty Used），最近最少使用算法。 ### ArrayList和LinkedList 關于ArrayList和LinkedList，ArrayList是基于數組的，這種方式將對象放在連續的位置中，讀取快，但是容量不足時需要進行數組擴容，性能降低，插入和刪除也慢；LinkedList是基于鏈表的，插入和刪除都快，但是查找麻煩，不能按照索引查找。所以說，對于構造一個隊列是用ArrayList或者LinkedList，是根據性能和方便來考慮的，比如LinkedList有removeLast()，ArrayList只能remove(index)，用LinkedList構造一個Queue的代碼演示如下： ~~~ class Queue { private LinkedList<String> llt; public Queue() { llt = new LinkedList<String>(); } public void add(String s) { llt.add(s); } public String get() { return llt.removeLast(); //隊列 //return llt.removeFirst(); //堆棧 } public boolean isNull() { return llt.isEmpty(); } } ~~~ ### ConcurrentModificationException ~~~ import java.util.*; import java.util.Map.Entry; class Test { public static void main(String[] args) throws Exception { HashMap<String,Integer> mTemp = new HashMap<String,Integer>(); mTemp.put("test1",1); Iterator<Entry<String,Integer>> iTemp = mTemp.entrySet().iterator(); //以下這行代碼會引發java.util.ConcurrentModificationException， //因為對聚集創建迭代器之后，進行遍歷或者修改操作時，如果遇到期望的修改計數器和實際的修改計數器不一樣的情況（modCount != expectedModCount） //就會報這個Exception，樂觀鎖的思想 //mTemp.put("test2",2); while(iTemp.hasNext()) { System.out.println(iTemp.next().getKey()); } //for循環,寫法更簡單一些，在編譯后，還是會被轉換為迭代器 for(Entry<String,Integer> e : mTemp.entrySet()) { System.out.println(e.getKey()); } ArrayList<string> al = new ArrayList<string>(); al.add("test"); for(String s : al) { Integer i = Integer.reverse((new java.util.Random().nextInt(100))); al.add(i.toString()); //這行代碼也會報ConcurrentModificationException } } } ~~~ 對于這種情況，可以使用java.util.concurrent包中的相關類，比如CopyOnWriteArrayList，就不會報這個異常了，因為CopyOnWriteArrayList類最大的特點就是，在對其實例進行修改操作（add/remove等）會新建一個數據并修改，修改完畢之后，再將原來的引用指向新的數組。這樣，修改過程沒有修改原來的數組，也就沒有了ConcurrentModificationException錯誤。 我們可以參考CopyOnWriteArrayList的源碼： ~~~ /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); } } ~~~ ConcurrentModificationException，表明：我正讀取的內容被修改掉了，你是否需要重新遍歷？或是做其它處理？這就是fast-fail（快速失敗機制）的含義。 雖然這只是在一個線程之內，并不是多線程的，我們同樣也可以這樣理解fast-fail： Fail-fast是并發中樂觀(optimistic)策略的具體應用，它允許線程自由競爭，但在出現沖突的情況下假設你能應對，即你能判斷出問題何在，并且給出解決辦法； 悲觀(pessimistic)策略就正好相反，它總是預先設置足夠的限制，通常是采用鎖(lock)，來保證程序進行過程中的無錯，付出的代價是其它線程的等待開銷。 快速失敗機制主要目的在于使iterator遍歷數組的線程能及時發現其他線程對Map的修改（如put、remove、clear等），因 此，fast-fail并不能保證所有情況下的多線程并發錯誤，只能保護iterator遍歷過程中的iterator.next()與寫并發. ### TreeSet和Collections.sort TreeSet是基于TreeMap的實現，底層數據結構是“紅黑樹”，數據加入時已經排好順序，存取及查找性能不如HashSet；Collections.sort是先把List轉換成數組，再利用“歸并排序”算法進行排序，歸并排序是一種穩定排序。 關于TreeMap的文章： [http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91](http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91) [http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html](http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html) [http://shmilyaw-hotmail-com.iteye.com/blog/1836431](http://shmilyaw-hotmail-com.iteye.com/blog/1836431) [http://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html](http://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html) [http://blog.csdn.net/chenhuajie123/article/details/11951777](http://blog.csdn.net/chenhuajie123/article/details/11951777) 對這兩種排序算法的性能比較如下（24核、64G內存，RHEL6.2）： 在數據已經基本排好順序的情況下，排序元素數目，在某個段內（大約是2萬-20萬），TreeSet更高效；其他數目下Collections.sort更高效； 在數據隨機性較強的情況下，排序元素數目，在1萬之內，相差不大，Collections.sort性能略高；在1萬之外，80萬之內，TreeSet性能明顯高于Collections.sort；80萬之外，Collection.sort性能更高；java.util.concurrent.ConcurrentSkipListSet這種基于“跳表”的線程安全的可排序類，在30萬之內，性能高于Collection.sort，30萬之外，性能低于Collection.sort，ConcurrentSkipListSet的排序性能總是低于TreeSet。 ConcurrentSkipListSet有一個平衡的樹形索引機構沒有的好處，就是在并發環境下其表現很好。 這里可以想象，在沒有了解SkipList這種數據結構之前，如果要在并發環境下構造基于排序的索引結構，那么也就紅黑樹是一種比較好的選擇了，但是它的平衡操作要求對整個樹形結構的鎖定，因此在并發環境下性能和伸縮性并不好。 代碼演示如下： ~~~ import java.util.TreeSet; import java.util.ArrayList; import java.util.Comparator; import java.util.Collections; import java.util.Arrays; import java.util.ListIterator; import java.util.Random; import java.util.Iterator; class Test { public static void main(String[] args) { final int LEN = 300000; final int SEED = 100000; Random r = new Random(); System.out.println("---------------------------"); long b = System.currentTimeMillis(); TreeSet<Temp> ts = new TreeSet<Temp>(new Comparator<Temp>(){ public int compare(Temp t1,Temp t2) {return t1.id-t2.id;} }); for(int i=0;i<LEN;i++) { ts.add(new Temp(r.nextInt(SEED))); } System.out.println(System.currentTimeMillis() - b); ArrayList<Temp> aTemp = new ArrayList<Temp>(); Iterator<Temp> it = ts.iterator(); while(it.hasNext()) { aTemp.add(it.next()); } System.out.println(System.currentTimeMillis() - b); System.out.println("---------------------------"); b = System.currentTimeMillis(); ArrayList<Temp> al = new ArrayList<Temp>(); for(int i=0;i<LEN;i++) { al.add(new Temp(r.nextInt(SEED))); } //split to the real excution unit /* Collections.sort(al,new Comparator<Temp>() { public int compare(Temp t1,Temp t2) {return t1.id-t2.id;} });*/ Temp[] a = new Temp[al.size()]; al.toArray(a); System.out.println(System.currentTimeMillis() - b); Arrays.sort(a,new Comparator<Temp>() { public int compare(Temp t1,Temp t2) {return t1.id-t2.id;} }); System.out.println(System.currentTimeMillis() - b); ListIterator<Temp> li = al.listIterator(); for(int i=0;i<a.length;i++) { li.next(); li.set(a[i]); } System.out.println(System.currentTimeMillis() - b); } } class Temp { public Temp(int id) {this.id = id;} public int id; } ~~~ 一個錯誤驗證： 增減進行過一個錯誤驗證，發現對一個對象使用TreeSet排序，和使用同樣數據Entry<String,Double>進行排序比較，性能很差。開始以為JDK對Entry做過優化，static/final之類，后來把對象也改成final，里面元素也改成final，發現性能依舊很差，完全不能解釋，感覺無法理解。 后來，發現是兩段代碼不一致，使用Entry進行排序的代碼有bug，導致排序的數據很少，所以顯得性能好。。。。 所以，無端的臆測還是不要的，建立在JDK深入理解的基礎上就好。 ### 另外一個排序思路 比如，取出Top 20，也不一定要全部排序，可以只取前20個，經驗證，小數據量時，性能也是非常高，大數據未驗證。代碼大致如下： ~~~ int n = 0; double minScore = 100; //Top20中最小的積分 String minKey = ""; //最小值所在的Key Map<String,Double> skuTop = new HashMap<String,Double>(); Set<String> styles = new HashSet<String>(); //過濾同款 for(String sku :tempSkuViewSkus.get(goodsUser.getKey())) { boolean filter = false; filter = filterSameStyle(sku,styles); if(filter) continue; //過濾不成功，直接continue Set<String> userSet = goodsUserView.get(sku); if(userSet == null || userSet.size() == 0) continue; //這一步，積分的計算，是最耗時的操作（性能瓶頸所在） double score = mathTools.getJaccardSimilar(goodsUser.getValue(), userSet); //前20個直接進入Map if(n++ < ConstMongo.maxRecomNum) { skuTop.put(sku, score); if(score < minScore) { minScore = score; minKey = sku; } continue; } if(score <= minScore) continue; //替換最小值 skuTop.remove(minKey); skuTop.put(sku, score); minScore = score; minKey = sku; for(Entry<String,Double> e : skuTop.entrySet()) { if(e.getValue() < minScore) { minScore = e.getValue(); minKey = e.getKey(); } } } ~~~ ### 正則表達式 ~~~ import java.util.regex.Matcher; import java.util.regex.Pattern; public class Hello { public static void main(String[] args) { Pattern pattern = Pattern.compile("正則表達式"); //Pattern pattern = Pattern.compile("Hello,正則表達式\\s[\\S]+"); Matcher matcher = pattern.matcher("正則表達式 Hello,正則表達式 World"); //替換第一個符合正則的數據 System.out.println(matcher.replaceFirst("Java")); } } ~~~ 常用的開發語言都支持正則表達式，但是其對于正則支持的程度是不一樣的。 Js正則：[http://msdn.microsoft.com/zh-cn/library/ae5bf541(VS.80).aspx](http://msdn.microsoft.com/zh-cn/library/ae5bf541(VS.80).aspx) Python正則：[http://www.cnblogs.com/huxi/archive/2010/07/04/1771073.html](http://www.cnblogs.com/huxi/archive/2010/07/04/1771073.html) Java正則： [http://www.blogjava.net/xzclog/archive/2006/09/19/70603.html](http://www.blogjava.net/xzclog/archive/2006/09/19/70603.html) [http://www.cnblogs.com/android-html5/archive/2012/06/02/2533924.html](http://www.cnblogs.com/android-html5/archive/2012/06/02/2533924.html) # 并發相關類 如下章節的內容有簡單使用演示：[http://blog.csdn.net/puma_dong/article/details/37597261#t5](http://blog.csdn.net/puma_dong/article/details/37597261#t5) # 壓縮解壓類 如下章節的內容有簡單使用演示：[http://blog.csdn.net/puma_dong/article/details/23018555#t20](http://blog.csdn.net/puma_dong/article/details/23018555#t20) # 其他工具類 定時器、日期、時間、貨幣等