hashmap源碼分析( 基于java8)

Heier 發(fā)布于2019-08-19 11:03 / 2196人閱讀

摘要：源碼分析簡(jiǎn)介的和操作的時(shí)間復(fù)雜度是常量?？梢源骀I值為，是線程不安全的。數(shù)組鏈表散列的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)桶，鏈表的實(shí)現(xiàn)桶的實(shí)現(xiàn)鏈表的實(shí)現(xiàn)值節(jié)點(diǎn)的鍵節(jié)點(diǎn)的值下一個(gè)節(jié)點(diǎn)鏈表構(gòu)造方法方法是線程不安全的判斷兩個(gè)元素是否相等重要屬性默認(rèn)的桶初始容量。

hashmap源碼分析 簡(jiǎn)介

hashmap的get和put操作的時(shí)間復(fù)雜度是常量。通過(guò)調(diào)用哈希函數(shù)將元素正確的分布到桶中。初始容量(capacity)的值不能設(shè)置太高，加載因子(loadfactor)不能設(shè)置的太低，否則會(huì)影響迭代的性能。
一個(gè)hashmap的實(shí)例有兩個(gè)參數(shù)將影響它的性能。初始容量、加載因子。初始容量是hashmap在創(chuàng)建時(shí)候桶的大小。加載因子用來(lái)確定何時(shí)進(jìn)行擴(kuò)容（size > 容量*加載因子）。擴(kuò)容的時(shí)候也會(huì)進(jìn)行對(duì)內(nèi)部的數(shù)據(jù)結(jié)構(gòu)進(jìn)行重新構(gòu)建，使桶的大小增加兩倍。

默認(rèn)的加載因子（0.75）在時(shí)間和空間復(fù)雜度上提供了很好的權(quán)衡。大一點(diǎn)的話會(huì)減少空間但是會(huì)增加get和put的時(shí)間。

hashmap可以存鍵值為null，是線程不安全的。如果想線程安全可以使用Collections.synchronizedMap()包裝.
或者使用ConcurrentMap，這個(gè)map是線程安全的。

hashmap數(shù)據(jù)結(jié)構(gòu)

hashmap是一個(gè)散列表，存儲(chǔ)的內(nèi)容是key-value。就像我們用的字典一樣，用過(guò)字母（key）查找單詞(value)。hashmap的時(shí)間復(fù)雜度是O(longN)。

在java8之前hashmap采用的是桶+鏈表的數(shù)據(jù)結(jié)構(gòu)。但是如果數(shù)據(jù)很大，鏈表的查找時(shí)間復(fù)雜度是O(n)，顯然者違背了hashmap的初衷，所以在鏈表的元素大于8的時(shí)候，java8會(huì)把鏈表旋轉(zhuǎn)為紅黑樹(shù)。

[數(shù)組鏈表散列（hash）
](https://blog.csdn.net/u013565...

hashmap的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 桶，鏈表的實(shí)現(xiàn)

桶的實(shí)現(xiàn):

transient Node[] table;

鏈表的實(shí)現(xiàn):

    
    
static class Node implements Map.Entry {

    final int hash;//hash值
    final K key;//節(jié)點(diǎn)的鍵
    V  value;//節(jié)點(diǎn)的值
    Node next;//下一個(gè)節(jié)點(diǎn)（鏈表）

Node(int hash, K key, V value, Node next) {//構(gòu)造方法
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}

//方法是線程不安全的
public final K getKey()        { return key; }
public final V getValue()      { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
    V oldValue = value;
    value = newValue;
    return oldValue;
}

public final boolean equals(Object o) {//判斷兩個(gè)元素是否相等
    if (o == this)
        return true;
    if (o instanceof Map.Entry) {
        Map.Entry e = (Map.Entry)o;
        if (Objects.equals(key, e.getKey()) &&
            Objects.equals(value, e.getValue()))
            return true;
    }
    return false;
}
}

重要屬性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)的桶初始容量（2^4=16）。

