總體介紹
之所以把HashSet和HashMap放在一起講解，是因為二者在Java里有著相同的實現(xiàn)，前者僅僅是對后者做了一層包裝颊咬，也就是說HashSet里面有一個HashMap（適配器模式）。因此本文將重點分析HashMap。
HashMap實現(xiàn)了Map接口犬庇，允許放入null
元素，除該類未實現(xiàn)同步外侨嘀，其余跟Hashtable
大致相同臭挽，跟TreeMap不同，該容器不保證元素順序飒炎，根據(jù)需要該容器可能會對元素重新哈希埋哟，元素的順序也會被重新打散，因此不同時間迭代同一個HashMap的順序可能會不同郎汪。 根據(jù)對沖突的處理方式不同赤赊，哈希表有兩種實現(xiàn)方式，一種開放地址方式（Open addressing）煞赢，另一種是沖突鏈表方式（Separate chaining with linked lists）抛计。Java HashMap采用的是沖突鏈表方式。
從上圖容易看出照筑，如果選擇合適的哈希函數(shù)吹截，put() 和 get() 方法可以在常數(shù)時間內(nèi)完成。但在對HashMap 進行迭代時凝危，需要遍歷整個table以及后面跟的沖突鏈表波俄。因此對于迭代比較頻繁的場景，不宜將HashMap 的初始大小設(shè)的過大蛾默。
有兩個參數(shù)可以影響HashMap 的性能：初始容量（inital capacity）和負載系數(shù)（load factor）懦铺。初始容量指定了初始 table 的大小，負載系數(shù)用來指定自動擴容的臨界值支鸡。當entry 的數(shù)量超過capacity* load_factor 時冬念，容器將自動擴容并重新哈希。對于插入元素較多的場景牧挣，將初始容量設(shè)大可以減少重新哈希的次數(shù)急前。
將對向放入到HashMap 或 HashSet 中時，有兩個方法需要特別關(guān)心：hashCode() 和 equals()瀑构。hashCode() 方法決定了對象會被放到哪個bucket里裆针，當多個對象的哈希值沖突時，equals() 方法決定了這些對象是否是“同一個對象”。所以据块，如果要將自定義的對象放入到HashMap 或 HashSet 中码邻，需要@Override hashCode() 和 equals() 方法。
方法剖析
get()
get(Object key) 方法根據(jù)指定的key 值返回對應(yīng)的value另假，該方法調(diào)用了getEntry(Object key) 得到相應(yīng)的entry像屋，然后返回 entry.getValue()。因此getEntry() 是算法的核心边篮。 算法思想是首先通過hash() 函數(shù)得到對應(yīng)bucket 的下標己莺，然后依次遍歷沖突鏈表，通過key.equals(k) 方法來判斷是否是要找的那個entry戈轿。
上圖中hash(k)&(table.length-1) * 等價于 hash(k)%table.length凌受，原因是HashMap* 要求table.length 必須是2的指數(shù)，因此table.length-1就是二進制低位全是1思杯，跟hash(k) 相與會將哈希值的高位全抹掉胜蛉，剩下的就是余數(shù)了。
// getEntry()方法
final Entry<K,V> getEntry(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[hash&(table.length-1)];//得到?jīng)_突鏈表
e != null; e = e.next) {//依次遍歷沖突鏈表中的每個entry
Object k;
//依據(jù)equals()方法判斷是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
put()
put(K key, V value) 方法是將指定的key, value 對添加到map 里色乾。該方法首先會對map 做一次查找誊册，看是否包含該元組，如果已經(jīng)包含則直接返回暖璧，查找過程類似于getEntry() 方法案怯；如果沒有找到，則會通過addEntry(int hash, K key, V value, int bucketIndex) 方法插入新的entry澎办，插入方式為頭插法嘲碱。
// addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);// 自動擴容，并重新哈希
hash = (null != key) ? hash(key) : 0;
bucketIndex = hash & (table.length - 1);// hash%table.length
}
// 在沖突鏈表頭部插入新的entry
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
remove()
remove(Object key) 的作用是刪除key 值對應(yīng)的entry局蚀，該方法的具體邏輯是在 removeEntryForKey(Object key) 里實現(xiàn)的麦锯。removeEntryForKey() 方法會首先找到key 值對應(yīng)的entry，然后刪除該entry（修改鏈表的相應(yīng)指針）琅绅。查找過程跟 getEntry() 過程類似离咐。
// removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
// hash&(table.length-1)
int i = indexFor(hash, table.length);
// 得到?jīng)_突鏈表
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 遍歷沖突鏈表
while (e != null) {
Entry<K,V> next = e.next;
Object k;
// 找到要刪除的entry
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++; size--;
// 刪除的是沖突鏈表的第一個entry
if (prev == e)
table[i] = next;
else
prev.next = next;
return e;
}
prev = e;
e = next;
}
return e;
}
HashSet
前面已經(jīng)說過HashSet 是對HashMap 的簡單包裝，對HashSet 的函數(shù)調(diào)用都會轉(zhuǎn)換成合適的HashMap 方法奉件，因此HashSet 的實現(xiàn)非常簡單，只有不到300行代碼昆著。這里不再贅述县貌。
// HashSet是對HashMap的簡單包裝
public class HashSet<E>
{
......
// HashSet里面有一個HashMap
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
......
// 簡單的方法轉(zhuǎn)換
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
......
}
原文地址：
https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/6-HashSet%20and%20HashMap.md
