ArrayList

概述

实现接口图

  • RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。
  • ArrayList是可以动态增长和缩减的索引序列，它是基于数组实现的List类。
  • ArrayList也可以储存null值

源码分析

属性

构造方法

核心方法

add方法

1
2
3
4
5
6
7
8
9
10
// 将指定的元素追加到此列表的末尾。
// 形参:
// e -要添加到此列表的元素
// 返回值:
// True(由 Collection.add）
  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

查看ensureCapacityInternal方法

1
2
3
private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }

查看ensureExplicitCapacity

1
2
3
4
5
6
7
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
// 从上面的代码可以看出，以无参构建ArrayList的时候，刚开始数组的大小是为0的，在第一次添加元素的时候会创建一个长度为10的数组，并将该元素赋值到数组的第一个位置
1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
      modCount++; //修改的次数可以忽略
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }

查看grow方法：上面我们传递的minCapacity是插入数据后的大小，当minCapacity - elementData.length > 0也就是当前的ArrayList的大小不足了，下面的grow肯定就是扩容的关键代码

扩容代码关键点

  • ArrayList有2个关键的属性：elementData数组，int的size;size是ArrayList储存数据的数量。
  • 当我们以无参构造ArrayList的时候分配给elementData长度为0，第 1 次添加元素，会创建一个长度为10的数组，并将该元素赋值到数组的第一个位置
  • 扩容的时间发生在插入数据后元素的大小大于当前ArrayList的大小的时候
  • 先扩容到旧容量的1.5倍看是否够用
  • 够用以该容量生成新的数组，数据拷贝到新数组里面，然后让elementData指向新数组
  • 扩容1.5倍倍后如果不够用，就扩大到插入元素后的大小；扩容1.5倍倍够用的话（或者在不够用的情况下，扩大到插入后的情况）就看看这个容量是否超过了规定的最大容量，如果是就调用 hugeCapacity方法，该方法中会判断插入元素数组的大小是否超过int的最大值，如果是抛出异常，不是就判断插入元素后的大小是否超出了ArrayList规定的最大值，如果不是就让它为规定的最大数，否则为int的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
// 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
// 形参: minCapacity -所需的最小容量
 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
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;//因为有保留了8个字符
    }
// 要分配的数组的最大大小。有些虚拟机在数组中保留一些头字。尝试分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过虚拟机限制
// private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 移除此列表中指定位置的元素。将所有后续元素向左移动(从它们的索引中减去1)。
// 形参:
// 指数 -要删除的元素的索引
// 返回值:
// 从列表中删除的元素
// 抛出:
// IndexOutOfBoundsException -如果索引超出范围(index < 0 || index >= size())
public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
  • ArrayList 中可以存储任何类型的对象，包括 null 值。
  • 以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10
  • size() 方法时，它会遍历列表并计算元素的个数，然后将这个计数值作为结果返回；

线程不安全Demo分析

1
2
3
4
5
6
7
8
9
10
11
public class ArrayListDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            int finalI = i;
            new Thread(() -> list.add("Element " + finalI)).start();
        }
        System.out.println("预期长度为10"+list.size());
        System.out.println("list:"+list);
    }
}

  1. 并发修改：由于有多个线程尝试同时修改 ArrayList，这会导致并发修改的问题。
  2. 数组扩容：当 ArrayList 达到其初始容量时，它需要进行扩容。扩容过程涉及到创建一个新的数组，并将旧数组的元素复制到新数组中。如果多个线程同时触发了扩容，可能会导致数据丢失或不一致。
  3. 快速失败迭代器：ArrayList 提供的迭代器是快速失败的，意味着在迭代过程中如果检测到列表被修改了（除了迭代器自身的 remove 方法），迭代器会立即抛出 ConcurrentModificationException。
  4. **潜在的**IndexOutOfBoundsException：由于 ArrayList 使用数组存储数据，当多个线程同时修改数组大小时，可能会导致数组下标越界异常。

解决方法

使用Collections.synchronizedList(List list) 包装的 ArrayList 或者 CopyOnWriteArrayList。

1
private static final List<String> list = Collections.synchronizedList(new ArrayList<>());

LinkedList

概述

  • LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。
  • LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口，能对它进行队列操作。
    LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
    LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
    LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
    LinkedList 是非同步的。
  • Deque接口：有队列的各种特性，
  • 没有RandomAccess：那么就推荐使用iterator

源码分析

属性

构造器

迭代器

LinkedList 的遍历的核心就是它的迭代器的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 双向迭代器
private class ListItr implements ListIterator<E> {
    // 表示上一次调用 next() 或 previous() 方法时经过的节点；
    private Node<E> lastReturned;
    // 表示下一个要遍历的节点；
    private Node<E> next;
    // 表示下一个要遍历的节点的下标，也就是当前节点的后继节点的下标；
    private int nextIndex;
    // 表示当前遍历期望的修改计数值，用于和 LinkedList 的 modCount 比较，判断链表是否被其他线程修改过。
    private int expectedModCount = modCount;
    …………
}

