Java集合源碼分析之HashMap

前言

HashMap可以說是我們日常開發(fā)中特別經常使用到的對象映射關系集合類了摩桶,本文將結合JDK1.8源碼從線程安全烁试、數(shù)據(jù)結構犀暑、初始化驯击、擴容、增刪改查母怜、特性總結等幾個部分去分析HashMap

線程安全

HashMap是非線程安全的余耽,不支持并發(fā)缚柏。我們可以從它的數(shù)據(jù)迭代器中可以得知苹熏,當產生線程安全問題時會拋出拋出ConcurrentModificationException異常。內部是通過一個modCount變量記錄集合的變化币喧,在擴容與刪除及清空等操作都會將modCount自增轨域,以此來標記集合的改變。

如何實現(xiàn)線程安全

1.通過Colletions.synchronizedMap獲取線程安全的Map對象
2.使用并發(fā)庫下的ConcurrentMap

數(shù)據(jù)結構

哈希表(數(shù)據(jù)+單鏈表)杀餐,結合了兩者的優(yōu)勢干发,采用拉鏈法解決哈希沖突。哈希沖突的常用解決方法包括拉鏈法和開發(fā)地址法史翘,由于使用了鏈表鏈接沖突元素枉长,那么證明它自然采用的是拉鏈法


image.png

初始化

提供了四個重載構造方法,除了默認的無參構造器外還可以指定初始容量以及初始集合內容以及同時指定容量與加載因子琼讽。無參構造器僅僅指定擴容因子為默認值0.75必峰;指定集合時澤通過entrySet遍歷將每個item指定putVal進行添加;容量指的是數(shù)組長度length的大小

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    public HashMap(int initialCapacity) { ... }
    public HashMap(int initialCapacity, float loadFactor) { ... }
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            // 表為null 進行初始化
            if (table == null) { // pre-size
                // 計算新的擴容閥值
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY); // 擴容閥值越界判斷
                if (t > threshold) // 閥值初始化钻蹬,首次的時候閥值=容量
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    // 初始化容量吼蚁,移位操作比符號運算效率更高
    // 此處tableSizeFor最后返回的有效位都是1,最后n+1恒為2的n次冪问欠。先注意下肝匆,后面會提到。也就是說最后容量result總是>=cap
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

擴容

HashMap的擴容主要步驟如下:更新閥值 -> 構建新的哈希桶 -> 將元素移動到新哈希桶中顺献,正常情況下每次擴容后為原容量2旗国,使得容量總是為2的n次冪。實際的擴容操作注整,首先是根據(jù)三種情況進行能曾。第一種情況是此次擴容屬于首次擴容嫁怀,如果舊閥值大于0(使用了兩個有參構造器),則新容量即為舊閥值借浊。第二種情況是此次擴容屬于首次擴容塘淑,該HashMap使用無參構造器進行初始化,那么新容量為默認值16蚂斤,閥值為160.75存捺。第三種情況,此處擴容非首次擴容曙蒸,那么新容量為舊容量2捌治,新閥值為舊閥值2

    // 擴容函數(shù)
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; // 舊哈希表
        int oldCap = (oldTab == null) ? 0 : oldTab.length; // 舊容量
        int oldThr = threshold; // 舊閥值
        int newCap, newThr = 0; // 新容量與新閥值
        if (oldCap > 0) { // 舊容量大于0,屬于非首次擴容情況
            if (oldCap >= MAXIMUM_CAPACITY) { // 越界保護
                threshold = Integer.MAX_VALUE;
                return oldTab; // 無法繼續(xù)擴容
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold 新閥值為舊閥值*2
        }
        // 首次擴容纽窟,且初始化時指定了閥值
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 由于初始化的閥值通過tableSizeFor獲得肖油,因此最后的結果也是2的n次冪
            newCap = oldThr; // 新容量直接等于初始化的閥值
        // 首次擴容,切初始化時使用的默認無參構造器
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY; // 新容量為默認容量16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新閥值為默認容量*默認加載因子臂港,即16*0.75
        }
        // 指定新閥值為新容量*加載因子
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 以下開始進行數(shù)據(jù)遷移
        if (oldTab != null) {
            // 遍歷節(jié)點森枪,注意哈希表結構。如果存在哈希碰撞的情況审孽,某個節(jié)點可能還有鏈表節(jié)點县袱。
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { // 臨時存儲目標節(jié)點
                    oldTab[j] = null; // 舊表對應位置元素置空,方便gc
                    // next為null表示該節(jié)點沒有hash碰撞找到下標賦值佑力,采用hash & (newCap - 1)式散,使用&與操作來代替%取模操作,提高效率打颤。為了使&能夠達到更加均勻的分布暴拄,減少hash碰撞,因此newCap的取值總是2的n次方
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e; // 放到新表
                    // 如果發(fā)生過哈希碰撞 ,而且是節(jié)點數(shù)超過8個编饺,轉化成了紅黑樹
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 如果發(fā)生過哈希碰撞乖篷,節(jié)點數(shù)未超過8個
                    // 存在碰撞的話,那么對于的鏈表上的節(jié)點有兩種可能
                    // 第一種反肋,hash與新容量取模后小于舊容量那伐,即值與hash與舊容量取模一樣(低位)
                    // 第二種,hash與新容量取模后大于舊容量石蔗,即值為hash與舊容量取模 + 舊容量(高位)
                    else { // preserve order
                        // 低位鏈表頭尾節(jié)點
                        Node<K,V> loHead = null, loTail = null;
                        // 高位鏈表頭尾節(jié)點
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next; // 操作節(jié)點
                        do {
                            next = e.next; // 操作節(jié)點賦值
                            // 通過hash與舊容量的與操作是否為0(高效)(注意是oldCap而不是olcCap-1)
                            // 判斷與新容量取模后的值是否大于舊容量
                            if ((e.hash & oldCap) == 0) {
                                // 結果==0表示處于低位
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { // 結果!=0表示處于高位
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null); // while循環(huán)罕邀,處理鏈表上所有節(jié)點
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead; // 放到新表中
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; // 放到新表中
                        }
                    }
                }
            }
        }
        return newTab;
    }

