HashMap源碼隨筆
源碼第一塊：
概述：
Map 接口的基于哈希表的實現。此實現提供所有可選的映射操作，并允許 null 值和 null 鍵。（HashMap 類大致等同于 Hashtable，只不過它是不同步的，并且允許 null。此類不保證地圖的順序;特別是，它不保證訂單會隨著時間的推移保持不變。此實現為基本操作（get 和 put）提供恒定時間性能，假設哈希函數將元素正確地分散在存儲桶中。對集合視圖進行迭代所需的時間與 HashMap 實例的“容量”（存儲桶數量）及其大小（鍵值映射數量）成正比。因此，如果迭代性能很重要，則不要將初始容量設置得太高（或負載系數太低），這一點非常重要。HashMap 實例有兩個影響其性能的參數：初始容量和負載因子。容量是哈希表中的存儲桶數量，初始容量只是創建哈希表時的容量。負載因子是衡量哈希表在容量自動增加之前允許的滿量。當哈希表中的條目數超過負載因子和當前容量的乘積時，將重新哈希表（即重新構建內部數據結構），以便哈希表的桶數大約是其兩倍。作為一般規則，默認負載系數 （0.75） 在時間和空間成本之間提供了良好的權衡。較高的值會減少空間開銷，但會增加查找成本（反映在 HashMap 類的大多數操作中，包括 get 和 put）。在設置映射的初始容量時，應考慮映射中的預期條目數及其負載系數，以最大程度地減少重新散列操作的次數。如果初始容量大于最大條目數除以負載因子，則不會發生重新散列操作。如果要在 HashMap 實例中存儲許多映射，則創建具有足夠大容量的映射將允許更有效地存儲映射，而不是讓它根據需要執行自動重新散列以增加表。請注意，使用具有相同 hashCode（） 的多個鍵肯定會降低任何哈希表的性能。為了改善影響，當鍵具有可比性時，此類可以使用鍵之間的比較順序來幫助打破聯系。請注意，此實現不是同步的。如果多個線程同時訪問哈希映射，并且至少有一個線程在結構上修改了映射，則必須在外部同步該映射。（結構修改是添加或刪除一個或多個映射的任何操作;僅更改與實例已包含的鍵關聯的值不是結構修改。這通常是通過在自然封裝地圖的某個對象上進行同步來實現的。如果不存在此類對象，則應使用 Collections.synchronizedMap 方法“包裝”映射。這最好在創建時完成，以防止意外的不同步訪問地圖： Map m = Collections.synchronizedMap（new HashMap（...））;此類的所有“集合視圖方法”返回的迭代器都是快速失敗的：如果在創建迭代器后的任何時間對映射進行結構修改，則迭代器將拋出 ConcurrentModificationException。因此，在面對并發修改時，迭代器會快速而干凈地失敗，而不是冒著在未來不確定的時間出現任意的、非確定性行為的風險。請注意，無法保證迭代器的快速失效行為，因為一般來說，在存在不同步的并發修改的情況下，不可能做出任何硬性保證。快速失敗迭代器會盡力而為地拋出 ConcurrentModificationException。因此，編寫一個依賴于此異常的程序的正確性是錯誤的：迭代器的快速失敗行為應該只用于檢測錯誤。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {}’
此映射通常充當 bined（桶）哈希表，但是當 bin 變得太大時，它們會轉換為 TreeNodes 的 bin，每個 bin 的結構與 java.util.TreeMap 中的結構類似。大多數方法嘗試使用普通的 bin，但在適用時中繼到 TreeNode 方法（只需檢查節點的實例）。TreeNodes 的 bin 可以像任何其他 bin 一樣被遍歷和使用，但在過度填充時還支持更快的查找。但是，由于正常使用的絕大多數箱不會過度填充，因此在表方法的過程中可能會延遲檢查樹箱是否存在。樹 bin（即元素都是 TreeNodes 的 bin）主要由 hashCode 排序，但在平局的情況下，如果兩個元素屬于相同的“類 C 實現 Comparable
`/**
* The default initial capacity - MUST be a power of two.
* 默認容量大小為16，其必須為2的整數次冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16`
`/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*最大容量，如果使用參數的任一構造函數隱式指定了較高的值，則使用該容量。必須是 2 的冪<= 1<<30。
* 規定了HashMap的最大容量大小為2的29次方，如果手動輸入了其他值，則采用改值，但是該值必須為2的冪``
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* 負載因子，沒什么好說的，網絡上的文章已經寫的很明白了
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 樹化的閾值為8，當HashMap的容量大于64并且在一個bin上發生沖突，鏈的長度為8的時候，進行樹化
* 該值必須大于 2，并且應至少為 8
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
* 解除樹化的閾值為6，與8之間空著一個7，防止單個元素增減的時候頻繁進行樹化與解除
* 該值必須小于樹化閾值，并且最多為6
*
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 樹化前置容量條件，當HashMap中的容量小于這個值的時候，達到了樹化閾值，那么將會進行一次檢定，如果容量
* 大于這個值，則進行樹化，否則就進行擴容來減少Hash沖突
* 該值至少應該是4倍的樹化閾值
*/
static final int MIN_TREEIFY_CAPACITY = 64;`
接下來是一個內部類Node，是HashMap進行元素存儲的基本單位之一，這里就不過多贅述。
`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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
接下來是一些對外的方法:
/**
* 計算 key.hashCode（） 并將 （XOR） 較高的哈希位傳播到更低的位。由于該表使用 2 的冪掩碼，因此僅以高于當前掩碼的位數變化的哈希集將始終發生沖突。
* （在已知的例子中，有一組浮點鍵，它們在小表中保存連續的整數。因此，我們應用了一個轉換
* ，將較高位的影響向下分散。在速度、實用性和比特擴展質量之間需要權衡。由于許多常
* 見的哈希集已經合理分布（因此不會從擴展中受益），并且由于我們使用樹來處理 bin 中的大量沖突，因此我們只是以最便宜的方式對一些移位進行異或，
* 以減少系統損失，并合并最高位的影響，否則由于表邊界，這些位永遠不會用于索引計算。
* 這里計算hash是對key的hashCode進行高16位與低16位的異或，從而使得hash值同時具有高16位與低16位的特征，從而減少Hash沖突
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
* 返回x的Class對象，當且僅當 X 是 X implement Comparable<X>，否則返回nul
* 詳細可以查看這篇博客 https://blog.csdn.net/qpzkobe/article/details/79533237
*/
static Class<?> comparableClassFor(Object x) {
// 首先 x 必須是 Comparable的實現類
if (x instanceof Comparable) {
// 初始化 Class對象，type對象，參數化類型對象
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
//返回實現接口信息的type數組 包含泛型信息
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
//遍歷數組，篩選出其中的參數化類型
if (((t = ts[i]) instanceof ParameterizedType) &&
// 獲取其中去掉參數化類型的對象等于Comparable
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
// 以參數化類型返回其中的參數化列表，與getRawType剛好相反
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
* 如果 x 與 kc 匹配（k 篩選的可比類），則返回 k.compareTo（x），否則為 0。
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
/**
* Returns a power of two size for the given target capacity.
* 返回大于 入參cap最小的2的整數次冪
*
*/
static final int tableSizeFor(int cap) {
// 首先就是讓cap減去1，否則如果cap本身就是2的整數次冪將得到一個錯誤的值
int n = cap - 1;
//原理： int具有32bit，
// 假設現在最高位的1是這樣的：00100...將其與自身的無符號右移1位后的數字進行或運算，得到00110...
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// 將其進行無符號右邊移動1+2+4+8+16,會發生什么？ 會發現其總共右邊移動了31位，而且是無符號右移動
// 也就意味著在符號位不參與運算的情況下，該算法使得‘最高位的1右邊的0全變成了1’
// 最后返回值再進行+1，就完成了這一次最近size的運算
// 當然返回值是有最大容量校驗的
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
浙公網安備 33010602011771號