风在路上
zdk
2022-02-20
目录

java基础

Table of Contents generated with DocToc (opens new window)

# 集合框架

# 思维导图

# List

# ArrayList扩容

新容量为原数组长度的1.5倍，如果扩容后的容量依然小于需要的容量，就将需要容量作为数组的长度。

然后将原数组元素拷贝到新的数组并返回

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11

# ArrayList在jdk7、8的不同

  1. jdk7

    • ArrayList list = new ArrayList()；//底层elementData数组初始大小为10
    • 执行add()时，如果此次的添加导致底层elementData数组容量不够，则扩容。默认情况下，扩容为原来容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中

  2. jdk8

    底层elementData初始化为{}，并没有初始化为长度10的数组，而是第一次调用add的时候，底层才创建了长度为10的数组，并将数据加入到数组。后续的添加和扩容操作与JDK7无异

  3. 总结：

    JDK7中的ArrayList的对象创建类似于单例模式中的饿汉式，而JDK8中的类似于懒汉式，延迟了数组的创建，节省了内存

# HashSet

底层也是数组(是一个HashMap)，初始容量为16，当如果使用率超过0.75，(16*0.75=12)就会扩大容量为原来的2倍。(16扩容为32，依次为64,128.....等) 详情见HashMap源码

添加元素的过程

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为:索引位置），判断数组此位置上是否已经有元素:

​ 如果此位置上没有其他元素，则元素α添加成功。---->情况1

​ 如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值: 如果hash值不相同，则元素α添加成功。---->情况2

​ 如果hash值相同，进而需要调用元素α所在类的equals()方法: 如果equals()返回true,元素α添加失败 如果equals()返回false,则元素α添加成功。---->情况3

对于添加成功的情况2和情况3而言:元素a与已经存在指定索引位置上数据以链表的方式存储。

jdk7：元素α放到数组中，指向原来的元素。 jdk8：原来的元素在数组中，指向元素α

# HashMap

# HashMap的底层原理

在jdk1.7之前HashMap是基于数组和链表 (opens new window)实现的，而且采用头插法。

而jdk1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。采用尾插法。

image

# HashMap怎么扩容

HashMap默认的初始化大小为 16。当HashMap中的元素个数之和大于负载因子*当前容量的时候就要进行扩充，容量变为原来的 2 倍。（这里注意不是数组中的个数，而且数组中和链/树中的所有元素个数之和！）

注意：我们还可以在预知存储数据量的情况下，提前设置初始容量（初始容量 = 预知数据量 / 加载因子）。这样做的好处是可以减少 resize() 操作，提高 HashMap 的效率

# HashMap是线程不安全的吗

HashMap是线程不安全的，其主要体现在：

  1. 在jdk1.7中，多线程环境下，扩容时可能会造成环形链或数据丢失
  2. 在jdk1.8中，多线程环境下，会发生数据覆盖的情况

# HashMap扩容的时候为什么是2的n次幂？

数组下标的计算方法是hash&(n-1)，取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

# HashMap使用的hash的实现

