簡單講解Java集合架構中的HashSet與HashMap。
簡介
- 本篇将簡單講解Java集合架構中的HashSet與HashMap。
散列集（HashSet）
快速入門
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public Iterator<E> iterator() {
return map.keySet().iterator();
} - 上面說到，在JDK 1.8之後，當連結清單長度超過門檻值8時，連結清單将轉為紅黑樹；當連結清單長度小于6時，紅黑樹重新轉為連結清單。那麼為什麼門檻值是8呢？
- 門檻值定義為8，符合數學機率論上的泊松分布Poisson。根據泊松分布，一個桶bucket是很難被填滿達到長度8的。
- 一旦用于存儲資料的連結清單長度達到門檻值8，則很大的可能是該HashSet所使用的散列函數性能不佳、或存在惡意代碼向集中添加了很多具有相同散列碼的值，此時轉為平衡二叉樹可以提高性能。
散清單
- 連結清單LinkedList、數組Array或數組清單ArrayList都有一個共同的缺點：根據值查找元素速度慢。一旦存放的資料較多，查找速度将十分緩慢。
- 如果應用中開發者不在意元素的排列順序，此時推薦使用的資料結構為散清單。散清單用于快速查找對象。
- 使用散清單的關鍵是對象必須具備一個散列碼，通過對象内HashCode()方法即可計算得到對象的散列碼。一般情況下，不同資料的對象将産生不同的散列碼。
- 下表顯示了使用String類中hashCode()方法成的散列碼：
| 字元串 | 散列碼 |
|---|---|
| "Lee" | 76268 |
| "lee" | 107020 |
| "eel" | 100300 |
- 在Java中，散清單HashTable使用動态數組加連結清單或紅黑樹的形式實作。
- 動态數組中的每個位置被稱為桶bucket。要想查找元素位于散清單中的位置，需要首先計算元素的散列碼，然後與桶的總數取餘，所得到的結果就是儲存這個元素的桶的索引。
- 假設動态數組為table，對象a的散列碼為hashCode，則元素将存放在table的索引為hashCode % table.size()，通常将該索引值成為散列值，它與散列碼是不一樣的。
- 例如，如果某個對象的散列碼為76268，并且有128個桶，那麼這個對象應該儲存在第108号桶中，因為76268%128=108。
- 如果在這個桶中沒有其他的元素，此時将元素直接插入到桶中即可；但如果桶已經被填充，這種現象被稱為散列沖突hash collision。發生散列沖突，需要将新對象與桶中的所有對象進行比較，檢視這個對象是否已經存在。
- 此時如果散列碼合理地随機分布（可以了解為散列函數hashCode()合理），桶的數目也足夠大，需要比較的次數就會很少。
- 在Java 8中，桶滿時會從連結清單變為平衡二叉樹。如果選擇的散列函數不好，會産生很多沖突，或者如果有惡意代碼試圖在散清單中填充多個有相同散列碼的值，這樣改為平衡二叉樹能提高性能。
- 如果需要更多地控制散清單的性能，可以指定一個初始的桶數。桶數是指用于收集具有相同散列值的桶的數目。如果要插入到散清單中的元素太多，就會增加沖突數量，降低檢索的性能。
- 如果大緻知道最終會有多少個元素要插入到散清單中，就可以設定桶數。通常，将桶數設定為預計元素個數的75%~150%。有些研究人員認為：最好将桶數設定為一個素數，以防止鍵的聚集。不過，對此并沒有确鑿的證據。
- 标準類庫使用的桶數是2的次幂，預設值為16（為表大小提供的任何值，都将自動轉換為2的下一個幂值）。
- 但是，并不總能夠知道需要存儲多少個元素，也有可能最初的估計過低。如果散清單太滿，就需要再散列rehashed。如果要對散清單再散列，就需要建立一個桶數更多的表，并将所有元素插入到這個新表中，然後丢棄原來的表。裝填因子load factor可以确定何時對散清單進行再散列。
- 例如，如果裝填因子是0.75（預設值），說明表中已經填滿了75%以上，就會自動再散列，新表的桶數是原來的兩倍。對于大多數程式來說，裝填因子為0.75是合理的。
- 散清單可以用于實作很多重要的資料結構，其中最簡單的是集類型。集是沒有重複元素的元素集合，其中add方法首先會在這個集中查找要添加的對象，如果不存在，就添加這個對象。
- Java集合架構提供了一個HashSet類，它實作了基于散清單的集。可以用add方法添加元素。contains方法已經被重新定義，用來快速查找某個元素是否已經在集中。它隻檢視一個桶中的元素，而不必檢視集合中所有元素。
- 散列集疊代器将依次通路所有的桶，由于散列将元素分散在表中，是以會以一種看起來随機的順序通路元素。隻有不關心集合中元素的順序時，才應該使用HashSet。
- 而HashSet的實作基于HashMap，在随後會對HashMap的部分源碼進行分析，以了解其初始容量及擴容機制。
散列映射（HashMap）
- 底層原理：動态數組加單向連結清單或紅黑樹。JDK 1.8之後，當連結清單長度超過門檻值8時，連結清單将轉換為紅黑樹。預設散清單中的動态數組長度為16，散列因子為0.75，擴容門檻值為12。
- 擴容機制：擴容後散清單中的動态數組長度，變為舊動态數組的兩倍。擴容門檻值為散列因子與動态數組長度的乘積。
- 以下為HashMap中代表單向連結清單結構的Node<K, V>類，與代表紅黑樹結構的TreeNode<K, V>類。
// HashMap.java源碼
// 基于單向連結清單的用于存儲資料的對象
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
// 基于紅黑樹的用于存儲資料的對象
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...
} 二次散列
- 散列映射HashMap隻對鍵進行散列，與鍵關聯的值不進行散列。以下為HashMap中的部分源碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} - 所有使用put()方法存入HashMap中的鍵值對，都會在内部調用putVal()進行添加元素操作。putVal()方法的第一個參數則需要提供key的散列碼。
- 此處并沒有直接使用key.hashCode()，而是使用了HashMap中的hash()方法對key進行二次散列。二次散列可以了解為在對象調用它的散列函數之後，再進行一次額外的計算。二次散列有助于獲得更好的散列碼。
擴容機制
- HashMap中的動态數組初始容量為16，預設的散列因子為0.75，即在容量到達16 * 0.75 = 12時，會對動态數組進行擴容處理，上限容量被稱為threshold。
- 擴容後的HashMap，其動态數組容量為原來的2倍，由于散列因子不會改變，是以threshold也為原來的2倍。
- 以下為HashMap中resize()、putVal()的源碼：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 第一個resize()是進行動态數組Node<K, V>[]初始化的操作，不會進行擴容
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 當HashMap中元素數量大于門檻值threshold，則會進行擴容resize()操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} - 通過源碼可以知道，HashMap在初始化的時候并不會立即為動态數組配置設定記憶體，直到調用putVal()為止，才會在putVal()中調用resize()方法初始化動态數組。
- 動态數組Node<K, V>[]将在resize()中完成初始化或擴容的操作。
- 其中有關初始化的關鍵代碼為：
newCap = DEFAULT_INITIAL_CAPACITY; // DEFAULT_INITIAL_CAPACITY = 1 << 4，即預設大小為16。
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // threshold = newCap * 0.75，即預設為12。 - 有關于擴容的關鍵代碼為：
if (oldCap > 0) { // 當動态數組擁有預設容量時，如果再次調用resize()，則一定會進行擴容操作
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { // 容量為原來的2倍
newThr = oldThr << 1; // 門檻值為原來的2倍
}
} 總結
- 以上為所有關于HashSet、HashMap的粗略介紹。
- 如果希望了解更多的内容，可以前往JDK閱讀源碼。
![java HashMap 與HashTable的差別[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)