Java編程思想——第17章 容器深入研究（two）

  • 2019 年 11 月 8 日
  • 筆記

六、隊列

　　排隊，先進先出。除並發應用外Queue只有兩個實現：LinkedList,PriorityQueue。他們的差異在於排序而非性能。

　　一些常用方法：

　　繼承自Collection的方法：

　　add 在尾部增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常

　　remove 移除並返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常

　　element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常

　　自帶的方法：

　　這些更適用於緩衝和並發訪問，最主要是不報異常啊

　　offer 在尾部添加一個元素並返回true 如果隊列已滿，則返回false

　　poll 移除並返問隊列頭部的元素 如果隊列為空，則返回null

　　peek 返回隊列頭部的元素 如果隊列為空，則返回null

　　put 添加一個元素 如果隊列滿，則阻塞

　　take 移除並返回隊列頭部的元素 如果隊列為空，則阻塞

七、理解Map

　　標準的Java類庫包含以幾種基本實現：HashMap,TreeMap,LinkedHashMap,WeakHashMap,ConcurrentHashMap,IdentityHahMap.

1.性能

　　普通的Map中get()方法呈線性搜索，執行速度相當慢，而hashMap使用了特殊的：散列碼來取代對鍵緩慢的搜索。

散列碼：“相對唯一”的，用以代表對象的int值。hashCode()是根類Object中的方法，所以所有Java對象都有散列碼，HashMap就是使用對象的hashCode()進行快速查詢的。

HashMap *：Map基於散列表的實現。插入和查詢“鍵值對”的開銷是固定的。可以通過構造器設置容量和負載因子以調節容器的性能。最常用的Map。

LinkedHashMap：使用鏈表維護內部順序，所以迭代訪問快。get訪問要慢一點點。

TreeMap：基於紅黑樹實現的。鍵會由Comparable或Comparator進行排序，是唯一帶有subMap()方法的Map;

      TreeMap<Integer, String> treeMap = new TreeMap<>();          treeMap.put(2, "two");          treeMap.put(1, "one");          treeMap.put(3, "three");          treeMap.put(4, "fore");          //fromKey-- 返回映射中鍵的低端點。          //fromInclusive-- true如果低端點要包含在返回的視圖。          //toKey-- 返回映射中鍵的高端點。          //toInclusive-- 這為true如果高端點要包含在返回的視圖。          NavigableMap<Integer, String> navigableMap = treeMap.subMap(1, true, 3, true);          System.out.println("values: " + navigableMap);
結果：   values: {1=one, 2=two, 3=three}

WeakHashMap：弱鍵(weak key)映射，允許釋放映射所指向的對象；如果映射之外沒有引用指向某個”鍵”，則此”鍵“可以被垃圾回收

ConcurrentHashMap：一種執行緒安全的Map.詳見 Java編程思想——第21章 並發 讀書筆記系列

IdentityHashMap：使用== 代替 equals()對鍵進行比較的散列映射。

　　對Map的鍵要求於Set中的元素要求一樣，任何鍵都要由一個equals()方法；如果是散列Map,鍵要實現hashCode()方法；如果是TreeMap,必須實現Comparable。

2.SortedMap

　TreeMap是現在的唯一實現，確保鍵處於排序狀態，以下是由SortedMap提供的方法：

    //返回當前Map使用的Comparator      public Comparator<? super K> comparator() {          return comparator;      }      //返回Map的第一個Key      public K firstKey() {          return key(getFirstEntry());      }      //返回Map的最後一個Key      public K lastKey() {          return key(getLastEntry());      }      //生成Map子集 由fromKey（包含） 到 toKey（不包含）的鍵值組成      public SortedMap<K,V> subMap(K fromKey, K toKey) {          return subMap(fromKey, true, toKey, false);      }      //生成Map子集 由鍵小於toKey的鍵值組成      public SortedMap<K,V> headMap(K toKey) {          return headMap(toKey, false);      }     //生成Map子集 由鍵大於或等於fromKey的鍵值組成      public SortedMap<K,V> tailMap(K fromKey) {          return tailMap(fromKey, true);      }

3.LinkedHashMap

　　為了提高速度LindedHashMap散列化所有的元素，但是遍歷鍵值對時又以元素的插入順序返回鍵值對。

　　*可以在構造函數中設定LinkedHashMap，使之採用基於訪問的最近最少使用（LRU）演算法。

// 初始化大小，加權因子，true開啟LRU演算法 false插入順序
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {          super(initialCapacity, loadFactor);          this.accessOrder = accessOrder;      }

八、散列與散列碼

HashMap使用equals()判斷當前的鍵是否與表中存在的鍵相同。

正確的equals()方法需滿足一下條件：

1）自反性。x.equals(x) 是true;

2）對稱性。x.equalse(y) 返回true y.equals(x)也得是true;

3）傳遞性。x.equals(y) 返回true ,y.equals(z) 返回true , x.equals(z)返回true;

