天天看点

[JDK8] HashMap源码解析

文章标题

    • 写在前面
    • 底层存储结构
    • 构造HashMap
      • tableSizeFor(int cap)
    • HashMap添加/更新
      • hash(key)
      • putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
      • treeifyBin(Node<K,V>[] tab, int hash)
      • resize()
    • HashMap删除
    • HashMap查找
    • 线程安全

写在前面

HashMap

的实现思想太有含金量了,方方面面都有值得细细品鉴的,想用一篇文章分析透彻,还是比较难的。

我也就是把这么多年的理解尝试着总结一下,写的仓促,可能有错误的地方,欢迎指正!

底层存储结构

HashMap

底层存储结构是数组:

Node<K,V>

HashMap

中定义的一个节点类,用于存储

(key, value)

键值对形式的对象:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // 省略其它
}
           

其中包含四个属性:

  1. key

    :键值对的

    key

  2. value

    :键值对的

    value

  3. hash

    key

    的哈希值,用于计算节点在数组

    table

    中的存储位置
  4. next

    :具有相同

    hash

    值的节点,会存储在数组

    table

    相同的位置,多个节点之间构成链表,数量超过

    8

    个后,转换成红黑树结构

因为数组 + 链表/红黑树这种存储结构就像是一张二维关系表,所以

Node<K,V>[]

取名

table

,更能表达存储结构的含义。

构造HashMap

HashMap

的构造方法有

4

个:

public HashMap() {...}
public HashMap(int initialCapacity) {...}
public HashMap(int initialCapacity, float loadFactor) {...}
public HashMap(Map<? extends K, ? extends V> m) {...}
           

最常用的是前两个构造方法。

第一个没什么好说的,就是一行配置

loadFactor

默认值的代码。

第二个最有意思,传入了一个构造参数

initialCapacity

,这个参数是用来设置数组

table

初始长度的。

说它有意思,是因为

initialCapacity

参数并不是直接拿来用的,它经过了一次二进制转换,变成了另外一个数值:最接近的但不小于initialCapacity本身的2的幂次方。

tableSizeFor(int cap)

跟踪构造方法,可以发现

initialCapacity

参数最终会传递给这个方法,源码如下:

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;
}
           

为了更好的理解转换过程,举几个例子:

  1. 构造参数为3,该方法就返回4;
  2. 构造参数为10,该方法就返回16;
  3. 构造参数为32,该方法就返回32,因为32本身就是2的幂次方

假设方法参数

cap = (1<<30) + 1

,那么

n = 1<<30

,有如下转换过程:

01000000 00000000 00000000 00000000 (n)
01100000 00000000 00000000 00000000 (n |= n >>> 1)
01111000 00000000 00000000 00000000 (n |= n >>> 2)
01111111 10000000 00000000 00000000 (n |= n >>> 4)
01111111 11111111 10000000 00000000 (n |= n >>> 8)
01111111 11111111 11111111 11111111 (n |= n >>> 16)
           

认真体会源码及示例,

tableSizeFor

方法告诉了我们三件事情:

第一,2的幂次方是怎么转换的

转换过程是通过

>>>

|

两个操作完成,全部执行完以后,第一个二进制

1

之后的位空间就都会变成

1

,最后

return

的时候再执行个

n+1

就能得到

2

的幂次方,巧妙!

第二,tableSizeFor的转换最大值

Java

中的

int

是有符号类型,占用

32bit

空间,第一个

bit

是符号位,

表示正数,

1

表示负数。

n = 1<<30

的时候,

n |= n >>> 16

得到的结果就是

int

的最大值,再执行

n+1

操作,最大值就会溢出,变成最小值。

所以,

n

不能大于

1<<30

,进而推导可得

cap

最大值为

1<<30

,刚好是

1G

也就是说,通过

tableSizeFor

转换能得到的最大值是

2

30

次方,这就是

1G

,最大容量字段

MAXIMUM_CAPACITY

定义的由来:

第三,先减1再加1的作用

