1 Set與儲存順序
#加入Set的元素必須定義equals()方法以確保物件的唯一性。
hashCode()只有這個類別被置於HashSet或LinkedHashSet中時才是必需的。但是對於良好的程式設計風格而言，你應該在覆寫equals()方法時，總是同時覆寫hashCode()方法。
如果一個物件被用於任何種類的排序容器中，例如SortedSet（TreeSet 是其唯一實作），那麼它必須實作Comparable介面。
注意，SortedSet的意思是「按物件的比較函數對元素排序”，而不是指“元素插入的順序”。 插入順序用LinkedHashSet#來儲存。
2 佇列
3 Map
#映射表（也稱為關聯陣列#Associative Array）。
3.1 效能
HashMap使用了特殊的值，稱作散列碼（hash code），來取代對鍵的緩慢搜尋。雜湊碼是「相對唯一」的、用以代表物件的int值，它是透過將該物件的某些資訊進行轉換而產生的。
hashCode()是根類別Object中的方法，因此所有物件都能產生雜湊碼。
對Map中使用的鍵的要求與Set中的元素的要求一樣：
4 雜湊與雜湊碼
HashMap使用equals()判斷目前的鍵是否與表中存在的鍵相同。
預設的Object.equals()只是比較物件的位址。 如果要使用自己的類別作為HashMap的鍵，必須同時重寫hashCode()和equals()
對稱性。
傳遞性。
一致性。
對任何不是null的x，x.equals(null)一定回傳false。
使用雜湊的目的在於：想要使用一個物件來尋找另一個物件。 Map的實作類別使用雜湊是為了
提高查詢速度#######。 ############雜湊的價值在於速度###：###雜湊使得查詢得以快速進行###。由於瓶頸位於######查詢速度######，因此解決方案之一就是保持鍵的排序狀態，然後使用###Collections.binarySearch()###進行查詢。 ############散列則更進一步，它將鍵保存在某處，以便能夠很快找到######。儲存一組元素最快的資料結構是數組，所以用它來表示鍵的資訊（請小心留意，我是說鍵的信息，而不是鍵本身）。但是因為數組不能調整容量，因此就有一個問題：我們希望在Map中保存數量不確定的值，但是如果鍵的數量被數組的容量限制了，該怎麼辦？ ###答案就是：陣列並不會保存鍵本身。而是透過鍵物件產生一個數字，將其作為數組的下標。這個數字就是散列碼，由定義在Object中的、且可能由你的類別覆寫的hashCode()方法（在計算機科學的術語中稱為散列函數#）生成。
為解決陣列容量固定的問題，不同的鍵可以產生相同的下標。也就是說，可能會有衝突，即散列碼不必是獨一無二的#。因此，數組多大就不重要了，任何鍵總能在數組中找到它的位置。
4.2 理解散列
綜上，散列就是將一個物件產生一個數字保存下來（作為數組的下標），然後在尋找這個物件時直接找到這個數字就可以了，所以散列的目的是為了提高查找速度，而手段是將一個物件產生的數字與其關聯並保存下來（透過數組，稱為散列表）。這個產生的數字就是散列碼。而產生這個雜湊碼的方法稱為雜湊函數（hashCode()）。
4.3 HashMap查詢過程（快速原因）
# 因此，HashMap中查詢一個key的過程就是：
因此，不是查詢整個list，而是快速地跳到陣列的某個位置，只對很少的元素進行比較。這便是HashMap會如此快速的原因。
4.4 簡單散列Map的實作
散列表中的插槽（slot）通常稱為桶位（bucket）
-
為使雜湊均勻，桶的數量通常使用質數（JDK5中是質數，JDK7中已經是2的整數次方了）。
事實證明，質數其實並不是散列桶的理想容量。近來，（透過廣泛的測試）Java的雜湊函數都使用2的整數次方。對現代處理器來說，除法與求餘數是最慢的操作。使用2的整數次方長度的散列表，可用掩碼代替除法。因為get()是使用最多的操作，求餘數的%操作是其開銷最大的部分，而使用2的整數次方可以消除此開銷（也可能對hashCode()有些影響）。
get()方法按照與put()方法相同的方式計算在buckets數組中的索引，這很重要，因為這樣可以保證兩個方法可以計算出相同的位置。
package net.mrliuli.containers;
import java.util.*;public class SimpleHashMap<K, V> extends AbstractMap<K, V> { // Choose a prime number for the hash table size, to achieve a uniform distribution:
static final int SIZE = 997; // You can't have a physical array of generics, but you can upcast to one:
@SuppressWarnings("unchecked")
LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];
@Override public V put(K key, V value){ int index = Math.abs(key.hashCode()) % SIZE; if(buckets[index] == null){
buckets[index] = new LinkedList<MapEntry<K,V>>();
}
LinkedList<MapEntry<K,V>> bucket = buckets[index];
MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
boolean found = false;
V oldValue = null;
ListIterator<MapEntry<K,V>> it = bucket.listIterator(); while(it.hasNext()){
MapEntry<K,V> iPair = it.next(); if(iPair.equals(key)){
oldValue = iPair.getValue();
it.set(pair); // Replace old with new
found = true; break;
}
} if(!found){
buckets[index].add(pair);
} return oldValue;
}
@Override public V get(Object key){ int index = Math.abs(key.hashCode()) % SIZE; if(buckets[index] == null) return null; for(MapEntry<K,V> iPair : buckets[index]){ if(iPair.getKey().equals(key)){ return iPair.getValue();
}
} return null;
}
@Override public Set<Map.Entry<K,V>> entrySet(){
Set<Map.Entry<K,V>> set = new HashSet<Map.Entry<K, V>>(); for(LinkedList<MapEntry<K,V>> bucket : buckets){ if(bucket == null) continue; for(MapEntry<K,V> mpair : bucket){ set.add(mpair);
}
} return set;
} public static void main(String[] args){
SimpleHashMap<String, String> m = new SimpleHashMap<String, String>(); for(String s : "to be or not to be is a question".split(" ")){
m.put(s, s);
System.out.println(m);
}
System.out.println(m);
System.out.println(m.get("be"));
System.out.println(m.entrySet());
}
}登入後複製
4.5 覆寫hashCode()
# 設計`hashCode()`時要考慮的因素：
#最重要的因素：無論何時，對同一相物件呼叫hashCode()都應該產生#相同的值。
此外，不應該使hashCode()依賴具有唯一性的物件訊息，尤其是使用this的值，這只能產生很糟糕的hashCode()。因為這樣做無法產生一個新的鍵，使之與put()中原始的鍵值對中的鍵相同。即應該使用物件內有意義的辨識資訊。也就是說，它必須基於物件的內容來產生雜湊碼。
但是，透過hashCode() equals()必須能夠完全確定物件的身份。
因為在生成桶的下標前，hashCode()還需要進一步處理，所以散列碼的生成範圍並不重要，只要是int即可。
好的hashCode()應該會產生分佈均勻的雜湊碼。
《Effective Java™ Programming Language Guide (Addison-Wesley, 2001)》為怎樣寫出一個像樣的hashCode()給了一個基本的指導：
給int變數result賦予一個非零值常數，如17
#为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c：
| 域类型 | 计算 |
|---|
| boolean | c=(f?0:1) |
| byte、char、short或int | c=(int)f |
| long | c=(int)(f^(f>>>32)) |
| float | c=Float.floatToIntBits(f); |
| double | long l = Double.doubleToLongBits(f); |
| Object,其equals()调用这个域的equals() | c=f.hashCode() |
| 数组 | 对每个元素应用上述规则 |
3. 合并计算散列码：result = 37 * result + c;
4. 返回result。
5. 检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。
5 选择不同接口的实现
5.1 微基准测试的危险（Microbenchmarking dangers）
已证明0.0是包含在Math.random()的输出中的，按照数学术语，即其范围是[0,1)。
5.2 HashMap的性能因子
HashMap中的一些术语：
容量（Capacity）：表中的桶位数（The number of buckets in the table）。
初始容量（Initial capacity）：表在创建时所拥有的桶位数。HashMap和HashSet都具有允许你指定初始容量的构造器。
尺寸（Size）：表中当前存储的项数。
负载因子（Loadfactor）：尺寸/容量。空表的负载因子是0，而半满表的负载因子是0.5，依此类推。负载轻的表产生冲突的可能性小，因此对于插入和查找都是最理想的（但是会减慢使用迭代器进行遍历的过程）。HashMap和HashSet都具有允许你指定负载因子的构造器，表示当负载情况达到该负载的水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重新将现有对象分布到新的桶位集中（这被称为再散列）。
HashMap使用的默认负载因子是0.75（只有当表达到四分之三满时，才进行再散列），这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间，但会增加查找代价，这很重要，因为查找是我们在大多数时间里所做的操作（包括get()和put()）。
6 Collection或Map的同步控制
Collections类有办法能够自动同步整个容器。其语法与“不可修改的”方法相似：
package net.mrliuli.containers;
import java.util.*;public class Synchronization { public static void main(String[] args){
Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
List<String> list = Collections.synchronizedList(new ArrayList<String>()); Set<String> s = Collections.synchronizedSet(new HashSet<String>()); Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
}
}登入後複製
6.1 快速报错（fail-fast）
Java容器有一种保护机制能够防止多个进行同时修改同一个容器的内容。Java容器类类库采用快速报错（fail-fast）机制。它会探查容器上的任何除了你的进程所进行的操作以外的所有变化，一旦它发现其他进程修改了容器，就会立刻抛出ConcurrentModificationException异常。这就是“快速报错”的意思——即，不是使用复杂的算法在事后来检查问题。
package net.mrliuli.containers;
import java.util.*;public class FailFast { public static void main(String[] args){
Collection<String> c = new ArrayList<>();
Iterator<String> it = c.iterator();
c.add("An Object"); try{
String s = it.next();
}catch(ConcurrentModificationException e){
System.out.println(e);
}
}
}登入後複製
相关文章：
Java编程思想学习课时（三）第15章-泛型
Java编程思想学习课时（五）第18章-Java IO系统
以上是Java程式設計思想學習課程（四）第17章-容器深入探討的詳細內容。更多資訊請關注PHP中文網其他相關文章！