4）一致性。如果對象中用於等價比較的資訊沒有變，那麼無論多少次 x.equals(y)返回值不會變

5）x.equals(null) 返回 false ；注意：(null).equals(x)報空指針。

強調：默認的Object.equals()只比較對象的地址，因此如果使用自己的類作為HashMap的Key,必須同時重載hashCode()和equals()。

hashCode()並不需要總是能夠返回唯一的標識碼，但是equals()方法必須嚴格的判斷兩個對象是否相等，作為鍵必須唯一否則系統報錯。

    @Override      public boolean equals(Object o) {          return o instanceof T && (i.equals(((T) o).i)));      }

instanceof檢查了此對象是否為null ，是null則返回false。

為速度而散列

　　以線性查詢的是最慢的查詢方式，存儲一組元素最快的數據結構是數組，所以使用它來標識鍵的資訊（注意，這裡說的是鍵資訊不是鍵本身）。由於數組不能調整容量，所以數組不保存鍵本身，而是通過鍵對象生成一個散列碼，將其作為數組的下標，這個散列碼就是由Object中的、或自己的類覆蓋的hashCode()生成的。

　　數組固定的問題解決了，但是鍵可以產生相同的下標，也就是說可能會有衝突。數組多大不重要，任何鍵總能在數組中找到它的位置。於是，查詢一個值的過程首先就是計算散列碼，然後使用散列碼查找數組。如果能夠保證沒有衝突（如果被查詢的值的數量是固定的，就有可能）。

　　通常，衝突由外部鏈接處理；數組並不直接保存值，而是保存值的list。然後對list中的值使用equals()方法進行線性查詢。這部分查找會比較慢，但是如果散列函數好的話，數組每個位置就有較少的值。

因此，不是查詢整個List而是快速的跳轉到數組的某個位置，只對很少的元素進行比較。這就是HashMap會如此快的原因。　

　　我們把散列表的數組稱為bucket(桶)，為了散布均勻且速度快，桶的容積通常使用質數或者2的整數次方，用LinkedList填充桶。

put()操作，計算key的hashCode(),找到桶中的位置，看LinkedList內容，有值用equals()與值的key相比，相等就替換，不等或者沒有值就在尾部加上新值。

覆蓋hashCode()

　　桶下標值是無法控制的，這個值依賴於具體的HashMap對象的容量，而容量的改變與容器的充滿程度和負載因子有關。hashCode()生成的結果，經過畜欄里後成為桶位的下標。

Joshua Blochw指出為寫出一份像樣的hashCode給出了知道：

1）給 int 變數 result 賦予某個非0常量，

2）為對象內每個有意義的域f(既每個可以做equals()操作的域)計算一個int 散列碼 c:

域類型：                                                                 計算：

boolean                                                                   c=(f?0:1)

byte、char、short、int                                           c=(int)f

float                                                                         c=(int)(f^(f>>>32))

double                                                                     long I =Double.doubleToLongBits(f); c=(int)(I^(I>>>32))

Object,其equals()調用這個域的equals()　　　　   c=f.hashCode()

數組　　　　　　　　　　　　　　　　　　　　 對每個元素應用上述規則　　　

3）合併計算得到散列碼

result = 37*result+c　　　

九、選擇介面的不同實現

容器之間的區別通常歸結於由什麼數據結構實現的。

　　比如：ArrayList和LinkedList都實現List介面，所以基本操作都是一樣的。然而ArrayList底層是數組實現的，而LinkedList是雙向鏈表實現的，其中每個對象包含數據的同時還包含直想鏈表中前一個和後一個元素的引用。因此更適合用於插入、刪除多的操作。而隨機訪問就應該選擇ArrayLIst，根據不同操作的性能選擇實現。

　　再比如：TreeSet、HashSet、LinkedHashSet都實現Set介面。每種都有不同行為：HashSet查詢速度最快；LinkedHashSet保持元素插入的次序；TreeSet基於TreeMap,生成一個處於排序狀態的Set。所以根據不同行為選擇的實現。

對List的選擇

　　對於數組支撐的List和ArrayList,無論列表的大小如何，訪問速度都是一樣的快。而對於LinkedList,訪問時間對於較大的列表將明顯增加。所以操作隨機訪問類型的操作，數組結構要比鏈表結構更合適。

　　當使用迭代器插入新元素時，對於ArrayList當列表變大時，開銷變大。但對於LinkedList，並不會隨著列表尺寸變化而明顯變化。因為，ArrayList插入時，必須為數組擴展空間，並將引用向前移動。而LinkedList則只需要鏈接新的元素，而不必修改列表中剩餘的元素。

　　LinkedList對List的端點會進行特殊處理——這使得LinkedList在作用於Queue時，效率提高。LInkedList中的插入和移除代價相當低廉，並且不會隨著列表尺寸發生變化，但是對於ArrayList插入操作的代價高昂，並且代價將隨列表尺寸增加而增加。

