HashMap學(xué)習(xí)筆記

一、HashMap學(xué)習(xí)筆記

HashMap采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，只是在jdk1.7和1.8的實(shí)現(xiàn)上有所不同，下面，簡(jiǎn)單的分析一下，方便自己更加深刻的理解這種典型的key-value的數(shù)據(jù)結(jié)構(gòu)。

1.1.jdk1.7實(shí)現(xiàn)原理簡(jiǎn)單分析

1.7的HashMap數(shù)據(jù)結(jié)構(gòu)圖

WX20181201-102134@2x

也可以這么理解

image-20181201115225976

在jdk1.8之前，HashMap由數(shù)組 + 鏈表組成，也就是鏈表散列，數(shù)組是HashMap的主體，鏈表實(shí)則是為了解決哈希沖突而存在的，（拉鏈法解決哈希沖突） 。

HashMap 通過 key 的 hashCode 經(jīng)過擾動(dòng)函數(shù)處理過后得到 hash 值，然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長(zhǎng)度），如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鏈法解決沖突。

所謂擾動(dòng)函數(shù)指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動(dòng)函數(shù)是為了防止一些實(shí)現(xiàn)比較差的 hashCode() 方法 換句話說使用擾動(dòng)函數(shù)之后可以減少碰撞。

所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合。也就是說創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

1.7的HashMap類中的常量

/** 初始化桶大小，HashMap底層是數(shù)組，這個(gè)是數(shù)組默認(rèn)的大小 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**  桶的最大值 */
static final int MAXIMUM_CAPACITY = 1 << 30;

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

static final Entry<?,?>[] EMPTY_TABLE = {};

/** table真正存放數(shù)據(jù)的數(shù)組 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/** map中存放數(shù)據(jù)的大小 */
transient int size;

/** 桶大小?？梢栽诔跏蓟臅r(shí)候顯示指定 */
int threshold;

/** 負(fù)載因子，可以在初始化的時(shí)候顯示指定 */
final float loadFactor;

loadFactor負(fù)載因子

默認(rèn)的HashMap的容量是16，負(fù)載因子是0.75，當(dāng)我們?cè)谑褂肏ashMap的時(shí)候，隨著我們不斷的put數(shù)據(jù)，當(dāng)數(shù)量達(dá)到16 * 0.75 = 12的時(shí)候，就需要將當(dāng)前的16進(jìn)行擴(kuò)容，而擴(kuò)容就涉及到數(shù)據(jù)的復(fù)制，rehash等，就消耗性能，所謂的負(fù)載因子，也可以叫加載因子，用來控制數(shù)組存放數(shù)據(jù)的疏密程度，loadFactor越趨緊與1，說明數(shù)組中存放的entry越多，鏈表的長(zhǎng)度就越長(zhǎng)。所以，建議當(dāng)我們知道HashMap的使用大小時(shí)，應(yīng)該在初始化的時(shí)候指定大小，減少擴(kuò)容帶來的性能消耗。

loadFactor太大導(dǎo)致查找元素效率低，太小導(dǎo)致數(shù)組的利用率低，存放的數(shù)據(jù)會(huì)很分散。loadFactor的默認(rèn)值為0.75f是官方給出的一個(gè)比較好的臨界值。

threshold桶大小

threshold桶大小，也叫臨界值，threshold = capacity \* loadFactor，當(dāng)HashMap的Size>=threshold的時(shí)候，那么就要考慮對(duì)數(shù)組的擴(kuò)增了，也就是說，這個(gè)的意思就是 threshold是衡量數(shù)組是否需要擴(kuò)增的一個(gè)標(biāo)準(zhǔn)。

table存放數(shù)據(jù)的數(shù)組

table數(shù)組中存放的是Entry類型的數(shù)據(jù)，下面我們簡(jiǎn)單看看Entry的定義。

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    /** 創(chuàng)建一個(gè)新的Entry */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

Entry是一個(gè)內(nèi)部類，其中的key就是寫入的鍵，value就是寫入的值，由于HashMap由數(shù)組+鏈表的形式，這里的next就是用于實(shí)現(xiàn)鏈表結(jié)構(gòu)。hash存放的事當(dāng)前key的hashcode值。