首先提出疑问:

tableSizeFor

方法第一行先做了个减法操作

n = cap - 1

,最后

return

的时候又做了个加法操作

n + 1

,为什么?多此一举?

并非多此一举,减

1

1

是为了保证方法参数

cap

刚好等于

2

的幂次方时,转换结果还是它本身,例如

cap = 128

时:

00000000 00000000 00000000 10000000 (cap = 128)
00000000 00000000 00000000 01111111 (n = cap - 1)
00000000 00000000 00000000 01111111 (n |= n >>> 1)
00000000 00000000 00000000 01111111 (n |= n >>> 2)
00000000 00000000 00000000 01111111 (n |= n >>> 4)
00000000 00000000 00000000 01111111 (n |= n >>> 8)
00000000 00000000 00000000 01111111 (n |= n >>> 16)
00000000 00000000 00000000 10000000 (return n + 1)
           

这就是二进制运算特性,巧妙!

最后的结果赋值给了属性变量

threshold

int threshold;
this.threshold = tableSizeFor(initialCapacity);
           

变量

threshold

是阈值的意思,表示的含义是

HashMap

中存储的元素超过这个数值的时候,底层数组

table

就要进行扩容了。

数组初始化之前,threshold不是阈值的意思,这点要理解!

通过构造函数初始化

HashMap

对象之后,底层数组

table

并没有被分配数组空间,此时的

threshold

保存着数组初始长度信息,还不是阈值的含义!

HashMap

首次添加元素时,第一次为数组

table

分配空间,通过

threshold

得知第一次分配的数组的长度。之后,

threshold

会被重新计算,再往后才是阈值的含义。

threshold

计算方法是:

int threshold = table.length * loadFactor
           

负载因子

loadFactor

默认是

0.75

负载因子

loadFactor

也可以在通过构造方法指定。

HashMap添加/更新

HashMap

添加

(key, value)

的键值对象,最常用的方法是:

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

顺着这个方法追下去,就是完整的添加/更新逻辑。

hash(key)

添加第一步,就

key

做了一个哈希处理:

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

从中可以看到两个知识点:

  1. key == null

    :哈希值是 ,所以,键值对象

    (null,value)

    永远存储在数组

    table

    的 号位置,也就是第一个位置
  2. key != null

    :在

    JVM

    默认哈希值的基础上,又做了一个变换,让哈希值二进制高

    16bit

    参与到低

    16bit

    运算中

为了更好地理解,举个具体的例子,假设

key

的哈希值是

16711680

00000000 11111111 00000000 00000000 (h = key.hashCode())
00000000 00000000 00000000 11111111 (h >>> 16)
00000000 11111111 00000000 11111111 (h ^ h >>> 16)
           

通过

Java

已有的方法

hashCode()

就可以计算出一个随机的哈希值,为什么非要再转换一次呢?为什么要将哈希值的高

16bit

数据融合到低

16bit

里面呢?

回答这个问题之前,先了解另一个知识点:

hash

值映射到数组

table

下标值的规则。

int h = key.hashCode();   // Object方法计算出的哈希值
int hash = h ^ h >>> 16;  // 哈希值高16bit融合进低16bit
int n = table.length;     // 数组table的长度
int i = (n - 1) & hash;   // hash值映射到数组下标
table[i] = value;         // 数组赋值Node<K,V>对象
           

这段代码是追踪源码后,得到的哈希值映射逻辑,映射规则是

(n - 1) & hash

这是个掩码映射思想,可类比网络

IP

设置中的掩码。

截止到目前,数组

table

的长度始终都是

2

的幂次方,

n - 1

得到的就是高位一串0,低位一串1的二进制数字,也是数组下标的最大值。

举个例子:

00000000 00000000 00000000 00010000 (n = table.length = 16)
00000000 00000000 00000000 00001111 (n - 1)
00000100 00100110 00100101 10001010 (hash)
00000000 00000000 00000000 00001010 (i = (n - 1) & hash)
           

