Thinking in java基礎(chǔ)之集合框架

---

大家都知道我的習(xí)慣，先上圖說話。

集合簡介(容器)
把具有相同性質(zhì)的一類東西，匯聚成一個整體，就可以稱為集合，例如這里有20個蘋果，我們把每一個蘋果當(dāng)成一個東西（一個對象），然后我們借用袋子把這20個蘋果裝起來，而這個袋子就是集合（也叫容器）。然后呢，我們按照不同的方法裝，就是不同的框架。

換句話說，集合框架就是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。

鏈表(數(shù)據(jù)結(jié)構(gòu))
LinkedList的結(jié)構(gòu)

public class chain { private class Data{private Object obj;private Data next = null;Data(Object obj){this.obj = obj;} } private Data first = null; public void insertFirst(Object obj){Data data = new Data(obj);data.next = first;first = data; }public Object deleteFirst() throws Exception{ if(first == null)throw new Exception("empty!"); Data temp = first;first = first.next;return temp.obj; } public Object find(Object obj) throws Exception{ if(first == null) throw new Exception("LinkedList is empty!"); Data cur = first; while(cur != null){ if(cur.obj.equals(obj)){ return cur.obj; } cur = cur.next; } return null; } public void remove(Object obj) throws Exception{ if(first == null) throw new Exception("LinkedList is empty!"); if(first.obj.equals(obj)){ first = first.next; }else{ Data pre = first; Data cur = first.next; while(cur != null){ if(cur.obj.equals(obj)){ pre.next = cur.next; } pre = cur; cur = cur.next; } } } public boolean isEmpty(){ return (first == null); } public void display(){if(first == null)System.out.println("empty");Data cur = first;while(cur != null){System.out.print(cur.obj.toString() + " -> ");cur = cur.next;}System.out.print("\n"); } public static void main(String[] args) throws Exception {chain ll = new chain();ll.insertFirst(4);ll.insertFirst(3);ll.insertFirst(2);ll.insertFirst(1);ll.display();ll.deleteFirst();ll.display();ll.remove(3);ll.display();System.out.println(ll.find(1));System.out.println(ll.find(4)); } }

3.Collection

• ①List
  保存輸入的順序，而且可以重復(fù)的存儲相關(guān)元素。
  ArrayList(隨機訪問)(數(shù)組線性表)
  ArrayList數(shù)組線性表的特點為:類似數(shù)組的形式進(jìn)行存儲，因此它的隨機訪問速度極快。
  ArrayList數(shù)組線性表的缺點為:不適合于在線性表中間需要頻繁進(jìn)行插入和刪除操作。因為每次插入和刪除都需要移動數(shù)組中的元素。可以這樣理解ArrayList就是基于數(shù)組的一個線性表，只不過數(shù)組的長度可以動態(tài)改變而已。ArrayList線程不安全，
  LinkedList(頻繁刪除添加)(鏈?zhǔn)骄€性表)
  您要頻繁的從列表的中間位置添加和除去元素，而只要順序的訪問列表元素，那么，LinkedList 實現(xiàn)更好。
  可以這樣理解LinkedList就是一種雙向循環(huán)鏈表的鏈?zhǔn)骄€性表，只不過存儲的結(jié)構(gòu)使用的是鏈?zhǔn)奖矶选?br /> Vector(向量)
  如果一定在多線程使用List的，您可以使用Vector，因為Vector和ArrayList基本一致，區(qū)別在于Vector中的絕大部分方法都使用了同步關(guān)鍵字修飾，這樣在多線程的情況下不會出現(xiàn)并發(fā)錯誤哦，還有就是它們的擴(kuò)容方案不同，ArrayList是通過原始容量*3/2+1,而Vector是允許設(shè)置默認(rèn)的增長長度，Vector的默認(rèn)擴(kuò)容方式為原來的2倍。
  切記Vector是ArrayList的多線程的一個替代品。
  Stack(棧)
  在各種List中，最好的做法是以ArrayList作為缺省選擇。當(dāng)插入、刪除頻繁時，使用LinkedList();Vector總是比ArrayList慢，所以要盡量避免使用。使用最多的是ArrayList。