Hash處理

獲取key的Hash值時不是直接返回其hashCode方法的值,而是通過“擾動函數(shù)”進行處理后返回养距。hashCode()是int類型诉探,取值范圍是40多億,只要哈希函數(shù)映射的比較均勻松散棍厌,碰撞幾率是很小的肾胯。但是由于HashMap的哈希桶長度要遠遠小于hashCode()竖席,因為一般采用取余的方式獲取key對應的桶下標,在HashMap中采用與操作來實現(xiàn)取余敬肚,如果直接使用hashCode()會忽略高位毕荐,導致碰撞幾率增大。擾動函數(shù)就是為了解決hash碰撞的艳馒。它會綜合hash值高位和低位的特征憎亚,并存放在低位,因此在與運算時弄慰,相當于高低位一起參與了運算第美,以減少hash碰撞的概率

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

增改操作

若數(shù)組為空則進行擴容,獲取index下標陆爽,若對應位置上沒有元素則直接賦值什往,若有元素先判斷是否key一致(hash與equals均一致),一致則進行覆蓋慌闭。不一致則表示發(fā)生碰撞别威,而HashMap采用拉鏈法解決碰撞,在對應鏈表上需要是否有key一致的元素贡必,有則覆蓋兔港,沒有則在末尾插入節(jié)點庸毫。(會修改modCount變量)最后仔拟,按需擴容。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// JDK 1.8 新增方法飒赃,若對應key的value之前存在利花,則不覆蓋
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}
public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, I;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
// index位置沒有元素,直接賦值
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
// index上元素key與目標key一致
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
// 紅黑樹(當鏈表節(jié)點數(shù)大于8载佳,轉為紅黑樹)
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 鏈表節(jié)點數(shù)小于8
            for (int binCount = 0; ; ++binCount) {
        // 到末尾節(jié)點炒事,仍沒有找到key一致的節(jié)點
        // 將此元素插入到該鏈表末尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
// 當鏈表節(jié)點數(shù)大于8,轉為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
        // 鏈表中存在key一致的節(jié)點
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
    // 上述過程找到了key一致的元素蔫慧,修改value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
        // 是否覆蓋value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);// 回調
    return null;
}

// 為LinkedHashMap提供的回調函數(shù)
void afterNodeAccess(Node<K,V> p) { } // 訪問(查)
void afterNodeInsertion(boolean evict) { } // 插入(增)
void afterNodeRemoval(Node<K,V> p) { } // 移除(刪)

刪操作

