Chiaki's Blog

【面试】Java集合

 Tech  3203  7 分钟

#简介

Java的集合包括单列集合（java.util.Collection）和双列集合（java.util.Map）。其中单列集合包括List和Set接口，双列集合主要是Map接口。List有序、有索引、允许重复；Set不允许重复、没有索引；Map使用key-value形式，key不允许重复。

#ArrayList、LinkedList与Vector

底层实现：ArrayList底层基于Object数组实现，LinkedList底层基于双向链表（JDK6及之前是循环链表，JDK7及以后取消了循环）实现，Vector底层基于数组实现。

线程安全：ArrayList和LinkedList不保证线程安全，Vector中采用synchronized关键字修饰，线程安全。

查找：ArrayList查找快，复杂度为O(1)，LinkedList查找慢，复杂度为O(n)。

插入和删除：ArrayList增删慢，默认在末尾追加（O(1)），指定位置插入和删除时复杂度为O(n - i)；LinkedList增删快，可以在头部或尾部插入，复杂度为O(1)，删除操作不受元素位置影响，复杂度O(1)，在指定位置插入时复杂度近似为O(n)。

内存空间占用：ArrayList空间浪费体现在list的结尾会预留一定的容量空间，LinkedList的空间花费体现在其每个元素都需要消耗比ArrayList更多的空间（存放前驱和后继数据）。

扩容：ArrayList有无参构造和带参构造两种方式。采用无参构造时会建立一个数组，JDK7及以前该数组的容量为10，即默认容量，JDK8及以后该数组为一个空数组，当第一次添加数据时才会扩容至默认容量10。采用带参构造时，会建立指定容量的数组。当数组中的容量大于初始容量时，就会进行扩容，扩容为原来的1.5倍，即new = old + (old >> 1)。扩容时会以新的容量建一个原数组的拷贝，修改原数组指向新数组，原数组会被GC回收。Vector中采用synchronized修饰，线程安全，但是同步操作会耗费大量的时间。Vector的初始容量为10，扩容时扩充为原来的2倍。

#HashMap和HashTable

底层实现：HashMap底层采用哈希表实现，JDK8前哈希表由数组+链表实现，JDK8及以后哈希表由数组+链表/红黑树实现，当链表结点超过8个时会转化为红黑树，以减少搜索时间。HashTable底层是哈希表实现，哈希表由数组+链表实现。

线程安全：HashMap线程不安全，并发下的rehash会造成元素之间形成循环链表，同时并发下的put操作可能会导致元素丢失；HashTable线程安全，内部方法经过synchronized修饰。

效率：HashMap比HashTable效率高一点。

对null key和null value的支持：HashMap支持null key和null value；HashTable不支持null key。

扩容：HashMap无参构造时，默认初始化容量为16，之后每次扩容时容量变为原来的2倍；HashMap带参构造时会将指定容量扩充至与其最接近的2的幂次方大小，之后每次扩容变为原来的2倍。HashTable无参构造时默认初始化容量为11，带参构造时初始化为指定容量，之后每次扩容方式为2n+1。

#HashMap源码相关

#HashMap底层实现

HashMap底层采用哈希表实现，JDK8以前，哈希表由数组和链表实现，即链表散列。HashMap通过key的hashCode经过扰动处理（hash()方法）后得到hash值，然后通过hash & (n - 1)确定元素的存放位置。若当前位置存在元素，先判断已有元素与当前元素的key值是否相同，若相同则直接覆盖，若不相同则采用拉链法解决哈希冲突。JDK8及之后，在解决哈希冲突时有了很大改进，链表长度大于8时，链表会转换为红黑树，以减少搜索时间。

红黑树的特点：

  • 结点是黑色或者红色；
  • 根节点是黑色；
  • 叶子节点都是黑色空结点；
  • 颜色为黑的结点的子节点的颜色一定为红；
  • 从任一结点到其每个叶子结点的所有路径都包含相同数目的黑色结点。