计算出数组下标

i = 10

,由此可以看出,

hash

真正能决定数组下标位置的的只有几个低位二进制数值,高位二进制对映射规则没有影响。

实际使用

HashMap

的时候,存储元素的个数通常不会超过

2

16

次方,也就是

65536

个。

在这个实际应用场景的约束下,计算出来的

hash

最多只有低

16bit

有用,高

16bit

完全没用。如果两个

hash

16bit

相同,高

16bit

不同,它们就会被映射到同一个数组下标,存储在同一个位置。

hash

二进制的高

16bit

融合进低

16bit

,就会改变低

16bit

的数值,进而得到不同的数组下标,存储在不同的位置。

现在可以回答之前的问题了:

HashMap

之所以要再次计算

hash

,将高

16bit

数据融合进低

16bit

,是为了在实际应用中,得到更好的哈希散列性,降低哈希碰撞的概率。

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

这是

HashMap

添加/更新元素的核心方法,源码如下,排版有压缩:

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;
    if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;
        else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        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) resize();
    afterNodeInsertion(evict);
    return null;
}
           

从这段代码里,可以整理出添加/更新逻辑:

  1. 首次添加元素时,数组

    table

    进行第一次初始化
  2. 根据哈希映射规则

    (n - 1) & hash

    计算出数组下标

    i

  3. 如果

    table[i] == null

    ,创建

    Node<K,V>

    对象,封装插入信息,插入数组

    table[i]

  4. 如果

    table[i] != null

    ,说明

    table[i]

    可能是一个

    Node<K,V>

    链表,也可能是一个红黑树

    TreeNode

  5. 如果

    table[i]

    是一个

    Node<K,V>

    链表,就执行链表的新增/更新逻辑
  6. 如果

    table[i]

    是一颗

    TreeNode

    红黑树,就执行红黑树的新增/更新逻辑
  7. 如果链表新增元素后,链表长度超过

    8

    个,就立刻将链表转换成红黑树结构。这么说其实是不太对的,但是为了讲述方便先这么理解吧,后面讲红黑树结构的时候,会说明为什么不对
  8. 新增元素时,如果是链表结构,就添加链表尾部,如果是红黑树,就根据树的特性添加到合适位置。但是还要知道,

    HashMap

    使用红黑树的时候,依旧记录着链表信息,在这个链表信息里面,元素依然是在最后的
  9. 如果两个元素的

    hash

    key

    相同,就说明是相同的元素,执行更新操作,更新元素

    value

  10. 方法参数

    onlyIfAbsent == true

    时,表示

    HashMap

    只能新增元素,不能更新元素
  11. 如果是更新元素,方法返回值是更新前的元素

    value

    值,如果是新增操作,方法返回的是

    null

  12. 如果集合元素数量

    size

    超过

    threshold

    阈值,就进行扩容操作
  13. 每次新增/更新完成后,都会执行一个操作

    ++modCount

    ,这个字段记录的是集合写次数,跟迭代器的使用有密切联系,可以达到迭代器的

    fail-fast

    效果

treeifyBin(Node<K,V>[] tab, int hash)

这个就是链表结构转化成红黑树的方法,源码如下,排版略有压缩:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null) hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null) hd.treeify(tab);
    }
}
           

从中整理出转换逻辑:

  1. 如果数组

    table.length < 64

    ,只进行扩容操作,不会进行红黑树转换。这是

    HashMap

    链表转换红黑树的另一个条件,数组长度需要满足阈值条件

    MIN_TREEIFY_CAPACITY = 64

  2. 红黑树转换过程,是先将

    Node<K,V>

    链表封装成

    TreeNode<K,V>

    链表,然后再通过

    treeify(Node<K,V>[] tab)

    方法真正将其转换成红黑树。所以转换后,这些元素组成的结构既是红黑树,又是链表,两者特性兼而有之!赞叹!巧妙!

resize()

HashMap

首次添加元素,或者,添加元素后

HashMap

元素数量超过

threshold

时,数组