put()方法

public V put(K key, V value) {
    /** 判斷當(dāng)前數(shù)組是否需要初始化 */
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    /** 如果key為空，則put一個(gè)空值進(jìn)去 */
    if (key == null)
        return putForNullKey(value);
    /** 根據(jù)key計(jì)算出hashcode值 */
    int hash = hash(key);
    /** 根據(jù)計(jì)算的hashcode值定位所在的桶 */
    int i = indexFor(hash, table.length);
    /** 如果桶是一個(gè)鏈表則需要遍歷判斷里面的 hashcode、key 是否和傳入 key 相等， */
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        /** 如果相等則進(jìn)行覆蓋，并返回原來的值 */
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    /** 如果桶是空的，說明當(dāng)前位置沒有數(shù)據(jù)存入；新增一個(gè) Entry 對(duì)象寫入當(dāng)前位置 */
    addEntry(hash, key, value, i);
    return null;
}

新增一個(gè)Entry

void addEntry(int hash, K key, V value, int bucketIndex) {
    /** 判斷當(dāng)前HashMap的size與臨界值的大小，判斷是否需要擴(kuò)容操作 */
    if ((size >= threshold) && (null != table[bucketIndex])) {
        /** 如果需要擴(kuò)容，就進(jìn)行2倍擴(kuò)容 */
        resize(2 * table.length);
        /** 將當(dāng)前的key重新hash并定位 */
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    /** 創(chuàng)建一個(gè)Entry,如果當(dāng)前桶存在元素，就形成鏈表 */
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

put()方法簡(jiǎn)單將如下：

image-20181201122714806

get()方法

public V get(Object key) {
    /** 如果key為null,就去數(shù)組[0]的位置找 */
    if (key == null)
        return getForNullKey();
    /** 根據(jù)key獲取Entry */
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
    /** 如果當(dāng)前HashMap的size都為0，那就直接返回null */
    if (size == 0) {
        return null;
    }
    /** 根據(jù)key計(jì)算hashcode值,然后定位到具體的桶中 */
    int hash = (key == null) ? 0 : hash(key);
    /** 判斷是否是鏈表，為鏈表則需要遍歷直到 key 及 hashcode 相等時(shí)候就返回值*/
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        /** 不是鏈表就根據(jù) key、key 的 hashcode 是否相等來返回值*/
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    /** 啥都沒取到就直接返回 null */
    return null;
}

1.2.jdk1.8實(shí)現(xiàn)原理簡(jiǎn)單分析

在jdk1.7中HashMap實(shí)現(xiàn)原理分析，我們知道當(dāng)hash沖突很嚴(yán)重的時(shí)候，鏈表的長(zhǎng)度就會(huì)很長(zhǎng)，我們也知道數(shù)組和鏈表的優(yōu)缺點(diǎn)，簡(jiǎn)單總結(jié)一下：

數(shù)組：數(shù)據(jù)存儲(chǔ)是連續(xù)的，占用內(nèi)存很大，所以空間復(fù)雜度較高，但是二分查找的時(shí)間復(fù)雜度為O(1)，簡(jiǎn)單講就是，數(shù)組尋址容易，插入和刪除較為困難。

鏈表：存儲(chǔ)區(qū)間零散，所以內(nèi)存較為寬松，故空間復(fù)雜度較低，但是時(shí)間復(fù)雜的高，為O(n)，簡(jiǎn)單講就是，鏈表尋址困難，插入和刪除較為容易。

所以，在jdk1.8中，對(duì)HashMap的實(shí)現(xiàn)做了相應(yīng)的修改，jdk1.8 以后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為 8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間。

1.8的HashMap的數(shù)據(jù)結(jié)構(gòu)圖

image-20181201133831561

1.8的HashMap類的常量

/** 默認(rèn)的初始容量16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

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

/** 默認(rèn)的填充因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/** 當(dāng)桶上的節(jié)點(diǎn)數(shù)量大于8時(shí)，會(huì)將鏈表轉(zhuǎn)為紅黑樹 */
static final int TREEIFY_THRESHOLD = 8;

/** 當(dāng)桶上的節(jié)點(diǎn)數(shù)量小于6時(shí)，會(huì)將紅黑樹轉(zhuǎn)為鏈表 */
static final int UNTREEIFY_THRESHOLD = 6;

/**桶中的結(jié)構(gòu)轉(zhuǎn)為紅黑樹對(duì)應(yīng)的最小數(shù)組大小為64 */
static final int MIN_TREEIFY_CAPACITY = 64;

/** 存儲(chǔ)元素的數(shù)組，總是2的冪次倍 */
transient Node<K,V>[] table;

/** 存放具體元素的集合 */
transient Set<Map.Entry<K,V>> entrySet;

/** 存放元素的個(gè)數(shù)，注意的是這個(gè)值不等于數(shù)組的長(zhǎng)度 */
transient int size;

/** 每次擴(kuò)容或者更改map結(jié)構(gòu)的計(jì)數(shù)器 */
transient int modCount;

/** 臨界值，當(dāng)實(shí)際大?。ㄈ萘?* 負(fù)載因子）超過臨界值的時(shí)候，就會(huì)進(jìn)行擴(kuò)容操作 */
int threshold;

/** 負(fù)載因子 */
final float loadFactor;

對(duì)比1.7中的常量，我們就會(huì)發(fā)現(xiàn)1.8中做了如下的改變。

  • 增加了TREEIFY_THRESHOLD，當(dāng)鏈表的長(zhǎng)度超過這個(gè)值的時(shí)候，就會(huì)將鏈表轉(zhuǎn)換紅黑樹。
  • Entry修改為Node，雖然Node的核心也是key、value、next。

Node類

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 哈希值
    final K key; // key
    V value; // value
    Node<K,V> next; // 指向下一個(gè)節(jié)點(diǎn)
}

樹節(jié)點(diǎn)類

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父
    TreeNode<K,V> left;    // 左
    TreeNode<K,V> right;   // 右
    TreeNode<K,V> prev;    
    boolean red;           // 判斷顏色
}