jdk8中，是通过hashCode()的高16异或低16位实现的：(hash = key.hashCode()) ^ (hash >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。

# 为什么要用异或运算符

保证了对象的hashCode的32位值，只要有一位发生改变，整个hash()的返回值就会改变，尽可能地减少碰撞

# HashMap的table的容量如何确定？loadFactor是什么？该容量如何变化？这种变化会带来什么问题？

  1. table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；
  2. loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；
  3. 扩容时，调用 resize() 方法，将 table 长度变为原来的两倍(注意是 table 长度，而不是 threshold)
  4. 如果数据很大的情况下，扩容时将会带来性能的损失，在形内要求很高的地方，这种损失可能会很致命。

# HashMap扩容的具体步骤

# jdk7

# 扩容必须满足的条件
  1. 存放新值的时候当前已有的元素个数必须大于等于阈值(threshold=cap*0.75)
  2. 存放新值的时候刚好产生hash碰撞(当前key计算的hash值换算出的数组下标位置已存在值)
# put方法的源码
public V put(K key, V value) {
　　　　//判断当前Hashmap(底层是Entry数组)是否存值（是否为空数组）
　　　　if (table == EMPTY_TABLE) {
　　　　　　inflateTable(threshold);//如果为空，则初始化
　　　　}　　　
　　　　//判断key是否为空
　　　　if (key == null)
　　　　　　return putForNullKey(value);//hashmap允许key为空　　　
　　　　//计算当前key的哈希值　　　　
　　　　int hash = hash(key);
　　　　//通过哈希值和当前数据长度，算出当前key值对应在数组中的存放位置
　　　　int i = indexFor(hash, table.length);
　　　　for (Entry<K,V> e = table[i]; e != null; e = e.next) {
　　　　　　Object k;
　　　　　　//如果计算的哈希位置有值（及hash冲突），且key值一样，则覆盖原值value，并返回原值value
　　　　　　if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
　　　　　　　　V oldValue = e.value;
　　　　　　　　e.value = value;
　　　　　　　　e.recordAccess(this);
　　　　　　　　return oldValue;
　　　　　　}
　　　　}
　　　　modCount++;
　　　　//存放值的具体方法
　　　　addEntry(hash, key, value, i);
　　　　return null;
　　}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还要判断是否需要扩容

void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　//1、判断当前个数是否大于等于阈值
　　　　//2、当前存放是否发生哈希碰撞
　　　　//如果上面两个条件否发生，那么就扩容
　　　　if ((size >= threshold) && (null != table[bucketIndex])) {
　　　　　　//扩容，并且把原来数组中的元素重新放到新数组中
　　　　　　resize(2 * table.length);
　　　　　　hash = (null != key) ? hash(key) : 0;
　　　　　　bucketIndex = indexFor(hash, table.length);
　　　　}
　　　　createEntry(hash, key, value, bucketIndex);
　　}
1
2
3
4
5
6
7
8
9
10
11
12

如果需要扩容，调用扩容的方法resize()

void resize(int newCapacity) {
　　　　Entry[] oldTable = table;
　　　　int oldCapacity = oldTable.length;
　　　　//判断是否有超出扩容的最大值，如果达到最大值则不进行扩容操作
　　　　if (oldCapacity == MAXIMUM_CAPACITY) {
　　　　　　threshold = Integer.MAX_VALUE;
　　　　　　return;
　　　　}
　　　　Entry[] newTable = new Entry[newCapacity];
　　　　// transfer()方法把原数组中的值放到新数组中
　　　　transfer(newTable, initHashSeedAsNeeded(newCapacity));
　　　　//设置hashmap扩容后为新的数组引用
　　　　table = newTable;
　　　　//设置hashmap扩容新的阈值
　　　　threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
　　}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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);
　　　　　　　　}
　　　　　　　　//通过key值的hash值和新数组的大小算出在当前数组中的存放位置
　　　　　　　　int i = indexFor(e.hash, newCapacity);
　　　　　　　　e.next = newTable[i];
　　　　　　　　newTable[i] = e;
　　　　　　　　e = next;
　　　　　　}
　　　　}
　　}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

jdk7及以前使用的是头插法(jdk8使用尾插法)

注：使用头插法在多线程扩容的时候可能会导致循环指向，从而在获取数据get()的时候陷入死循环，到是线程执行无法结束

头插法：

比如[1]->2->3->4->5 1是数组当前的node，如果插入一个0，头插法，链表应该变成[0]->1->2->3->4->5

先插入的会被逐步放到最底下，越后来的会被放在头部，并将next指针指向之前的头部，这样在扩容的时候，先取头部然后把头部放到新对应数组下标的链表处，由于头插法，最早取的会被最先放进并逐步变成最尾，如果多线程执行扩容，将数组下标3位置链表存入的A->B->C扩容时存入到新的数组（假设扩容后A/B/C还在同一个链表上），线程1取第一个元素A被挂起的时候，挂起的元素A元素的next指向B，而线程2放入新的链表时，A被先放但没有完成，线程2在放入B后，B的next指向之前放入的A，当线程1执行的时候本身A的next指向B，这样就行程了循环引用，最后存入C，并将C的next指向B，最终就变成C->B-><-A，在get()方法执行到该数组下标时，遍历链表查找的时候就会出现死循环。