下面我们对迭代器 ListItr 中的核心方法进行详细介绍。

我们先来看下从头到尾方向的迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 判断还有没有下一个节点
public boolean hasNext() {
    // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
    return nextIndex < size;
}
// 获取下一个节点
public E next() {
    // 检查在迭代过程中链表是否被修改过
    checkForComodification();
    // 判断是否还有下一个节点可以遍历，如果没有则抛出 NoSuchElementException 异常
    if (!hasNext())
        throw new NoSuchElementException();
    // 将 lastReturned 指向当前节点
    lastReturned = next;
    // 将 next 指向下一个节点
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

再来看一下从尾到头方向的迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 判断是否还有前一个节点
public boolean hasPrevious() {
    return nextIndex > 0;
}

// 获取前一个节点
public E previous() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果没有前一个节点，则抛出异常
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 将 lastReturned 和 next 指针指向上一个节点
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

如果需要删除或插入元素，也可以使用迭代器进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add(null);
list.add("banana");

//  Collection 接口的 removeIf 方法底层依然是基于迭代器
list.removeIf(Objects::isNull);

for (String fruit : list) {
    System.out.println(fruit);
}

迭代器对应的移除元素的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 从列表中删除上次被返回的元素
public void remove() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果上次返回的节点为空，则抛出异常
    if (lastReturned == null)
        throw new IllegalStateException();

    // 获取当前节点的下一个节点
    Node<E> lastNext = lastReturned.next;
    // 从链表中删除上次返回的节点
    unlink(lastReturned);
    // 修改指针
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    // 将上次返回的节点引用置为 null，方便 GC 回收
    lastReturned = null;
    expectedModCount++;
}

总结

1）linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。 2）能存储null值 3）跟arrayList相比较，就真正的知道了，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好 4）从源码中看，它不存在容量不足的情况 5）linkedList不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值。 6）linkedList不光能当链表，还能当队列使用，这个就是因为实现了Deque接口。

HashMap

概述

+ [Java 8系列之重新认识HashMap](https://tech.meituan.com/2016/06/24/java-hashmap.html)（这个看完可以不用看下面的大部分内容） + HashMap中的key最好使用不可变对象，否则新值重写计算的hashcode和之前的值可能不一样，从而导致查询失败。

Java面试题：聊聊HashMap扩容的流程_哔哩哔哩_bilibili

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

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // hashCode() 和 equals() 基于 name 和 age
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public String toString() {
        return "Person{" + "name='" + name + '\'' + ", age=" + age + '}';
    }
}

public class Main {
    public static void main(String[] args) {
        Person person1 = new Person("Alice", 25);
      
        // 创建一个 HashMap，并将 person1 作为键
        HashMap<Person, String> map = new HashMap<>();
        map.put(person1, "Developer");

        // 查询时能正常获取值
        System.out.println("Before changing age: " + map.get(person1)); // 输出: Developer

        // 修改 person1 的 age
        person1.age = 26;

        // 再次查询时，由于 hashCode 改变，可能无法获取值;更改值后hash值发生了变化
        System.out.println("After changing age: " + map.get(person1)); // 输出: null

        // 打印 map 内容以验证
        System.out.println("Map content: " + map);
    }
}

  • HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
  • JDK1.8 之前 HashMap 由 数组+链表 组成的， JDK1.8 以后变成了数组加链表加红黑树
  • HashMap的数据结构和存储原理
    • 第一步：HashMap内部有一个entry的内部类，其中有四个属性，我们要存储一个值，则需要一个key和一个value，存到map中就会先将key和value保存在这个Entry类创建的对象中。
1
2
3
4
5
static class Entry<K,V> implements Map.Entry<K,V> {
     　　　　  final K key;    //就是我们说的map的key
      　　　　 V value;    //value值，这两个都不陌生
      　　　　 Entry<K,V> next;//指向下一个entry对象
      　　　　 int hash;//通过key算过来的你hashcode值。
  • Entry的物理模型图：
  • 第二步：构造好了entry对象，然后将该对象放入数组中
  • 大概的一个存放过程是：通过entry对象中的hash值来确定将该对象存放在数组中的哪个位置上，如果在这个位置上还有其他元素，则通过链表来存储这个元素。当然JDK1.8后会把链表变成红黑树
  • 通过key、value封装成一个entry对象，然后通过key的值来计算该entry的hash值，通过entry的hash值和数组的长度length来计算出entry放在数组中的哪个位置上面，每次存放都是将entry放在第一个位置，在这个过程中，就是通过hash值来确定将该对象存放在数组中的哪个位置上。
  • JDK1.8后的结构
  • 上图很形象的展示了HashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。

源码分析

属性