table

就会进行扩容操作。

扩容过程包含两件事情:

  1. 扩大底层数组

    table

    容量,也就是扩大

    HashMap

    的哈希槽,可以容纳更多的

    key

  2. 哈希槽增加后,集合元素需根据

    hash

    值重新映射数组

    table

    下标位置,这个过程叫做重哈希

这两件事情都是在

resize()

方法中完成,第一件事情,扩大数组容量的相关源码如下:

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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;
    // 以下是重哈希部分,省略
}
           

阅读这段代码,可以理出数组扩容的逻辑:

  1. table

    第一次初始化时,

    threshold

    表示数组长度信息,如果没有指定,就使用默认值

    DEFAULT_INITIAL_CAPACITY = 16

  2. 默认负载因子是

    DEFAULT_LOAD_FACTOR = 0.75f

    ,表示当集合元素数量达到

    table.length * 0.75

    的时候,就触发扩容机制
  3. 扩容时,数组长度以

    2

    倍的速度递增,创建

    2

    倍长度新数组,取代原数组
  4. 数组长度最大值是

    Integer.MAX_VALUE

    ,它跟

    MAXIMUM_CAPACITY

    的关系是

    Integer.MAX_VALUE = MAXIMUM_CAPACITY * 2 - 1

  5. 当数组长度达到

    Integer.MAX_VALUE

    时,

    threshold

    阈值也会设置成

    Integer.MAX_VALUE

理清了扩容的逻辑,再来看看重哈希的逻辑,相关源码:

final Node<K,V>[] resize() {
    // 以上是数组扩容逻辑,省略
    Node<K,V>[] oldTab = table;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null, hiHead = null, hiTail = null, next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null) hiHead = e;
                            else hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
           

源码有点长,排版上做点压缩。分析这段代码,理出重哈希逻辑:

  1. 基本思路,遍历原数组,根据

    hash

    计算元素在新数组中的存储位置,存入新数组
  2. 原数组

    table[j]

    ,可能是

    null

    ,可能是一个

    Node<K,V>

    对象,也可能是多个

    Node<K,V>

    对象组成的链表,还可能是个

    TreeNode<K,V>

    红黑树
  3. 如果

    table[j] == null

    ,说明这个位置没有存储对象,也就不需要处理
  4. 如果

    table[j]

    只是一个

    Node<K,V>

    对象,直接计算新的下标值

    e.hash & (newCap - 1)

    ,存入新数组即可
  5. 如果

    table[j]

    是一个

    Node<K,V>

    链表,就根据规则

    e.hash & oldCap

    将其拆分成两个链表,分别存储在新数组

    newTab[j]

    newTab[j + oldCap]

    的位置。这与直接计算元素下标

    e.hash & (newCap - 1)

    效果是一样的,且更为简单直接
  6. 如果

    table[j]

    是一个

    TreeNode<K,V>

    红黑树,拆分就稍微复杂一点,需要详细分析

    TreeNode<K,V>

    split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)

    方法,这里先搁置,另起一节细说

对于第

5

点和第

6

点,有必要单独拿出来再细说一下。

关于第5点

举个例子,理解

table[j]

是个

Node<K,V>

链表的情况:

假设当前

HashMap

8

,现有两个

Node<K,V>

对象

node1

node2

,它们的信息如下:

n = table.length = 8

node1.hash == 0001
(n - 1) & hash = 0111 & 0001 = 0001 = 1
node2.hash == 1001
(n - 1) & hash = 0111 & 1001 = 0001 = 1

table[1] = node1, node2
           

所以,

node1

node2

分别都存储在数组

table[1]

的位置,形成链表。

现在要进行扩容,重哈希,

node1

node2

在新数组中的情况:

oldCap = 8
n = table.length = 16

node1.hash == 0001
(n - 1) & hash = 01111 & 0001 = 0001 = 1
table[1] = node1 // 链表拆分规则:hash & oldCap = 0001 & 1000 = 0000