尾插法：

比如[1]->2->3->4->5 1是数组当前的node，如果插入一个0，尾插法，链表应该变成[1]->2->3->4->5->0

元素插入的时候都是从尾部插入，这样新进来的就在头部，后进来的就在尾部，扩容的时候，先进来的先出，指向next和扩容前方向一致，所以不存在循环指向的问题。

# 总结

Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。

因为上面这两个条件，所以存在下面这些情况

  1. 就是当HashMap存值的时候(默认大小为16，负载因子0.75，阈值12)，可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值在底层数组中都分别占据一个位置，并没有发生hash碰撞。
  2. 当然也可能存储更多值(超过16个值，最多27个值)都还没有扩容。原因：前11个值全部hash碰撞，存到数组同一下标形成链表(虽然hash冲突，但是这时元素个数size小于阈值12(因为是存入第12个元素之前才判断size)，不会并没有满足扩容的两个条件，所以不会扩容)。后面15个值分散到数组的剩下15个位置，每个位置一个(这时元素的个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，即没有满足扩容的两个条件，所以也不会扩容)，前面12+15=27，所以在存入第28个值的时候才同时满足上面两个条件，这时才会发生扩容

# jdk8

# 扩容条件

jdk8不再像jdk7一个需要同时满足两个条件，jdk8只需要满足一个条件：

当存放新值(注意不是替换已有元素位置时)的时候，如果已有元素个数大于等于阈值(已有元素等于阈值，下一个存放必然触发扩容机制)

注：

  1. 扩容一定是放入新值的时候，该新值不是替换以前位置的情况下(说明：put("name","zhangsan")，而map中原有数据("name","lisi")，这个存放过程就是替换一个原有值的过程，不是新增值，不会扩容)
  2. 扩容数据存放后(即先存放进去再扩容)，判断存放后当前的size，如果大于阈值则直接进行扩容
# 背景知识

​ Java7中HashMap底层采用的是Entry对数组，而每一个Entry对又向下延伸是一个链表，在链表上的每一个Entry对不仅存储着自己的key/value值，还存了前一个和后一个Entry对的地址。

Java8中的HashMap底层结构有一定的变化，还是使用的数组，但是数组的对象以前是Entry对，现在换成了Node对象（可以理解是Entry对，结构一样，存储时也会存key/value键值对、前一个和后一个Node的地址），以前所有的Entry向下延伸都是链表，Java8变成链表和红黑树的组合，数据少量存入的时候优先还是链表，当链表长度大于等于8，且总数据量大于等于64的时候，链表就会转化成红黑树，所以你会看到Java8的HashMap的数据存储是链表+红黑树的组合，如果数据量小于64则只有链表，如果数据量大于等于64，且某一个数组下标数据量大于等于8，那么该处即为红黑树。

# 源码分析

