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

當前位置:首頁 > 科技  > 軟件

探秘HashMap:有趣的算法之旅

來源: 責編: 時間:2024-03-18 17:43:34 181觀看
導讀HashMap是Java中非常重要且被廣泛使用的數據結構,其內部實現充滿了有趣而復雜的算法。我們研究下HashMap內部的一些核心算法,包括哈希沖突的解決、擴容策略、樹化與樹退化等。1. 容量計算方法即tableSizeFor方法。其主

9Y128資訊網——每日最新資訊28at.com

HashMap是Java中非常重要且被廣泛使用的數據結構,其內部實現充滿了有趣而復雜的算法。我們研究下HashMap內部的一些核心算法,包括哈希沖突的解決、擴容策略、樹化與樹退化等。9Y128資訊網——每日最新資訊28at.com

1. 容量計算方法

tableSizeFor方法。其主要目的是確保HashMap的容量始終是2的冪次方,這一特性對HashMap的哈希算法和擴容策略都至關重要。9Y128資訊網——每日最新資訊28at.com

// cap為用戶傳入的map初始化大小,將返回一個大于該數的,距離最近的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): 這個方法返回參數cap - 1的二進制表示中,從最高位開始連續的零的個數。這個值實際上表示了cap的二進制表示中,最高位的位置(不包括符號位)。
  • -1 >>> Integer.numberOfLeadingZeros(cap - 1): 這一步通過將-1右移numberOfLeadingZeros位,實際上將最高位至numberOfLeadingZeros位之間的所有位都置為1,其余位為0。這樣做的目的是為了確保在后續的計算中,得到的值是一個2的冪次方減1的形式。
  • (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1: 這一步對上述得到的值進行判斷和修正。如果計算結果小于0,說明cap為0,因此將容量設為1;如果計算結果超過了MAXIMUM_CAPACITY,即HashMap的最大容量限制,將容量設為MAXIMUM_CAPACITY;否則,將容量設為n + 1。這里的n + 1保證了返回的容量是2的冪次方。

總的來說,tableSizeFor方法確保了HashMap的容量始終是2的冪次方。這種容量設置的方式有助于提高哈希算法的性能,同時與HashMap的擴容策略密切相關。這樣的設計使得HashMap在進行哈希計算時,可以通過位運算,取代一些昂貴的除法運算,從而提高計算效率。9Y128資訊網——每日最新資訊28at.com

9Y128資訊網——每日最新資訊28at.com

2. 哈希沖突:鏈表和紅黑樹

在HashMap中,哈希沖突是指不同的鍵可能映射到相同的索引位置的情況。為了解決沖突,HashMap采用了拉鏈法,即將具有相同哈希碼的鍵值對存儲在同一個數組位置,以鏈表的形式。9Y128資訊網——每日最新資訊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中的一個節點,包含了鍵、值、哈希碼以及指向下一個節點的引用。當沖突的鏈表長度超過一定閾值(默認為8)時,HashMap會將鏈表轉換為紅黑樹,以提高查找效率。9Y128資訊網——每日最新資訊28at.com

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

9Y128資訊網——每日最新資訊28at.com

3. 擴容:2 的冪次方擴容

當HashMap的元素數量達到一定負載因子時(默認為0.75),為了避免鏈表過長,會觸發擴容操作。在擴容時,HashMap將數組容量擴大至原來的兩倍,并重新計算所有元素的索引位置。9Y128資訊網——每日最新資訊28at.com

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

oldCap表示原數組的容量,newCap表示新數組的容量,通過位運算將原容量左移一位實現擴容。9Y128資訊網——每日最新資訊28at.com

4. 哈希碼計算:擾動函數

為了減小哈希沖突的概率,HashMap采用了擾動函數,將鍵的哈希碼進行“擾動”。9Y128資訊網——每日最新資訊28at.com

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

這里的hash方法通過異或運算和無符號右移等位運算,將鍵的哈希碼進行擾動,增加哈希碼的隨機性。9Y128資訊網——每日最新資訊28at.com

9Y128資訊網——每日最新資訊28at.com

5. 樹化與樹退化

為了提高查找效率,當鏈表長度超過一定閾值(默認為8)時,HashMap會將鏈表轉化成紅黑樹。而在刪除或鏈表長度過短時,紅黑樹又可能退化成鏈表。9Y128資訊網——每日最新資訊28at.com

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

UNTREEIFY_THRESHOLD是一個閾值,表示當紅黑樹的節點數小于等于6時,將紅黑樹退化為鏈表。9Y128資訊網——每日最新資訊28at.com

6. 負載因子和重新哈希

負載因子是HashMap決定是否需要進行擴容的一個關鍵參數。當HashMap中的元素數量達到容量與負載因子的乘積時,就會觸發擴容。在擴容時,HashMap會重新計算所有元素的索引位置,這個過程稱為重新哈希。9Y128資訊網——每日最新資訊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])) {        // 執行重新哈希的操作        resize();        // ...    }    // ...}

DEFAULT_LOAD_FACTOR是一個默認的負載因子,表示當元素數量達到容量的75%時,觸發擴容。9Y128資訊網——每日最新資訊28at.com

通過這些代碼示例,我們可以稍微了解到HashMap內部的一些核心算法。這些算法保證了HashMap在面對不同場景時能夠保持高效的性能,同時保證了數據結構的穩定性。深入了解這些算法不僅有助于我們理解HashMap的內部工作原理,還能夠在需要的情況下更好地優化我們的代碼。希望通過這次的有趣之旅,大家對HashMap內部的奧秘有了更深層次的理解。9Y128資訊網——每日最新資訊28at.com

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

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

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

下一篇: 故障現場 | 消息發送居然有這么大的坑

標簽:
  • 熱門焦點
Top 主站蜘蛛池模板: 阜阳市| 漠河县| 永泰县| 宿迁市| 土默特左旗| 高雄市| 绩溪县| 阿坝| 独山县| 英吉沙县| 大埔区| 尚志市| 托克逊县| 防城港市| 兴安盟| 开化县| 荔波县| 湟中县| 漯河市| 宜宾市| 永兴县| 石景山区| 宜州市| 礼泉县| 渝北区| 大英县| 永兴县| 尼玛县| 恩施市| 黑水县| 库尔勒市| 江孜县| 定安县| 南京市| 隆尧县| 习水县| 万安县| 奇台县| 岳池县| 若羌县| 睢宁县|