集合框架底层数据结构

java-collection-hierarchy

  • List
    • ArrayList：Object[]数组
    • Vector：Object[]数组，保证线程安全
    • LinkedList：双向链表
  • Set
    • HashSet「无序、唯一」：HashMap
    • LinkedHashSet：LinkedHashMap
    • TreeSet「无序、唯一」：红黑树
  • Queue
    • PriorityQueue：Object[]数组实现二叉堆
    • ArrayQueue：Object[]数组+双指针
  • Map
    • HashMap：数组➕链表或者红黑树「链表是为了解决哈希冲突」。当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
    • LinkedHashMap：数组➕链表或者红黑树
    • Hashtable：数组➕链表
    • TreeMap：红黑树

ArrayList与LinkedList

  • 线程安全：都不保证线程安全

  • 底层数据结构：前者使用Object[]，后者使用双向链表

  • 快速随机访问：LinkedList不支持，ArrayList支持

  • 内存空间占用：ArrayList 的空间浪费主要体现在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据

ArrayList扩容机制

以无参数构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。

扩容是在通过add()添加元素时，发现数组满的时候进行扩容的。

1
2
3
4
5
6
7
8
9
//判断是否需要扩容
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          //调用grow方法进行扩容，调用此方法代表已经开始扩容了
          grow(minCapacity);
  }

通过源码可以看到grow方法是扩容的关键。

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容1.5倍
  if (newCapacity - minCapacity < 0) {
    newCapacity = minCapacity; //如果不够大，直接赋值
  }
  if (newCapacity - MAX_ARRAY_SIZE > 0) {
    newCapacity = hugeCapacity(minCapacity); //更新最大容量
  }
  elementData = Arrays.copyOf(elementData, newCapacity);
}

可以明显看到，每次扩容后容量都会变为原来的1.5倍左右。

无序性和不可重复性

  • 无序性：无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
  • 不可重复性：添加的元素按照equals()判断时，返回false。

比较三个Set的异同

  • 都能保证元素唯一，并且都不是线程安全的
  • HashSet的底层数据结构是HashMap；LinkedHashSet的底层数据结构是链表和哈希表，元素的插入和取出顺序满足FIFO；TreeSet底层数据结构是红黑树
  • HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景

HashMap

  • 线程是否安全：非线程安全。主要原因在于并发下的Rehash会造成元素之间形成一个循环列表。虽然在1.8之后解决了这个问题，但还是会造成其他问题比如数据丢失。并发环境下推荐使用ConcurrentHashMap
  • 对Null的支持：可以存储null的key和value，但null作为键只能有一个，null作为值可以有多个
  • 初始容量大小和扩容
    • 若不指定容量，默认初始化大小为16。之后每次扩容，容量变为原来的2倍
    • 如果给定了容量初始值，会扩充为2的幂次方大小
  • 底层数据结构：当链表长度大于阈值「默认为8」时，将链表转化为红黑树（若当前数组的长度小于64，会进行数组扩容）

为什么HashMap的长度是2的幂次方

  1. hash值在用之前要对数组的长度进行取模运算。得到的余数也就是对应的数组下标，这个下标的计算方式是(n-1)&hash
  2. 如果除数是2x−12^x-1这种形式，与运算等价于取模。
  3. 与运算效率更高

HashMap的遍历方式

1
2
3
4
5
6
7
8
9
10
HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(2, 1);
        hashMap.put(3, 2);
        hashMap.put(4, 3);
        hashMap.put(5, 4);
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            int x = entry.getKey();
            int y = entry.getValue();
            System.out.println(x + " " + y);
        }

ConcurrentHashMap

  • 底层数据结构：数组+链表
  • 实现线程安全的方式：用 Node 数组 + 链表 + 红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。

java8_concurrenthashmap

如何实现线程安全

1
2
3
4
5
6
7
8
9
10
11
static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    // values for lockState
    static final int WRITER = 1; // set while holding write lock
    static final int WAITER = 2; // set when waiting for write lock
    static final int READER = 4; // increment value for setting read lock
...
}

数据结构跟HashMap的结构类似，数组➕链表或者红黑树。当链表长度超过一定阈值时将链表转换为红黑树。

TreeNode 是存储红黑树节点，被 TreeBin 包装。TreeBin 通过 root 属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 ConcurrentHashMap 中 TreeBin 通过 waiter 属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。

采用Node➕CAS➕synchronized来保证并发安全。synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，就不会影响其他Node的读写，效率大幅提升。

参考文章：JavaGuide