• ②Set
  Set子接口: 無序，不允許有重復(fù)的元素,最多允許有一個null元素對象。
  HashSet(沒有順序)
  您會使用 HashSet 存儲重復(fù)自由的集合。考慮到效率，添加到 HashSet 的對象需要采用恰當(dāng)分配哈希碼的方式來實現(xiàn)hashCode()方法。雖然大多數(shù)系統(tǒng)類覆蓋了Object中缺省的hashCode()和equals()實現(xiàn)，但創(chuàng)建您自己的要添加到HashSet的類時，別忘了覆蓋 hashCode()和equals()。
  LinkedHashSet(添加順序會被記錄)
  如果想跟蹤添加給HashSet的元素的順序，LinkedHashSet實現(xiàn)會有幫助。 按照元素的插入順序來訪問各個元素。它提供了一個可以快速訪問各個元素的有序集合。
  TreeSet(按照比較器排序)
  當(dāng)您要從集合中以有序的方式插入和抽取元素時，TreeSet實現(xiàn)會有用處。
  為了能順利進(jìn)行。添加到TreeSet的元素必須是可排序的。
• 在各種Set中，HashSet通常優(yōu)于TreeSet（插入、查找）。只有當(dāng)需要產(chǎn)生一個經(jīng)過排序的序列，才用TreeSet。
  TreeSet存在的唯一理由：能夠維護(hù)其內(nèi)元素的排序狀態(tài)。
• ③Queue(隊列)

4.Map
Map接口用于維護(hù)鍵/值對(key/value pairs)。該接口描述了從不重復(fù)的鍵到值的映射。
HashMap
在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。
LinkedHashMap(包含插入順序)
以插入順序?qū)㈥P(guān)鍵字/值對添加進(jìn)鏈接哈希映像中
TreeMap(自定義順序)
但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。
WeakHashMap
它使用WeakReference(弱引用)來存放哈希表關(guān)鍵字。使用這種方式時，當(dāng)映射的鍵在 WeakHashMap 的外部不再被引用時，垃圾收集器會將它回收，但它將把到達(dá)該對象的弱引用納入一個隊列。WeakHashMap的運行將定期檢查該隊列，以便找出新到達(dá)的 弱應(yīng)用。當(dāng)一個弱引用到達(dá)該隊列時，就表示關(guān)鍵字不再被任何人使用，并且已經(jīng)被收集起來。然后WeakHashMap便刪除相關(guān)的映射。
HashTable

• 在各種Map中HashMap用于快速查找，使用的最多。
• Array
  我們都知道，由于Array(數(shù)組)通常意義上講只是一個單純的線性序列，又基于Native(本地方法)，憑此它的效率歷來便號稱Java中最高。所以通常我們也都承認(rèn)Java中效率最高的存儲方式就是使用數(shù)組。但是，由于數(shù)組初始化后大小固定，索引不能超出下標(biāo)，缺少靈活的擴(kuò)展功能等原因，使得很多人放棄了數(shù)組的使用， 轉(zhuǎn)而使用Collection,List,Map,Set等接口處理集合操作。