node2.hash == 1001
(n - 1) & hash = 01111 & 1001 = 1001 = 9
table[9] = node2 // 链表拆分规则:hash & oldCap = 1001 & 1000 = 1000
           

可以发现,其实有两种规则方法,可以完成扩容时的重哈希操作:

  1. 哈希映射规则:

    (n - 1) & hash

  2. 链表拆分规则:

    hash & oldCap

关于第6点

拆分红黑树后需要考虑的问题是拆分后的两个结构应该如何存储?是使用

TreeNode<K,V>

红黑树结构?还是使用

Node<K,V>

链表结构?

相关源码如下:

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null) loHead = e;
            else loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null) hiHead = e;
            else hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) loHead.treeify(tab); // (else is already treeified)
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null) hiHead.treeify(tab);
        }
    }
}
           

整理出拆分逻辑:

  1. 因为

    TreeNode<K,V>

    本身也保存有链表信息,所以先根据上面第

    5

    点讲的链表拆分规则

    hash & oldCap

    将其拆分成两个子链表
  2. 如果子链表长度不大于

    UNTREEIFY_THRESHOLD = 6

    这个阈值,就转换成

    Node<K,V>

    链表,存入新数组对应位置
  3. 如果子链表长度大于

    UNTREEIFY_THRESHOLD = 6

    这个阈值,就转换成

    TreeNode<K,V>

    红黑树,存入新数组对应位置

关于链表和红黑树互转的小总结:

  1. 链表转红黑树的时候,需要元素数量大于等于

    9

  2. 红黑树转链表的时候,需要元素数量小于等于

    6

HashMap删除

删除逻辑相对简单,核心源码是:

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;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        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;
                } 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) tab[index] = node.next;
            else p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
           

逻辑整理如下:

  1. 根据

    hash

    规则映射数组

    table

    下标

    i

    ,如果

    table[i] == null

    ,证明元素不存在,无需删除,直接返回

    null

  2. 如果

    table[i] != null

    ,那么

    table[i]

    可能是链表,也可能是红黑树,所以要区分节点类型,从链表中查找,或者从红黑树中查找
  3. 如果找到元素,就从相应结构中删除,并返回删除元素
  4. 方法参数

    matchValue == true

    ,表示删除的时候,不仅要

    key

    相等,而且

    value

    也要相等,才能删除。当然,这个特性很少用到
  5. 方法参数

    matchValue == false

    ,表示从红黑树结构中删除元素后,不重新移动树的其它节点。这个也不常用,仅作了解

HashMap查找

查找逻辑也简单,核心源码:

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 && ((k = first.key) == key || (key != null && key.equals(k))))  // always check first node
            return first;
        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;
}
           

逻辑整理如下:

  1. 根据

    hash

    映射数组

    table

    下标位置

    i

  2. 如果

    table[i] == null

    ,说明没有该元素,返回

    null

  3. 如果

    table[i] != null

    ,说明

    table[i]

    可能是链表,可能是红黑树
  4. 如果

    table[i]

    是链表,就以链表方式找,有就返回节点,没有就返回

    null

  5. 如果

    table[i]

    是红黑树,就以红黑树方式找,有就返回节点,没有就返回

    null

  6. 如果存在节点,上层的封装方法

    get(Object key)

    也就是从节点中再返回节点的

    value

    值就行了

线程安全

并发场景下,

HashMap

是非线程安全的。

如果要线程安全,就用

ConcurrentHashMap

类。

数组

table

扩容、集合数据重哈希,这两个过程是最容易出现线程问题的。

因为随着集合数据量的增加,重哈希是一个比较耗时的操作,扩容过程其实就是原有集合数据重新写入新数组的过程。

多线程场景下,短时间内向同一个地方大量写入数据,就是容易出现线程安全问题。

如果出现线程安全问题,

HashMap

最可能出现的现象就是数据丢失,具体过程就不分析了。

写的够多了,就到这里吧,

Markdown

编辑器已经顶不住了,太卡了。

继续阅读