集合框架底层数据结构

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. 如果除数是2x12^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 属性维护红黑树的根结点,因为红黑树在旋转的时候,根结点可能会被它原来的子节点替换掉,在这个时间点,如果有其他线程要写这棵红黑树就会发生线程不安全问题,所以在 ConcurrentHashMapTreeBin 通过 waiter 属性维护当前使用这棵红黑树的线程,来防止其他线程的进入。

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

参考文章:JavaGuide