RB-Tree和AVL-Tree的区别？

  • 查询：RB-Tree稍逊于AVL-Tree，因为RB-Tree不是严格平衡的，而AVL-Tree高度平衡；
  • 插入：都只需要最多2次旋转来维持平衡，复杂度为O(1)；
  • 删除：RB-Tree最多需要3次旋转来保持平衡，复杂度为O(1)；AVL-Tree需要维护被删除结点到根结点路径上所有结点的平衡，复杂度为O(logN)。因此在结点删除并保持平衡上来看，RB-Tree优于AVL-Tree。
  • 空间开销：RB-Tree空间开销小，维护成本低；AVL-Tree空间开销大，维护成本高。
  • 选择：插入删除多时选择RB-Tree，查询多选择AVL-Tree。
#HashMap的默认参数

默认初始容量为16：1 << 4

最大容量为2^30：1 << 30

默认负载因子为0.75：当容量 * 负载因子 < 保存节点个数时发生扩容，默认情况下当元素个数超过12时，会将HashMap的容量扩充为16 * 2 = 32，然后进行rehash操作。

树化阈值为8：根据泊松分布计算而来，一个桶中结点到达8个的概率为0.0000006，几乎不可能。当一个桶中结点数目超过8时，链表转换为红黑树。

链表化阈值为6：当红黑树的结点个数小于6时，红黑树变为链表。6和8之间有个差值7可以防止链表和树频繁转换。

链表树化的HashMap最小容量为64：哈希表容量小于64时，很可能是因为容量过小导致的哈希冲突，此时进行一次扩容就能基本解决冲突问题。

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

为了能够让HashMap存取高效要尽量避免哈希冲突。哈希值的范围为-2^31 ~ 2^31 - 1，这样大的范围难以在内存中存放，因此考虑将哈希值对HasMap的容量取模，即hash % n，用取模后的结果来确定元素的存放位置。但是，我们知道HashMap中确定元素存放位置时采用的操作是hash & (n - 1)。两种方法看似不一样，但我们忽略了HashMap的一个特点，即HashMap的容量大小始终是2的幂次方。在这个条件下hash % n等价于hash & (n - 1)。同时，&操作相对于%能够提高运算效率。

#ConcurrentHashMap与HashTable

ConcurrentHashMap和HashTable都是线程安全的，但二者实现线程安全的方式不同。

JDK8之前，ConcurrentHashMap的底层采用分段数组+链表实现。在线程安全的实现方式上，ConcurrentHashMap采用分段锁实现，将ConcurrentHashMap分为若干个Segment（继承自ReentrantLock，默认为16段）。每一段都是一个HashMap，用数组来保存。当需要对某一个键值对进行加锁时，只需要对该键值对所在的分段加锁即可，多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高。JDK8及之后摒弃了Segment的概念，使用结点数组+链表/红黑树来实现底层结构。同时采用CAS操作和synchronized来完成并发控制，加锁时只对结点数组的头结点进行加锁。

HashTable底层采用数组+链表来实现，内部方法采用synchronized修饰，对整个数组加锁，效率低。

#线程安全的List、Set和Map

#线程安全的List

  • Vector：内部使用synchronized关键字修饰方法

  • CopyOnWriteArrayList：写入时（增删元素）会复制原来的数组，在操作完成后用新数组替换原数组，效率十分低下。读写分离，写时加锁，读不加锁，因此读操作比Vector快。

    CopyOnWriteArrayList<Object> objects = new CopyOnWriteArrayList<>();

  • Collections.synchronizedList()方法：集合类的同步方法

    Collections.synchronizedList(new ArrayList<>());
#线程安全的Set
  • CopyOnWriteArraySet
  • Collections.synchronizedSet()
#线程安全的Map
  • HashTable
  • ConcurrentHashMap
  • Collections.synchronizedMap()