static final int MAXIMUM_CAPACITY = 1 << 30;//最大的桶的容量

static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認(rèn)的加載因子

static final int TREEIFY_THRESHOLD = 8;//當(dāng)鏈表大于這個(gè)閾值會(huì)被旋轉(zhuǎn)為紅黑樹(shù)

static final int UNTREEIFY_THRESHOLD = 6;//當(dāng)做resize操作的時(shí)候，如果桶中某個(gè)節(jié)點(diǎn)的數(shù)量小于這個(gè)閾值，則把樹(shù)旋轉(zhuǎn)為鏈表

static final int MIN_TREEIFY_CAPACITY = 64;//當(dāng)桶中的數(shù)量大于64是，才會(huì)判斷是否轉(zhuǎn)換成樹(shù)

transient Node[] table;//桶

transient int size;//hashmap的存儲(chǔ)的元素大小

transient int modCount;//hashmap結(jié)構(gòu)被修改的次數(shù)

int threshold;//擴(kuò)容閾值

final float loadFactor;//加載因子

構(gòu)造方法

構(gòu)造方法會(huì)創(chuàng)建一個(gè)空的桶，計(jì)算擴(kuò)容閾值和加載因子

HashMap(int,float)

public HashMap(int initialCapacity, float loadFactor) {//桶初始化容量，加載因子
if (initialCapacity < 0)//桶初始容量不能小于0
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//如果桶初始化容量大于hashmap最大的容量，則初始化容量等于最大的容量
    initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//計(jì)算擴(kuò)容閾值
}

HashMap(int)

public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//加載因子為默認(rèn)的0.75
}

HashMap()

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; //桶初始容量為0，加載因?yàn)?.75
}

HashMap(Map)

public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//加載因子為默認(rèn)的0.75
putMapEntries(m, false);//map放入桶中
}



final void putMapEntries(Map m, boolean evict) {
int s = m.size();//插入元素大小
if (s > 0) {//如果大于0 ，則繼續(xù)進(jìn)行插入操作
    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)//如果插入元素?cái)?shù)量大于擴(kuò)容閾值，則桶的大小擴(kuò)容兩倍
        resize();
    for (Map.Entry e : m.entrySet()) {
        K key = e.getKey();
        V value = e.getValue();
        putVal(hash(key), key, value, false, evict);//插入元素
    }
}
}

主要的幾個(gè)方法分析 get(Obejct)

public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}


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


//根據(jù)key獲取value
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;//tab:桶 first：桶中節(jié)點(diǎn)的第一個(gè)元素    n:桶的長(zhǎng)度 k:第一個(gè)節(jié)點(diǎn)的key
if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & hash]) != null) {//如果桶不為空，并且key所在的節(jié)點(diǎn)的第一個(gè)元素不為空
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))//如果key是節(jié)點(diǎn)的第一元素則返回節(jié)點(diǎn)的第一個(gè)元素
        return first;
    if ((e = first.next) != null) {//遍歷鏈表/平衡樹(shù) 查找元素
        if (first instanceof TreeNode)
            return ((TreeNode)first).getTreeNode(hash, key);//在樹(shù)中查找 
        do {
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        } while ((e = e.next) != null);
    }
}
return null;
}