  • HashMap的实例有两个参数影响其性能。
    • 初始容量：哈希表中桶的数量
    • 加载因子：哈希表在其容量自动增加之前可以达到多满的一种尺度
  • 桶
    • 数组中每一个位置上都放有一个桶，每个桶里就是装一个链表，链表中可以有很多个元素(entry)，这就是桶的意思。也就相当于把元素都放在桶中。
  • 当哈希表中条目数超出了当前容量*加载因子(其实就是HashMap的实际容量)时，则对该哈希表进行rehash操作，将哈希表扩充至两倍的桶数。
  • loadFactor加载因子
    • 定义：loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity,这里的capacity是底层数组的大小，size：指的是哈希表中当前存储的键值对数量
    • loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0
    • 那么数组中存放的数据也就越稀，也就是可能数组中每个位置上就放一个元素。那有人说，就把loadFactor变为1最好吗，存的数据很多，但是这样会有一个问题，就是我们在通过key拿到我们的value时，是先通过key的hashcode值，找到对应数组中的位置，如果该位置中有很多元素，则需要通过equals来依次比较链表中的元素，拿到我们的value值，这样花费的性能就很高，如果能让数组上的每个位置尽量只有一个元素最好，我们就能直接得到value值了，所以有人又会说，那把loadFactor变得很小不就好了，但是如果变得太小，在数组中的位置就会太稀，也就是分散的太开
  • capacity
    • capacity译为容量代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16。
    • 一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。
  • size
    • size就是在该HashMap的实例中实际存储的元素的个数

构造器

  • 我们一般new HashMap()都是采用的无参构造，这个时候知识给负载因子赋值为0.75了，而没有给Node数组分配大小

put方法

1
2
3
4
5
6
7
8
// 将指定值与此映射中的指定键关联。如果映射以前包含键的映射，则替换旧值。
// 形参:
// 关键 -指定值要关联的关键字 价值 -与指定密钥关联的值
// 返回值:
// 与key关联的前一个值，如果没有key的映射，则为空。(null返回也可以表明映射先前将null与key关联。
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

putVal方法

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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // hash值不相等，即key不相等；为红黑树结点
        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;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}
  • HashMap并没有直接提供putVal接口给用户调用，而是提供的put函数，而put函数就是通过putVal来插入元素的。

扩容

  • threshold是所能容纳的key-value对极限；
  • threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