在jdk7中，初始化HashMap()时就会对其进行初始化，而jdk8中new HashMap<>()并没有对其进行初始化，而是在put()方法中通过判断当前table是否等于null，如果为空则调用resize()方法来初始化

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
1
2
3
/**
     * Implements Map.put and related methods
     *
     * @param hash key值计算传来的下标
     * @param key
     * @param value
     * @param onlyIfAbsent true只是在值为空的时候存储数据，false都存储数据
     * @param evict
     * @return 返回被覆盖的值，如果没有覆盖则返回null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // 申明entry数组对象tab[]:当前Entry[]对象
        Node<K,V>[] tab;
        // 申明entry对象p:这里表示存放的单个节点
        Node<K,V> p;
        // n:为当前Entry对象长度 　　　　 // i:为当前存放对象节点的位置下标
        int n, i;
 
        /**
         * 流程判断
         * 1、如果当前Node数组(table)为空，则直接创建(通过resize()创建)，并将当前创建后的长度设置给n
         * 2、如果要存放对象所在位置的Node节点为空，则直接将对象存放位置创建新Node，并将值直接存入
         * 3、存放的Node数组不为空，且存放的下标节点Node不为空（该Node节点为链表的首节点）
         *   1）比较链表的首节点存放的对象和当前存放对象是否为同一个对象，如果是则直接覆盖并将原来的值返回
         *   2）如果不是分两种情况
         *      （1）存储处节点为红黑树node结构，调用方法putTreeVal()直接将数据插入
         *      （2）不是红黑树，则表示为链表，则进行遍历
         *          A.如果存入的链表下一个位置为空，则先将值直接存入，存入后检查当前存入位置是否已经大于等于链表的第8个位置
         *              a.如果大于,调用treeifyBin方法判断是扩容 还是 需要将该链表转红黑树（大于等于8且总数据量大于64则转红黑色，否则对数组进行扩容）
         *              b.当前存入位置链表长度没有大于等于8，则存入成功，终端循环操作。
         *          B.如果存入链表的下一个位置有值，且该值和存入对象“一样”，则直接覆盖，并将原来的值返回
         *          上面AB两种情况执行完成后，判断返回的原对象是否为空，如果不为空，则将原对象的原始value返回
         * 上面123三种情况下，如果没有覆盖原值，则表示新增存入数据，存储数据完成后，size+1,然后判断当前数据量是否大于阈值，
         * 如果大于阈值，则进行扩容。
         */
        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;
        // 如果不是替换数据存入，而是新增位置存入后，则将map的size进行加1，然后判断容量是否超过阈值，超过则扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

treeifyBin()方法判断是扩容还是将当前链表转为红黑树

从指定hash位置处的链表nodes头部开始，全部替换成红黑树结构。

