AHashMap的文檔中有這樣一句話：如果初始容量大于最大條目數(shù)除以負(fù)載因子，則不會發(fā)生重新哈希操作。請注意文檔如何說rehash，而不是調(diào)整大小- 即使 rehash 只會在調(diào)整大小時發(fā)生；那是當(dāng)桶的內(nèi)部大小變成兩倍大時。當(dāng)然也HashMap提供了這樣一個構(gòu)造函數(shù)，我們可以在其中定義這個初始容量。構(gòu)造一個具有指定初始容量和默認(rèn)負(fù)載因子 (0.75) 的空 HashMap。好的，看起來很簡單：// these are NOT chosen randomly... List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY", "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");int maxNumberOfEntries = list.size(); // 9double loadFactor = 0.75;int capacity = (int) (maxNumberOfEntries / loadFactor + 1); // 13所以容量是13（在內(nèi)部是16- 下一個 2 的冪），這樣我們就可以保證文檔部分沒有重新哈希。好的，讓我們測試一下，但首先介紹一個方法，該方法將進(jìn)入 aHashMap并查看值：private static <K, V> void debugResize(Map<K, V> map, K key, V value) throws Throwable { Field table = map.getClass().getDeclaredField("table"); table.setAccessible(true); Object[] nodes = ((Object[]) table.get(map)); // first put if (nodes == null) { // not incrementing currentResizeCalls because // of lazy init; or the first call to resize is NOT actually a "resize" map.put(key, value); return; } int previous = nodes.length; map.put(key, value); int current = ((Object[]) table.get(map)).length; if (previous != current) { ++HashMapResize.currentResizeCalls; System.out.println(nodes.length + " " + current); }}現(xiàn)在讓我們測試一下：static int currentResizeCalls = 0;public static void main(String[] args) throws Throwable { List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY", "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR"); int maxNumberOfEntries = list.size(); // 9 double loadFactor = 0.75; int capacity = (int) (maxNumberOfEntries / loadFactor + 1);好吧，resize被調(diào)用，因此條目被重新哈希，而不是文檔所說的。如上所述，密鑰不是隨機(jī)選擇的。這些設(shè)置是為了觸發(fā)static final int TREEIFY_THRESHOLD = 8;屬性 - 當(dāng)一個桶轉(zhuǎn)換為一棵樹時。不是真的，因為我們還需要擊中MIN_TREEIFY_CAPACITY = 64樹才能出現(xiàn)；直到resize發(fā)生這種情況，或者桶的大小增加了一倍；因此會發(fā)生條目的重新散列。我只能暗示為什么HashMap那句話中的文檔是錯誤的，因為在java-8之前，bucket 沒有轉(zhuǎn)換為 Tree；因此，該屬性將保持不變，從 java-8 開始就不再正確了。由于我不確定這一點，因此我不會將其添加為答案。
1 回答
蝴蝶不菲
TA貢獻(xiàn)1810條經(jīng)驗 獲得超4個贊
文檔中的那一行，
如果初始容量大于最大條目數(shù)除以負(fù)載因子，則不會發(fā)生重新哈希操作。
確實可以追溯到在 JDK 8 ( JEP 180 ) 中添加 tree-bin 實現(xiàn)之前。您可以在JDK 1.6 HashMap 文檔中看到此文本。事實上，本文可以追溯到 JDK 1.2 引入集合框架（包括 HashMap）時。您可以在網(wǎng)絡(luò)上找到 JDK 1.2 文檔的非官方版本，或者如果您想親自查看，也可以從檔案中下載一個版本。
我相信在添加 tree-bin 實現(xiàn)之前，此文檔是正確的。但是，正如您所觀察到的，現(xiàn)在有些情況是不正確的。如果條目數(shù)除以負(fù)載因子超過容量（實際上是表長度），則策略不僅可以調(diào)整大小。正如您所指出的，如果單個存儲桶中的條目數(shù)超過 TREEIFY_THRESHOLD（當(dāng)前為 8）但表長度小于 MIN_TREEIFY_CAPACITY（當(dāng)前為 64），也會發(fā)生大小調(diào)整。
你可以在treeifyBin()HashMap的方法中看到這個決定。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
當(dāng)單個存儲桶中的條目超過 TREEIFY_THRESHOLD 時，就會到達(dá)代碼中的這一點。如果表大小等于或大于 MIN_TREEIFY_CAPACITY，則此 bin 被樹化；否則，表格只是調(diào)整大小。
請注意，在小表大小下，這可能會使 bin 的條目比 TREEIFY_THRESHOLD 多。這并不是很難證明。首先，一些反射 HashMap 轉(zhuǎn)儲代碼：
// run with --add-opens java.base/java.util=ALL-UNNAMED
static Class<?> classNode;
static Class<?> classTreeNode;
static Field fieldNodeNext;
static Field fieldHashMapTable;
static void init() throws ReflectiveOperationException {
classNode = Class.forName("java.util.HashMap$Node");
classTreeNode = Class.forName("java.util.HashMap$TreeNode");
fieldNodeNext = classNode.getDeclaredField("next");
fieldNodeNext.setAccessible(true);
fieldHashMapTable = HashMap.class.getDeclaredField("table");
fieldHashMapTable.setAccessible(true);
}
static void dumpMap(HashMap<?, ?> map) throws ReflectiveOperationException {
Object[] table = (Object[])fieldHashMapTable.get(map);
System.out.printf("map size = %d, table length = %d%n", map.size(), table.length);
for (int i = 0; i < table.length; i++) {
Object node = table[i];
if (node == null)
continue;
System.out.printf("table[%d] = %s", i,
classTreeNode.isInstance(node) ? "TreeNode" : "BasicNode");
for (; node != null; node = fieldNodeNext.get(node))
System.out.print(" " + node);
System.out.println();
}
}
現(xiàn)在，讓我們添加一堆都屬于同一個桶的字符串。選擇這些字符串，使得它們的哈希值，由 HashMap 計算，都是 0 mod 64。
public static void main(String[] args) throws ReflectiveOperationException {
init();
List<String> list = List.of(
"LBCDD", "IKBNU", "WZQAG", "MKEAZ", "BBCHF", "KRQHE", "ZZMWH", "FHLVH",
"ZFLXM", "TXXPE", "NSJDQ", "BXDMJ", "OFBCR", "WVSIG", "HQDXY");
HashMap<String, String> map = new HashMap<>(1, 10.0f);
for (String s : list) {
System.out.println("===> put " + s);
map.put(s, s);
dumpMap(map);
}
}
從初始表大小 1 和荒謬的負(fù)載因子開始，這將 8 個條目放入單獨的存儲桶中。然后，每次添加另一個條目時，表都會調(diào)整大?。颖叮袟l目最終都在同一個存儲桶中。這最終會產(chǎn)生一個大小為 64 的表，其中一個桶具有長度為 14 的線性節(jié)點鏈（“基本節(jié)點”），然后添加下一個條目最終將其轉(zhuǎn)換為樹。
程序的輸出如下：
===> put LBCDD
map size = 1, table length = 1
table[0] = BasicNode LBCDD=LBCDD
===> put IKBNU
map size = 2, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU
===> put WZQAG
map size = 3, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG
===> put MKEAZ
map size = 4, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ
===> put BBCHF
map size = 5, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF
===> put KRQHE
map size = 6, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE
===> put ZZMWH
map size = 7, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH
===> put FHLVH
map size = 8, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH
===> put ZFLXM
map size = 9, table length = 2
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM
===> put TXXPE
map size = 10, table length = 4
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE
===> put NSJDQ
map size = 11, table length = 8
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ
===> put BXDMJ
map size = 12, table length = 16
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ
===> put OFBCR
map size = 13, table length = 32
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR
===> put WVSIG
map size = 14, table length = 64
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG
===> put HQDXY
map size = 15, table length = 64
table[0] = TreeNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG HQDXY=HQDXY
添加回答
舉報
0/150
提交
取消