您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)Java數(shù)據(jù)結(jié)構(gòu)之如何實(shí)現(xiàn)HashMap,小編覺得挺實(shí)用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。
Java數(shù)據(jù)結(jié)構(gòu)-HashMap
1. HashMap數(shù)據(jù)結(jié)構(gòu)
沒有哈希沖突時,為數(shù)組,支持動態(tài)擴(kuò)容
哈希沖突時,分為兩種情況:
1.當(dāng)沖突長度小于8或數(shù)組長度小于64(MIN_TREEIFY_CAPACITY默認(rèn)值為64)時,為數(shù)組+鏈表(Node)
2.當(dāng)沖突長度大于8時,為數(shù)組+紅黑樹/鏈表(TreeNode)。
紅黑樹用于快速查找,鏈表用于遍歷。
2. 紅黑樹
HashMap中的TreeNode是紅黑樹的實(shí)現(xiàn)。
TreeNode幾個方法
1. 左旋轉(zhuǎn)
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; }
實(shí)現(xiàn)效果如圖
2. 右旋轉(zhuǎn)
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; }
實(shí)現(xiàn)效果如圖
3. 插入
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { if ((xp = x.parent) == null) { x.red = false; return x; } else if (!xp.red || (xpp = xp.parent) == null) //① return root; if (xp == (xppl = xpp.left)) { if ((xppr = xpp.right) != null && xppr.red) { //② xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { //③ root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { //④ xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { if (xppl != null && xppl.red) { //② xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { //⑤ root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { //⑥ xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }
實(shí)現(xiàn)效果如下:
關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)之如何實(shí)現(xiàn)HashMap”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。