除非整个数组对象（Map集合）数据量(不是size，size是key个数即元素个数，而是table数组的长度。table 的长度不一定等于size，因为可能发生hash冲突会有的table[i]是链表结构，实际的元素个数是大于table的长度的)很小（小于64），该情况下则通过resize()对这个Map进行扩容，而代替将链表转红黑树的操作。

    final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
        int n, index; HashMap.Node<K,V> e;
        // 如果Map为空或者当前存入数据n（可以理解为map的size()）的数量小于64便进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 如果size()大于64则将正在存入的该值所在链表转化成红黑树
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            HashMap.TreeNode<K,V> hd = null, tl = null;
            do {
                HashMap.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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 总结

  1. jdk8在新增数据存入后才进行扩容

  2. 扩容发生的条件有两个，满足任意一个都会扩容

    • 存入数据后，size>threshold
    • 存入数据到某一条链表上，此时链表的长度大于8了，且table数组的length小于64

  3. 注意jdk7、8区别：

    jdk7是在存入数据前进行判断是否扩容，而jdk8是在存入数据后再进行扩容的判断

# 补充

这里补充一下JDK8关于红黑树和链表的知识：

第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取“与”来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个（代码是>=7,从0开始，及第8个开始判断是否转化成红黑树），如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。

# HashMap的put方法

  1. 根据key通过哈希算法和与运算得出数组下标
  2. 如果该数组下标元素为空，则将key和value封装为Entry对象(jdk1.7是Entry对象，1.8是Node对象)，并放入该位置
  3. 如果数组下标位置元素不为空，则要分情况
    • 如果在jdk1.7中，会首先判断是否需要扩容，如果要扩容就先进行扩容，如果不需要则生成Entry对象，并用头插法添加到当前链表中。
    • 如果是在jdk1.8中，则会先判断当前位置上的TreeNode类型，看是红黑树还是链表Node
      • 如果是红黑树TreeNode，则会将key和value封装为一个红黑树结点并添加到红黑树中去，在这个过程中会判断红黑树中是否存在当前key，如果存在则更新value
      • 如果此位置上的Node对象时链表结点，则将key和value封装为一个Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，遍历的过程中会判断是否存在当前key，如果存在则更新其value，否则遍历完链表后，将新的Node插入到链表，插入后会看当前链表的结点个数，如果大于8，将会将这条链表转为红黑树
      • 将key和value封装为Node插入到链表或红黑树以后，再判断是否需要扩容，如果需要扩容，就结束put方法

# HashMap，LinkedHashMap，TreeMap有什么区别？它们的使用场景

  • HashMap参考上面的问题；主要用于在Map中插入、删除和定位元素时

  • LinkedHashMap保存了记录的插入顺序，在使用Iterator遍历时，先取到的记录肯定是先插入的；遍历比HashMap慢；

    主要用在需要按自然顺序或自定义顺序遍历键值的情况下

  • TreeMap实现了SortMap接口，能够把它保存的记录根据key排序(默认按键值升序排序，也可以指定排序的比较器)；

    主要用在需要输出和输入顺序相同的情况下

# HashMap和Hashtable有什么区别

  • HashMap是线程不安全的；Hashtable是线程安全的；
  • 由于是线程安全的，所以Hashtable的效率低于HashMap
  • HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而Hashtable不允许；
  • HashMap默认初始化table的大小为16，扩容时扩大为两倍；Hashtable初始化为11，扩容为两倍+1
  • HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

# Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？

  1. ConcurrentHashMap 类（是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。
    • HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；
    • 而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了CAS（无锁算法）+ synchronized。

# HashMap & ConcurrentHashMap 的区别？

除了加锁，原理上无太大区别。

另外，HashMap 的键值对允许有null，但是ConCurrentHashMap 都不允许。

# ConcurrentHashMap

在jdk1.7是 分段的数组+链表 (opens new window) ，jdk1.8的时候跟HashMap1.8的时候一样都是基于数组+链表 (opens new window)/红黑树 (opens new window)。

ConcurrentHashMap是线程安全的

  1. 在jdk1.7的时候是使用分段锁segment，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
  2. 在jdk1.8的时候摒弃了 Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。synchronized只锁定当前链表或红黑二叉树的首节点

# 为什么 ConcurrentHashMap 比 HashTable 效率要高？

  • HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；
  • ConcurrentHashMap
    • JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
    • JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

# 针对 ConcurrentHashMap 锁机制具体分析（JDK 1.7 VS JDK 1.8）？

JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。 ①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶； ②、HashEntry 用来封装映射表的键-值对； ③、每个桶是由若干个 HashEntry 对象链接起来的链表。

image-20220319200113437

JDK 1.8中，采用Node + CAS + Synchronized来保证并发安全。取消类 Segment，直接用 table 数组存储键值对；当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD(8)时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

image-20220319200054701

image

# ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

  • 粒度降低了；
  • JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，更加自然。
  • 在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

# ConcurrentHashMap简单介绍？

  1. 重要的常量：

    private transient volatile int sizeCtl; 当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容； 当为 0 时，表示 table 还没有初始化； 当为其他正数时，表示初始化或者下一次进行扩容的大小。

  2. 数据结构：

    • Node是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据；
    • TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储结构，用于红黑树中存储数据；
    • TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制。

  3. 存储对象时（put() 方法）：

    1. 如果没有初始化，就调用 initTable() 方法来进行初始化;
    2. 如果没有 hash 冲突就直接 CAS 无锁插入；
    3. 如果需要扩容，就先进行扩容；
    4. 如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；
    5. 如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一次进入循环；
    6. 如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。

  4. 扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。 helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。

  5. 获取对象时（get()方法）：

    1. 计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；
    2. 如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；
    3. 以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

# 17.ConcurrentHashMap的并发度是什么？

程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）

在 GitHub 上编辑此页 (opens new window)
最后更新: 2022/10/04, 16:10:00
纲要
操作系统

← 操作系统→

Theme by Vdoing | Copyright © 2022-2024 zdk | notes
湘ICP备2022001117号-1
川公网安备 51142102511562号
提供加速服务