put(K,V)

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;//如果桶為空，擴(kuò)容兩倍
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);//如果key所在的桶第一個(gè)元素為null則直接插入桶中的第一個(gè)節(jié)點(diǎn)
else {//否則插入鏈表/樹(shù)
    Node e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;//如果插入的元素等于桶中的第一個(gè)一個(gè)元素，直接返回桶中的第一個(gè)元素
    else if (p instanceof TreeNode)
        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//如果是樹(shù)節(jié)點(diǎn)，插入樹(shù)中
    else {//插入鏈表中
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++modCount;
if (++size > threshold)//如果hashmap中的元素等于擴(kuò)容閾值，則重新構(gòu)造數(shù)據(jù)結(jié)構(gòu)
    resize();
afterNodeInsertion(evict);
return null;
}

hash（）

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

h是原始的hash返回的值是int類型，int取值范圍:-2147483648到2147483648,前后加起來(lái)大概四十億的映射空間。只要hash函數(shù)映射的比較松散，一般是很難出現(xiàn)碰撞的。
但是考慮到實(shí)際的內(nèi)存的大小，很難放下這么大的數(shù)組。

所以為了空間上的考慮上述中的擾動(dòng)函數(shù)，對(duì)原始計(jì)算出來(lái)的hash值（int 四個(gè)字節(jié)32位），右移16位，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始hash值的高位和地位，以此來(lái)加大低位的隨機(jī)性。而且混合后的地位參雜了高位的部分特征，這樣高位的信息也被變相的保留下來(lái)了。

線程安全性

hashmap線程不安全的，如果要使用安全的hashmap建議使用ConcurrentHashMap。

參考：

hash（）原理: https://www.zhihu.com/questio...

關(guān)注我的公眾號(hào)第一時(shí)間閱讀有趣的技術(shù)故事
掃碼關(guān)注：

也可以在微信搜索公眾號(hào)即可關(guān)注我：codexiulian
渴望與你一起成長(zhǎng)進(jìn)步！

GPU云服務(wù)器云服務(wù)器基于數(shù)據(jù)分析基于數(shù)據(jù)的分析基于大數(shù)據(jù)分析基于大數(shù)據(jù)分析學(xué)習(xí)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76918.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Heier

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

RackNerd LLC：雙11活動(dòng)，4款美國(guó)便宜VPS低至$12/年，機(jī)房可選洛杉磯、圣何塞、西雅

閱讀 1101·2021-11-15 18:00
云主機(jī)如何連接-云主機(jī)怎么用手機(jī)連接？

閱讀 2815·2021-09-22 15:18
初始Selenium

閱讀 1977·2021-09-04 16:45
響應(yīng)式網(wǎng)頁(yè)布局 - W3Schools How-Tos 01

閱讀 758·2019-08-30 15:55
用CSS3 transition屬性實(shí)現(xiàn)淡入淡出輪播圖

閱讀 3870·2019-08-30 13:10
圖片批量上傳js+html+css

閱讀 1345·2019-08-30 11:06
HTML & CSS 之小白再續(xù)前緣

閱讀 1994·2019-08-29 12:51
JavaScript發(fā)展史，JavaScript組成和開(kāi)發(fā)工具介紹-樂(lè)字節(jié)

閱讀 2302·2019-08-26 13:55

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

hashmap源碼分析( 基于java8)

相關(guān)文章

初探Java8中的HashMap

HashMap ConcurrentHashMap

Java學(xué)習(xí)路線總結(jié)，搬磚工逆襲Java架構(gòu)師（全網(wǎng)最強(qiáng)）

Java相關(guān)

**Java容器之HashMap傾力詳解 - 用得那么多，但你真的懂嗎？**

發(fā)表評(píng)論

0條評(píng)論

Heier

男|高級(jí)講師

TA的文章

RackNerd LLC：雙11活動(dòng)，4款美國(guó)便宜VPS低至$12/年，機(jī)房可選洛杉磯、圣何塞、西雅

云主機(jī)如何連接-云主機(jī)怎么用手機(jī)連接？

初始Selenium

響應(yīng)式網(wǎng)頁(yè)布局 - W3Schools How-Tos 01

用CSS3 transition屬性實(shí)現(xiàn)淡入淡出輪播圖

圖片批量上傳js+html+css

HTML & CSS 之小白再續(xù)前緣

JavaScript發(fā)展史，JavaScript組成和開(kāi)發(fā)工具介紹-樂(lè)字節(jié)

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

hashmap源碼分析( 基于java8)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！