日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當(dāng)前位置:首頁(yè) > 科技  > 軟件

探秘HashMap:有趣的算法之旅

來(lái)源: 責(zé)編: 時(shí)間:2024-03-18 17:43:34 182觀看
導(dǎo)讀HashMap是Java中非常重要且被廣泛使用的數(shù)據(jù)結(jié)構(gòu),其內(nèi)部實(shí)現(xiàn)充滿了有趣而復(fù)雜的算法。我們研究下HashMap內(nèi)部的一些核心算法,包括哈希沖突的解決、擴(kuò)容策略、樹(shù)化與樹(shù)退化等。1. 容量計(jì)算方法即tableSizeFor方法。其主

bzI28資訊網(wǎng)——每日最新資訊28at.com

HashMap是Java中非常重要且被廣泛使用的數(shù)據(jù)結(jié)構(gòu),其內(nèi)部實(shí)現(xiàn)充滿了有趣而復(fù)雜的算法。我們研究下HashMap內(nèi)部的一些核心算法,包括哈希沖突的解決、擴(kuò)容策略、樹(shù)化與樹(shù)退化等。bzI28資訊網(wǎng)——每日最新資訊28at.com

1. 容量計(jì)算方法

tableSizeFor方法。其主要目的是確保HashMap的容量始終是2的冪次方,這一特性對(duì)HashMap的哈希算法和擴(kuò)容策略都至關(guān)重要。bzI28資訊網(wǎng)——每日最新資訊28at.com

// cap為用戶傳入的map初始化大小,將返回一個(gè)大于該數(shù)的,距離最近的2的冪次方static final int tableSizeFor(int cap) {    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}
  • Integer.numberOfLeadingZeros(cap - 1): 這個(gè)方法返回參數(shù)cap - 1的二進(jìn)制表示中,從最高位開(kāi)始連續(xù)的零的個(gè)數(shù)。這個(gè)值實(shí)際上表示了cap的二進(jìn)制表示中,最高位的位置(不包括符號(hào)位)。
  • -1 >>> Integer.numberOfLeadingZeros(cap - 1): 這一步通過(guò)將-1右移numberOfLeadingZeros位,實(shí)際上將最高位至numberOfLeadingZeros位之間的所有位都置為1,其余位為0。這樣做的目的是為了確保在后續(xù)的計(jì)算中,得到的值是一個(gè)2的冪次方減1的形式。
  • (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1: 這一步對(duì)上述得到的值進(jìn)行判斷和修正。如果計(jì)算結(jié)果小于0,說(shuō)明cap為0,因此將容量設(shè)為1;如果計(jì)算結(jié)果超過(guò)了MAXIMUM_CAPACITY,即HashMap的最大容量限制,將容量設(shè)為MAXIMUM_CAPACITY;否則,將容量設(shè)為n + 1。這里的n + 1保證了返回的容量是2的冪次方。

總的來(lái)說(shuō),tableSizeFor方法確保了HashMap的容量始終是2的冪次方。這種容量設(shè)置的方式有助于提高哈希算法的性能,同時(shí)與HashMap的擴(kuò)容策略密切相關(guān)。這樣的設(shè)計(jì)使得HashMap在進(jìn)行哈希計(jì)算時(shí),可以通過(guò)位運(yùn)算,取代一些昂貴的除法運(yùn)算,從而提高計(jì)算效率。bzI28資訊網(wǎng)——每日最新資訊28at.com

bzI28資訊網(wǎng)——每日最新資訊28at.com

2. 哈希沖突:鏈表和紅黑樹(shù)

在HashMap中,哈希沖突是指不同的鍵可能映射到相同的索引位置的情況。為了解決沖突,HashMap采用了拉鏈法,即將具有相同哈希碼的鍵值對(duì)存儲(chǔ)在同一個(gè)數(shù)組位置,以鏈表的形式。bzI28資訊網(wǎng)——每日最新資訊28at.com

class Node<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;    }}

上述Node類表示HashMap中的一個(gè)節(jié)點(diǎn),包含了鍵、值、哈希碼以及指向下一個(gè)節(jié)點(diǎn)的引用。當(dāng)沖突的鏈表長(zhǎng)度超過(guò)一定閾值(默認(rèn)為8)時(shí),HashMap會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù),以提高查找效率。bzI28資訊網(wǎng)——每日最新資訊28at.com

static final int TREEIFY_THRESHOLD = 8;// 當(dāng)鏈表長(zhǎng)度達(dá)到8時(shí),將鏈表轉(zhuǎn)換為紅黑樹(shù)void treeifyBin(Node<K, V>[] tab, int hash) {    // ...    if (n >= TREEIFY_THRESHOLD) {        // 執(zhí)行轉(zhuǎn)換為紅黑樹(shù)的操作        treeifyBin(tab, hash);        // ...    }    // ...}

bzI28資訊網(wǎng)——每日最新資訊28at.com

3. 擴(kuò)容:2 的冪次方擴(kuò)容

當(dāng)HashMap的元素?cái)?shù)量達(dá)到一定負(fù)載因子時(shí)(默認(rèn)為0.75),為了避免鏈表過(guò)長(zhǎng),會(huì)觸發(fā)擴(kuò)容操作。在擴(kuò)容時(shí),HashMap將數(shù)組容量擴(kuò)大至原來(lái)的兩倍,并重新計(jì)算所有元素的索引位置。bzI28資訊網(wǎng)——每日最新資訊28at.com