• 當(dāng)元素個數(shù)固定，用Array，因為Array效率是最高的。
• 比較器(Comparator和Comparable接口)
  在“集合框架”中有兩種比較接口：Comparable接口和Comparator接口。像String和Integer
  等Java內(nèi)建類實現(xiàn) Comparable接口以提供一定排序方式，但這樣只能實現(xiàn)該接口一次。對于那些沒有實現(xiàn)Comparable接口的類、或者自定義的類，您可以通過 Comparator接口來定義您自己的比較方式。
  Comparable接口
  在java.lang包中，Comparable接口適用于一個類有自然順序的時候。假定對象集合是同一類型，該接口允許您把集合排序成自然順序。
  (1) int compareTo(Object o): 比較當(dāng)前實例對象與對象o，如果位于對象o之前，返回負(fù)
  值，如果兩個對象在排序中位置相同，則返回0，如果位于對象o后面，則返回正值
  在 Java 2 SDK版本1.4中有二十四個類實現(xiàn)Comparable接口。下表展示了8種基本類型的自然排序。雖然一些類共享同一種自然排序，但只有相互可比的類才能排序。
  類排序 BigDecimal,BigInteger,Byte, Double, Float,Integer,Long,Short 按數(shù)字大小排序
  Character 按 Unicode 值的數(shù)字大小排序
  String 按字符串中字符 Unicode 值排序
  利用Comparable接口創(chuàng)建您自己的類的排序順序，只是實現(xiàn)compareTo()方法的問題。通常就是依賴幾個數(shù)據(jù)成員的自然排序。同時類也應(yīng)該覆蓋equals()和hashCode()以確保兩個相等的對象返回同一個哈希碼。
  Comparator接口
  若一個類不能用于實現(xiàn)java.lang.Comparable，或者您不喜歡缺省的Comparable行為并想提供自己的排序順序(可能多種排序方式)，你可以實現(xiàn)Comparator接口，從而定義一個比較器。
  (1)int compare(Object o1, Object o2): 對兩個對象o1和o2進(jìn)行比較，如果o1位于o2
  的前面，則返回負(fù)值，如果在排序順序中認(rèn)為o1和o2是相同的，返回0，如果o1位于o2的
  后面，則返回正值“與Comparable相似，0返回值不表示元素相等。一個0返回值只是表示兩個對象排在同一位置。由Comparator用戶決定如何處理。如果兩個不相等的元素比較的結(jié)果為零，您首先應(yīng)該確信那就是您要的結(jié)果，然后記錄行為。”
  (2)boolean equals(Object obj): 指示對象obj是否和比較器相等。
  “該方法覆寫Object的equals()方法，檢查的是Comparator實現(xiàn)的等同性，不是處于比較
  狀態(tài)下的對象。”
• Iterator(迭代模式)
  調(diào)用iterator()方法，返回Iterator<T>對象，Iterator<T>對象有hasnext();next();方法提過循環(huán)
  Collection接口有iterator()方法。Map.entrySet()返回Set<Map.Entry<K,V>>,然后調(diào)用Collection對應(yīng)的iterator();方法。
  Iterator iterator = Collection.iterator();
  while(iterator.hasNext()) {
  Object iter=iterator.next();
  System.out.println("object=" +object);
  }
  Iterator iterator = Map.entrySet().iterator();
  while (iterator .hasNext()) {
  Map.Entry entry = (Map.Entry) iterator .next();
  Object key = entry.getKey();
  Object value = entry.getValue();
  System.out.println("key=" + key + " value=" + value);
  }
• 工具類Collections and Arrays(靜態(tài)方法)
  Collections(常用方法)
  addAll添加
  shuffle混排
  binarySearch二分查搜索法
  reverse反轉(zhuǎn)
  fill 替換
  max/min 找出最大/最小(根據(jù)默認(rèn)的自然排序或者自定義排序規(guī)則)
  sort排序(根據(jù)默認(rèn)的自然排序或者自定義排序規(guī)則)
  Arrays
  binarySearch二分搜索法
  sort排序
  copyOf復(fù)制
  equals判斷相等
  fill指定分配、替換
  toString 返貨字符串
  hashCode哈希嗎
  詳情參考中文API?oracle官網(wǎng)API
• 總結(jié)
  在實際工作中，若用到集合框架，最常用的是ArrayList,HashSet,HashMap。這三者也是首先考慮的。而且，因為TreeXXX繼承SortedXXX，所以用TreeXXX都是排序的。
• 參看文獻(xiàn)
  java集合框架的講解
  JAVA中關(guān)于鏈表的操作和基本算法
  java的集合框架最全詳解（圖）
  集合_java集合框架
  《Thinking in java》
  《算法與數(shù)據(jù)結(jié)構(gòu)》-------java語言描述 清華大學(xué)出版社

作者： 慕曉白?
鏈接：http://www.imooc.com/article/7577
來源：慕課網(wǎng)
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Thinking in java基础之集合框架的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。