　　對於隨機訪問get() 和 set() 操作，ArrayList明顯速度快於LinkedList，因為LInkedLIst不是針對隨機訪問設計的。

　　最佳的做法時選擇ArrayList,只有經常插入和刪除而影響性能時才會選擇LinkedList.

對Set的選擇

　　HashSet的性能總比TreeSet好，特別是在添加和刪除元素時，而這兩個操作更為重要。TreeSet唯一好吃就是可以維持元素的排序；因為排序 所以TreeSet的迭代通常比HashSet快。

　　對於插入LinkedHashSet要比HashSet代價高；因為要額外維護鏈表所帶來的額外開銷。

對Map的選擇

　　除了IdentityHashMap外，所有的Map實現的插入操作都會隨著Map尺寸的變大而明顯變慢，但是查找操作代價要小得多。

　　TreeMap通常比HashMap慢，TreeMap是一種創建有序列表的方式。樹的行為是：保證有序，並且不必進行特殊排序。一旦填充TreeMap,就可以通過keySet()方法獲取鍵的Set試圖，然後調用toArray()形成鍵的數組。

　　當使用Map時HahsMap應該是首選，除非需要Map始終保持有序時使用TreeMap。

　　LinkedHashMap在插入時比HashMap慢一點，因為在維護散列數據結構得同時還要維護鏈表，也因此迭代速度更快。

　　IdentityHashMap具有完全不同的性能因為使用== 而不是 equals()來比較元素。

HashMap的性能因子

　　可以通過手動調整HashMap提高性能，這裡有些術語必須了解：

　　容量：表中的桶位。

　　初始容量：表在創建時所擁有的桶位數。HashMap和HashSet都可以通過構造函數指定初始化容量。

　　尺寸：表中當前存儲的項數。

　　負載因子：尺寸/容量。空表的負載因子是0，半滿表的負載因子是0.5，負載輕的表衝突可能性小，因此插入和查找更快，迭代則慢一些。HashMap和HashSet都具有指定負載因子的構造器，當負載達到該負載因子水平時，容器會自動增加容量，實現方式是使容量大致加倍，並重新將現有對象分布到新的桶位集中（再散列）。

　　HashMap使用默認的負載因子是0.75，更高的負載因子會增加查找代價。

十、實用方法

　　Collections類（注意不是Collection）內部有很多卓越的的靜態方法：

public static <T extends Object & Comparable<? super T>> T max/min(Collection<? extends T> coll) 返回Collection中最大或最小的元素-採用Collection內置的自然比較法,  　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　                (Collection<? extends T> coll, Comparator<? super T> comp) - 採用Comparator進行比較。  public static int indexOfSubList/lastIndexOfSubList(List<?> source, List<?> target) 返回target在source中第一次/最後一次出現的位置，找不到返回-1  public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) 使用newVal替換oldVal  public static void reverse(List<?> list) 逆轉所有元素次序  public static <T> Comparator<T> reverseOrder() 返回一個排序規則 逆轉自然順序 例：TreeSet tr=new TreeSet(Collections.reverseOrder());  public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) 逆轉參數的順序 例：TreeSet tr=new TreeSet(Collections.reverseOrder(new StrLenComparator()));  public static void rotate(List<?> list, int distance) 所有元素向後移動distance個位置，將末尾元素移到前面。  public static void shuffle(List<?> list) 隨機改變指定列表順序 參數列表：(List<?> list, Random rnd)時可使用自己的隨機機制  public static <T> void sort(List<T> list) 使用List中的自然排序 參數列表：(List<T> list, Comparator<? super T> c) 時，利用參數中排序規則排序  public static <T> void copy(List<? super T> dest, List<? extends T> src) 將src中的元素複製到dest  public static void swap(List<?> list, int i, int j) 替換list中位置i和位置j的元素  public static <T> void fill(List<? super T> list, T obj) 用元素x替換list中的元素  public static boolean disjoint(Collection<?> c1, Collection<?> c2) 兩個集合沒有任何相同元素時 返回true  public static int frequency(Collection<?> c, Object o) 返回集合中等於o的元素個數  public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) 在有排序的list中查找key元素的位置  public static <T> List<T> nCopies(int n, T o) 返回大小為n的List,且List不可改變，o為List中元素  emptyList()/emptyMap()/emptySet()返回不可變的空集合  singleton(T t)/singleList(T t)/singleMap(K key,V value) 產生不可變的集合，只包含參數中的元素

設定Collection或Map為不可修改

　　對“不可修改的”方法調用並不會產生編譯時檢查，但是完成轉換後，任何會改變容器內容的操作都會引起UnsupportedOperationException異常。

　　不可修改:Collections.unmodifiableXXX(XXX); 比如：Collections.unmodifiableList(new ArrayList(data));

同步

　　Collections.synchronizedXXX(XXX) 比如：Collections.synchronizedList(new ArrayList(data)) ; 一旦發現兩個執行緒同時操作就會拋出ConcurrentMdificationException　　　　　　

VirMach 便宜 VPS

QNews

QNews