根據(jù)下面的代碼，hashmap 初始默認(rèn)容量為 16，LF 為 0.75，所以當(dāng)我輸入第 13 個(gè)元素時(shí)，應(yīng)該進(jìn)行重新散列，因?yàn)槲姨峁┝艘粋€(gè)恒定的散列碼，它在內(nèi)部維護(hù)一個(gè)鏈表來(lái)維護(hù)插入順序。所以，直到第 10 個(gè)元素它按預(yù)期工作，但是當(dāng)我輸入第 11 個(gè)元素時(shí)，它會(huì)打亂順序。任何人都可以幫助我理解為什么它只在第 11 個(gè)元素插入時(shí)發(fā)生。class A{ int a; A(int a){ this.a = a; } @Override public int hashCode() { return 7; } @Override public String toString() { return "" + a + ""; }}class Base { public static void main(String[] args) { Map<Object, Integer> m = new HashMap<Object, Integer>(); m.put(new A(1), 1); m.put(new A(2), 1); m.put(new A(3), 1); m.put(new A(4), 1); m.put(new A(5), 1); m.put(new A(6), 1); m.put(new A(7), 1); m.put(new A(8), 1); m.put(new A(9), 1); m.put(new A(10), 1); //m.put(new A(11), 1); System.out.println(m); }}我得到的輸出直到第 10 個(gè)元素：{1=1, 2=1, 3=1, 4=1, 5=1, 6=1, 7=1, 8=1, 9=1, 10=1}輸入第 11 個(gè)元素后得到的輸出：{4=1, 1=1, 2=1, 3=1, 5=1, 6=1, 7=1, 8=1, 9=1, 10=1, 11=1}它應(yīng)該保持插入順序，或者如果它在內(nèi)部使用 RB 樹(shù)，那么在這種情況下它在這里使用哪種遍歷？
2 回答
萬(wàn)千封印
TA貢獻(xiàn)1891條經(jīng)驗(yàn) 獲得超3個(gè)贊
它應(yīng)該保持插入順序，或者如果它在內(nèi)部使用 RB 樹(shù)，那么在這種情況下它在這里使用哪種遍歷？
沒(méi)有“應(yīng)該”；不HashMap保證任何訂單。當(dāng)前實(shí)現(xiàn)中實(shí)際發(fā)生的情況由兩個(gè)常數(shù)TREEIFY_THRESHOLD = 8和決定MIN_TREEIFY_CAPACITY = 64。
當(dāng)一個(gè)桶中的項(xiàng)目數(shù)超過(guò)前者時(shí)，桶將轉(zhuǎn)化為一棵節(jié)點(diǎn)樹(shù)，除非map的總?cè)萘啃∮诤笳叩某?shù)，在這種情況下，容量會(huì)翻倍。
因此，當(dāng)您插入第 9 個(gè)對(duì)象時(shí)，容量將從 16 提高到 32，插入第 10 個(gè)會(huì)導(dǎo)致從 32 提高到 64，然后，插入第 11 個(gè)元素將導(dǎo)致桶轉(zhuǎn)換為樹(shù)。
這種轉(zhuǎn)換總是會(huì)發(fā)生，無(wú)論是否有實(shí)際的好處。由于對(duì)象具有相同的哈希碼并且沒(méi)有實(shí)現(xiàn)Comparable，因此最終將使用它們的身份哈希碼來(lái)確定順序。這可能會(huì)導(dǎo)致順序發(fā)生變化（在我的環(huán)境中，它不會(huì)）。
胡說(shuō)叔叔
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超8個(gè)贊
它獨(dú)立于指定的哈希碼編號(hào)，即 7，而是您的哈希碼是恒定的導(dǎo)致它。以下是原因：
我瀏覽了 HashMap 的 put 方法的源代碼，其中有一個(gè)常量TREEIFY_THRESHOLD決定何時(shí)將普通桶轉(zhuǎn)換為樹(shù)。
靜態(tài)最終 int TREEIFY_THRESHOLD = 8;
put 方法的代碼片段如下（Put 方法調(diào)用 putVal 方法）：
.
.
.
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 (binCount >= TREEIFY_THRESHOLD - 1)條件的行。一旦它發(fā)現(xiàn)一個(gè)桶被填滿TREEIFY_THRESHOLD，它就會(huì)調(diào)用treeifyBin()方法。
該方法反過(guò)來(lái)resize()僅在MIN_TREEIFY_CAPACITY滿足時(shí)調(diào)用該方法。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
在上面的代碼段中查找以下條件
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
然后 resize 方法根據(jù)它具有的多個(gè)條件檢查相應(yīng)地增加地圖的大小。它基本上通過(guò)負(fù)載系數(shù)增加容量。
如果沒(méi)有，就像樹(shù)化一樣。樹(shù)中的元素?cái)?shù)量減少。UNTREEIFY_THRESHOLD使用ie 6 作為基礎(chǔ)執(zhí)行 Untreeify 操作。
我引用了這個(gè)鏈接來(lái)瀏覽 Hashmap 代碼。
添加回答
舉報(bào)
0/150
提交
取消