6月安卓手機(jī)好評(píng)榜：魅族20 Pro蟬聯(lián)冠軍
性能榜和性價(jià)比榜之后，我們來(lái)看最后的安卓手機(jī)好評(píng)榜，數(shù)據(jù)來(lái)源安兔兔評(píng)測(cè)，收集時(shí)間2023年6月1日至6月30日，僅限國(guó)內(nèi)市場(chǎng)。第一名：魅族20 Pro好評(píng)率：95%5月份的時(shí)候魅族20 Pro就是
HashMap是Java中非常重要且被廣泛使用的數(shù)據(jù)結(jié)構(gòu)，其內(nèi)部實(shí)現(xiàn)充滿了有趣而復(fù)雜的算法。我們研究下HashMap內(nèi)部的一些核心算法，包括哈希沖突的解決、擴(kuò)容策略、樹(shù)化與樹(shù)退化等。
即tableSizeFor方法。其主要目的是確保HashMap的容量始終是2的冪次方，這一特性對(duì)HashMap的哈希算法和擴(kuò)容策略都至關(guān)重要。
// 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;}總的來(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ì)算效率。
在HashMap中，哈希沖突是指不同的鍵可能映射到相同的索引位置的情況。為了解決沖突，HashMap采用了拉鏈法，即將具有相同哈希碼的鍵值對(duì)存儲(chǔ)在同一個(gè)數(shù)組位置，以鏈表的形式。
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ù)，以提高查找效率。
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); // ... } // ...}
當(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ì)算所有元素的索引位置。
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ò)容。
為了減小哈希沖突的概率，HashMap采用了擾動(dòng)函數(shù)，將鍵的哈希碼進(jìn)行“擾動(dòng)”。
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ī)性。
為了提高查找效率，當(dāng)鏈表長(zhǎng)度超過(guò)一定閾值（默認(rèn)為8）時(shí)，HashMap會(huì)將鏈表轉(zhuǎn)化成紅黑樹(shù)。而在刪除或鏈表長(zhǎng)度過(guò)短時(shí)，紅黑樹(shù)又可能退化成鏈表。
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ù)退化為鏈表。
負(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ò)程稱為重新哈希。
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ò)容。
通過(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)部的奧秘有了更深層次的理解。
本文鏈接：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
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)