根據(jù)key為條件或者以key-value為條件挠乳。首先找到key一致元素(鏈表頭,或者鏈表中)姑躲,然后從數(shù)組或鏈表中剔除睡扬。修改modCount與size

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
    // 通過index找到key相同的元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
    // 發(fā)生碰撞,在對應鏈表中尋找
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e; // P為被刪除前一個(當目標即為第一個時p==node)
                } while ((e = e.next) != null);
            }
        }
    // 移除元素黍析,修改指針
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p) // 鏈表首個元素卖怜,數(shù)組位置指向其next
                tab[index] = node.next;
            else
                p.next = node.next; // p.next跨過目標元素
            ++modCount;
            --size;
            afterNodeRemoval(node); // 刪除回調
            return node;
        }
    }
    return null;
}

查:通過hash去查找元素value

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
    // 表頭
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
    // 表中
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
        // key一致(hash相等,equals成立)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null; // 沒找到
}
// 雙層for:數(shù)字 + 鏈表
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

無序性

從HashIterator類中我們可以看出元素的遍歷是從哈希桶從低到高阐枣,鏈表從前到后

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot
......
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

特性總結

HashMap采用數(shù)組+單鏈表結構马靠,key與value均可為null
(在JDK1.7中專門有個HashMapEntry對象用于存儲key為null的元素奄抽,而JDK1.8中則是針對key==null的情況返回hash為0來進行實現(xiàn))
HashMap中的高效運算:(1)通過&來進行取模,hash&(cap - 1)(2)在舊元素拷貝到新的哈希桶中甩鳄,通過&進行高低位判斷逞度,hash&oldCap
HashMap中的碰撞優(yōu)化:(1)哈希桶的容量總是為2的n次方,為了讓hash結果分布均勻妙啃,減少hash碰撞(2)擾動函數(shù):避免取模時只關注hashCode低位第晰,減少hash碰撞,讓高低位同時參數(shù)hash計算彬祖。hash = (h = key.hashCode()) ^ h >>> 16


image.gif

HashMap與HashTable的區(qū)別

HashTable是線程安全的茁瘦,且不允許key、value是null
HashTable默認容量是11
HashTable是直接使用key的hashCode()作為hash值
HashTable取哈希桶下標是直接用模運算%.(因為其默認容量也不是2的n次方储笑,所以也無法用位運算替代模運算)
擴容時甜熔,新容量是原來的2倍+1。int newCapacity = (oldCapacity << 1) + 1

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末突倍,一起剝皮案震驚了整個濱河市腔稀,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌羽历,老刑警劉巖焊虏,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異秕磷,居然都是意外死亡诵闭,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進店門澎嚣,熙熙樓的掌柜王于貴愁眉苦臉地迎上來疏尿,“玉大人,你說我怎么就攤上這事易桃∪焖觯” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵晤郑,是天一觀的道長敌呈。 經常有香客問我,道長造寝,這世上最難降的妖魔是什么磕洪? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮匹舞,結果婚禮上褐鸥,老公的妹妹穿的比我還像新娘。我一直安慰自己赐稽,他們只是感情好叫榕,可當我...
    茶點故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布浑侥。 她就那樣靜靜地躺著,像睡著了一般晰绎。 火紅的嫁衣襯著肌膚如雪寓落。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天荞下,我揣著相機與錄音伶选,去河邊找鬼。 笑死尖昏,一個胖子當著我的面吹牛仰税,可吹牛的內容都是我干的。 我是一名探鬼主播抽诉,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼陨簇,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了迹淌?” 一聲冷哼從身側響起河绽,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎唉窃,沒想到半個月后耙饰,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡纹份,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年苟跪,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片矮嫉。...
    茶點故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡削咆,死狀恐怖,靈堂內的尸體忽然破棺而出蠢笋,到底是詐尸還是另有隱情,我是刑警寧澤鳞陨,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布昨寞,位于F島的核電站,受9級特大地震影響厦滤,放射性物質發(fā)生泄漏援岩。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一掏导、第九天 我趴在偏房一處隱蔽的房頂上張望享怀。 院中可真熱鬧,春花似錦趟咆、人聲如沸添瓷。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽鳞贷。三九已至坯汤,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間搀愧,已是汗流浹背惰聂。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留咱筛,地道東北人搓幌。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像迅箩,于是被迫代替她去往敵國和親鼻种。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內容