resize方法

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
78
79
80
81
82
83
84
85
86
87
88
89
90
final Node<K,V>[] resize() {
    // 当前table保存
    Node<K,V>[] oldTab = table;
    // 保存table大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存当前阈值 
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 之前table大小大于0
    if (oldCap > 0) {
        // 之前table大于最大容量
        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
    }
    // 之前阈值大于0
    else if (oldThr > 0)
        newCap = oldThr;
    // oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）
    else {         
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新阈值为0
    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"})
    // 初始化table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 之前的table已经初始化过
    if (oldTab != null) {
        // 复制元素，重新进行hash
        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;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash
                    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;
}

resize()
  • 进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

在resize前和resize后的元素布局如下:

ConcurrentHashMap

概述

+ 　在ConcurrentHashMap中通过一个Node[]数组来保存添加到map中的键值对，而在同一个数组位置是通过链表和红黑树的形式来保存的。但是这个数组只有在第一次添加元素的时候才会初始化，否则只是初始化一个ConcurrentHashMap对象的话，只是设定了一个sizeCtl变量，这个变量用来判断对象的一些状态和是否需要扩容，后面会详细解释。 + 第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取与来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个以上，如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64了的话，在会将该节点的链表转换成树。 + 　通过扩容数组的方式来把这些节点给分散开。然后将这些元素复制到扩容后的新的数组中，同一个链表中的元素通过hash值的数组长度位来区分，是还是放在原来的位置还是放到扩容的长度的相同位置去 。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。 + 　取元素的时候，相对来说比较简单，通过计算hash来确定该元素在数组的哪个位置，然后在通过遍历链表或树来判断key和key的hash，取出value值。 + 其是作为线程安全的 HashMap + JDK1.8储存结构![](https://cdn.nlark.com/yuque/0/2024/png/28066124/1714196599884-0630fcf6-2922-491b-b5f8-7ed2f6bfc225.png) + ![](https://cdn.nlark.com/yuque/0/2024/png/28066124/1714196639191-71e9db80-da55-4d9b-a861-eab07bb5f9c3.png)

源码分析

初始化 initTable 
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
/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        //　如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。
        if ((sc = sizeCtl) < 0)
            // 让出 CPU 使用权
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

从源码中可以发现 ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl （sizeControl 的缩写），它的值决定着当前的初始化状态。

  1. -1 说明正在初始化，其他线程需要自旋等待
  2. -N 说明 table 正在进行扩容，高 16 位表示扩容的标识戳，低 16 位减 1 为正在进行扩容的线程数
  3. 0 表示 table 初始化大小，如果 table 没有初始化

  4. 0 表示 table 扩容的阈值，如果 table 已经初始化。

put

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
public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key 和 value 不能为空
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        // f = 目标位置元素
        Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值
        if (tab == null || (n = tab.length) == 0)
            // 数组桶为空，初始化数组桶（自旋+CAS)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                break;  // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 使用 synchronized 加锁加入节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 说明是链表
                    if (fh >= 0) {
                        binCount = 1;
                        // 循环加入新的或者覆盖节点
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 红黑树
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

  • 根据 key 计算出 hashcode 。
  • 判断是否需要进行初始化。
  • 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
  • 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  • 如果都不满足，则利用 synchronized 锁写入数据。
  • 如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥64 时才会将链表转换为红黑树。
  • put操作中CAS的使用：
    • 从源码上来看，我们能够发现，ConcurrentHashMap 和 HashMap 的元素插入操作流程是非常相似的。最大的几个不同点在于：

1.如果槽是空的，那么添加元素的时候，ConcurrentHashMap 是通过 CAS操作来完成的。HashMap则是直接赋值。对比图如下：

2.如果槽不是空的，在对槽中元素（链表/红黑树）进行遍历的时候。<font style="color:rgb(199, 37, 78);background-color:rgb(249, 242, 244);">ConcurrentHashMap</font> 有通过 <font style="color:rgb(199, 37, 78);background-color:rgb(249, 242, 244);">synchronized</font> 将整个<font style="color:rgb(199, 37, 78);background-color:rgb(249, 242, 244);">Node</font>节点给加锁（也就是所谓的分段锁）。<font style="color:rgb(199, 37, 78);background-color:rgb(249, 242, 244);">HashMap</font>则没有。

get

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
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // key 所在的 hash 位置
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果指定位置元素存在，头结点hash值相同
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                // key hash 值相等，key值相同，直接返回元素 value
                return e.val;
        }
        else if (eh < 0)
            // 头结点hash值小于0，说明正在扩容或者是红黑树，find查找
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            // 是链表，遍历查找
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

总结一下 get 过程：

  1. 根据 hash 值计算位置。
  2. 查找到指定位置，如果头节点就是要找的，直接返回它的 value.
  3. 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
  4. 如果是链表，遍历查找之。

总结：

总的来说 ConcurrentHashMap 在 Java8 中相对于 Java7 来说变化还是挺大的，

Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制

  • ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps)上，不允许null值的出现的主要原因是他可能会在并发的情况下带来难以容忍的二义性。如果在HashMap等非并发容器中，你可以通过contains方法来判断，这个key是究竟不存在，还是本来就是null。但是在并发容器中，如果允许空值的存在的话，你就没法判断真正的情况

HashSet

概述

  • 无序性：HashSet 不保证元素的顺序，它不按照元素的插入顺序或者排序顺序进行存储。因此，当你迭代 HashSet 时，元素的顺序是不确定的。
  • 唯一性：HashSet 中不允许重复的元素。如果你尝试将一个已经存在的元素添加到 HashSet 中，添加操作将会被忽略，不会有任何效果。
  • 允许 null 元素：HashSet 允许存储 null 元素。你可以将 null 添加到 HashSet 中，并且只能添加一个 null 元素，因为它不允许重复。
  • 线程不安全：HashSet 是线程不安全的。如果需要在多线程环境中使用，应该使用 Collections.synchronizedSet 包装 HashSet 或者使用 ConcurrentHashMap 作为其底层实现。
  • 不保证元素的唯一性：虽然 HashSet 不允许集合中直接出现重复的元素，但是它依赖于对象的 equals() 和 hashCode() 方法来确定对象的唯一性。如果集合中的两个对象通过 equals() 方法比较是相等的，但它们的 hashCode() 返回不同的值，HashSet 仍然会认为它们是不同的元素，并允许它们同时存在于集合中。不过，这会降低性能，因为 HashSet 需要使用 equals() 方法来比较对象。
  • 对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素
  • 添加值得时候会先获取对象的hashCode方法，如果hashCode 方法返回的值一致，则再调用equals方法判断是否一致，如果不一致才add元素。

源码分析

属性

  • HashSet是基于HashMap实现的，HashMap是key和value结构，Hashset中的vaule是一个虚拟值

构造器

方法

  • add方法保证元素不重复的关键就是map中添加key保证key不重复
1
2
if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
  • 这里先比较的是Node节点的hash值也就是key的hashcode，然后就是(k = p.key) == key || (key != null && key.equals(k)
  • 当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。