void resize() {    int oldCap = table.length;    int newCap = oldCap << 1;    // 創(chuàng)建新的數(shù)組,大小為原來(lái)的兩倍    Node<K, V>[] newTab = new Node[newCap];    // 重新計(jì)算元素在新數(shù)組中的位置    // ...    table = newTab;}

oldCap表示原數(shù)組的容量,newCap表示新數(shù)組的容量,通過(guò)位運(yùn)算將原容量左移一位實(shí)現(xiàn)擴(kuò)容。bzI28資訊網(wǎng)——每日最新資訊28at.com

4. 哈希碼計(jì)算:擾動(dòng)函數(shù)

為了減小哈希沖突的概率,HashMap采用了擾動(dòng)函數(shù),將鍵的哈希碼進(jìn)行“擾動(dòng)”。bzI28資訊網(wǎng)——每日最新資訊28at.com

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

這里的hash方法通過(guò)異或運(yùn)算和無(wú)符號(hào)右移等位運(yùn)算,將鍵的哈希碼進(jìn)行擾動(dòng),增加哈希碼的隨機(jī)性。bzI28資訊網(wǎng)——每日最新資訊28at.com

bzI28資訊網(wǎng)——每日最新資訊28at.com

5. 樹(shù)化與樹(shù)退化

為了提高查找效率,當(dāng)鏈表長(zhǎng)度超過(guò)一定閾值(默認(rèn)為8)時(shí),HashMap會(huì)將鏈表轉(zhuǎn)化成紅黑樹(shù)。而在刪除或鏈表長(zhǎng)度過(guò)短時(shí),紅黑樹(shù)又可能退化成鏈表。bzI28資訊網(wǎng)——每日最新資訊28at.com

static final int UNTREEIFY_THRESHOLD = 6;// 將紅黑樹(shù)退化為鏈表void untreeify(Node<K, V>[] tab) {    // ...    if ((n <= UNTREEIFY_THRESHOLD) && (first instanceof TreeNode))        // 執(zhí)行退化為鏈表的操作        untreeify(tab);    // ...}

UNTREEIFY_THRESHOLD是一個(gè)閾值,表示當(dāng)紅黑樹(shù)的節(jié)點(diǎn)數(shù)小于等于6時(shí),將紅黑樹(shù)退化為鏈表。bzI28資訊網(wǎng)——每日最新資訊28at.com

6. 負(fù)載因子和重新哈希

負(fù)載因子是HashMap決定是否需要進(jìn)行擴(kuò)容的一個(gè)關(guān)鍵參數(shù)。當(dāng)HashMap中的元素?cái)?shù)量達(dá)到容量與負(fù)載因子的乘積時(shí),就會(huì)觸發(fā)擴(kuò)容。在擴(kuò)容時(shí),HashMap會(huì)重新計(jì)算所有元素的索引位置,這個(gè)過(guò)程稱為重新哈希。bzI28資訊網(wǎng)——每日最新資訊28at.com

static final float DEFAULT_LOAD_FACTOR = 0.75f;void addEntry(int hash, K key, V value, int bucketIndex) {    // ...    if ((size >= threshold) && (null != table[bucketIndex])) {        // 執(zhí)行重新哈希的操作        resize();        // ...    }    // ...}

DEFAULT_LOAD_FACTOR是一個(gè)默認(rèn)的負(fù)載因子,表示當(dāng)元素?cái)?shù)量達(dá)到容量的75%時(shí),觸發(fā)擴(kuò)容。bzI28資訊網(wǎng)——每日最新資訊28at.com

通過(guò)這些代碼示例,我們可以稍微了解到HashMap內(nèi)部的一些核心算法。這些算法保證了HashMap在面對(duì)不同場(chǎng)景時(shí)能夠保持高效的性能,同時(shí)保證了數(shù)據(jù)結(jié)構(gòu)的穩(wěn)定性。深入了解這些算法不僅有助于我們理解HashMap的內(nèi)部工作原理,還能夠在需要的情況下更好地優(yōu)化我們的代碼。希望通過(guò)這次的有趣之旅,大家對(duì)HashMap內(nèi)部的奧秘有了更深層次的理解。bzI28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接:http://www.www897cc.com/showinfo-26-77526-0.html探秘HashMap:有趣的算法之旅

聲明:本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí),若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系,我們將在第一時(shí)間刪除處理。郵件:2376512515@qq.com

上一篇: 如何在Selenium中查找第一個(gè)元素和所有元素

下一篇: 故障現(xiàn)場(chǎng) | 消息發(fā)送居然有這么大的坑

標(biāo)簽:
  • 熱門(mén)焦點(diǎn)
Top 主站蜘蛛池模板: 沁阳市| 花莲县| 兴业县| 邻水| 闽侯县| 五莲县| 潜江市| 绩溪县| 留坝县| 色达县| 古丈县| 龙井市| 廊坊市| 西贡区| 台山市| 油尖旺区| 泰来县| 德格县| 灵寿县| 周宁县| 剑川县| 新疆| 土默特左旗| 崇明县| 厦门市| 阿拉善盟| 辰溪县| 射洪县| 扶绥县| 婺源县| 寻乌县| 容城县| 格尔木市| 峨边| 龙州县| 玛沁县| 黔西县| 全椒县| 屏东市| 鹤岗市| 定安县|