put()方法

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<K,V>[] tab; Node<K,V> p; int n, i;
    /** 判斷當(dāng)前桶是否為空，空的就需要初始化（resize 中會(huì)判斷是否進(jìn)行初始化） */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /** 根據(jù)當(dāng)前 key 的 hashcode 定位到具體的桶中并判斷是否為空，
     * 為空表明沒有 Hash 沖突就直接在當(dāng)前位置創(chuàng)建一個(gè)新桶即可。
     */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        /** 如果當(dāng)前桶有值（ Hash 沖突），
         * 那么就要比較當(dāng)前桶中的 key、key 的 hashcode 與寫入的 key 是否相等，相等就賦值給 e
         */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;     
        /** 如果當(dāng)前桶為紅黑樹，那就要按照紅黑樹的方式寫入數(shù)據(jù)*/
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            /** 如果是個(gè)鏈表，就需要將當(dāng)前的 key、value 封裝成一個(gè)新節(jié)點(diǎn)寫入到當(dāng)前桶的后面（形成鏈表）*/
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    /** 接著判斷當(dāng)前鏈表的大小是否大于預(yù)設(shè)的閾值，大于時(shí)就要轉(zhuǎn)換為紅黑樹 */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                /** 如果在遍歷過程中找到 key 相同時(shí)直接退出遍歷 */  
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        /** 如果 e != null 就相當(dāng)于存在相同的 key,那就需要將值覆蓋 */
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    /** 最后判斷是否需要進(jìn)行擴(kuò)容 */
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put方法圖解

image-20181201174411906

get()方法

public V get(Object key) {
    Node<K,V> e;
    /** 首先將 key hash 之后取得所定位的桶 */
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    /** 如果桶為空則直接返回 null  */
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        /** 否則判斷桶的第一個(gè)位置(有可能是鏈表、紅黑樹)的 key 是否為查詢的 key，是就直接返回 value */
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /** 如果第一個(gè)不匹配，則判斷它的下一個(gè)是紅黑樹還是鏈表 */
        if ((e = first.next) != null) {
            /** 紅黑樹就按照樹的查找方式返回值 */
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            /** 鏈表就遍歷匹配返回值 */
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

小結(jié)

從上面的簡(jiǎn)單分析中，我們可以知道在jdk1.8之后，對(duì)HashMap的實(shí)現(xiàn)做了改變，主要在于將鏈表的長(zhǎng)度超過臨界值的時(shí)候，就將鏈表轉(zhuǎn)為紅黑樹，利用紅黑樹的優(yōu)點(diǎn)，可以更好的查找元素，使得查詢的時(shí)間復(fù)雜度變?yōu)镺(logn)

但是，jdk1.8并未有修改HashMap之前的線程安全問題，我們都知道HashMap是線程不安全的，涉及到線程安全的時(shí)候，我們應(yīng)該使用ConcurrentHashMap，有關(guān)ConcurrentHashMap的知識(shí)將在下一片博客中學(xué)習(xí)，這里簡(jiǎn)單的分析一下，為什么HashMap會(huì)造成線程不安全尼？

1.3.HashMap線程不安全的原因

resize造成死循環(huán)

在1.7中，當(dāng)數(shù)據(jù)put進(jìn)HashMap的時(shí)候，都會(huì)比較和thredhold的大小，當(dāng)超過臨界值的時(shí)候，就會(huì)進(jìn)行擴(kuò)容操作，就會(huì)調(diào)用resize()方法。而resize()中調(diào)用了transfer方法。下面簡(jiǎn)單的看看transfer方法。

但是在1.8中，resize()方法的實(shí)現(xiàn)和1.7有一些不一樣，沒有使用transfer方法，可以說1.8中hashmap不會(huì)因?yàn)槎嗑€程put導(dǎo)致死循環(huán)，但是依然有其他的弊端，比如數(shù)據(jù)丟失等。因此多線程情況下還是建議使用concurrenthashma,

Jdk1.7中transfer方法如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

transfer方法的的作用就是：

  • 對(duì)索引數(shù)組中的元素遍歷
  • 對(duì)鏈表上的每一個(gè)節(jié)點(diǎn)遍歷：用 next 取得要轉(zhuǎn)移那個(gè)元素的下一個(gè)，將 e 轉(zhuǎn)移到新 Hash 表的頭部，使用頭插法插入節(jié)點(diǎn)。
  • 循環(huán)2，直到鏈表節(jié)點(diǎn)全部轉(zhuǎn)移
  • 循環(huán)1，直到所有索引數(shù)組全部轉(zhuǎn)移

轉(zhuǎn)移的時(shí)候是逆序的。假如轉(zhuǎn)移前鏈表順序是1->2->3，那么轉(zhuǎn)移后就會(huì)變成3->2->1。死鎖問題不就是因?yàn)?->2的同時(shí)2->1造成的嗎？所以，HashMap 的死鎖問題就出在這個(gè)transfer()函數(shù)上。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 先看下JAVA中Map的類關(guān)系圖 下面針對(duì)各個(gè)實(shí)現(xiàn)類的特點(diǎn)做一些說明： (1) HashMap：它根據(jù)鍵的hash...
    luoyoub閱讀 354評(píng)論 0贊 0
  • 摘要 HashMap是Java程序員使用頻率最高的用于映射(鍵值對(duì))處理的數(shù)據(jù)類型。隨著JDK（Java Deve...
    周二倩你一生閱讀 1,357評(píng)論 0贊 5
  • HashMap 是 Java 面試必考的知識(shí)點(diǎn)，面試官?gòu)倪@個(gè)小知識(shí)點(diǎn)就可以了解我們對(duì) Java 基礎(chǔ)的掌握程度。網(wǎng)...
    野狗子嗷嗷嗷閱讀 6,806評(píng)論 9贊 107
  • 撐傘繞湖徐行，蜻蜓低飛捉蟲。采得紅花一朵，知否？知否？我情！ 外面雨驟風(fēng)疾，多多注意身體。不要迷花戀草，懂否？懂否...
    hsy751115閱讀 138評(píng)論 0贊 0
  • 《送楊山人歸嵩山》·李白 我有萬(wàn)古宅，嵩陽(yáng)玉女峰。 長(zhǎng)留一片月，掛在東溪松。 爾去掇仙草，菖蒲花紫茸。 歲晚或相訪...
    刀客特唬閱讀 974評(píng)論 11贊 18

友情鏈接更多精彩內(nèi)容