1. 概述

容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。

Collection

image-20210914185116246

1. Set(无序的、不可重复的)

  • TreeSet(有序,唯一,不能存储null): 基于红黑树(自平衡的排序二叉树)实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为 O(logN)。
  • HashSet(无序,唯一,可以存储一个null):基于HashMap实现,支持快速查找,底层采用HashMap来保存元素,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
  • LinkedHashSet(可以存储一个null):具有 HashSet 的查找效率,并且内部使用双向链表维护元素的插入顺序。是 HashSet 的子类,并且其内部是通过 LinkedHashMap 来实现的

2. List(有序的、可重复的,可以存储多个null值)

  • ArrayList:基于动态数组Object[]实现,支持随机访问,线程不安全。
  • Vector:和 ArrayList 类似Object[]实现,但它是线程安全的。
  • LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列和双向队列。

java.util.Arrays.asList() 可以把数组类型转换为 List 类型。

public static <T> List<T> asList(T... a)
/*
注意的是 asList() 的参数为泛型的变长参数,不能使用基本类型数组作为参数,只能使用相应的包装类型数组。
*/

3. Queue(有序的、可重复的)

  • LinkedList:可以用它来实现双向队列。
  • PriorityQueue:基于堆结构实现,可以用它来实现优先队列。

Map

map

  • TreeMap:基于红黑树实现。
  • HashMap
  • HashTable
  • LinkedHashMap:继承自 HashMap,使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序。

HashMap分析

  1. JDK1.8之前
    JDK1.8之前 HashMap 底层是 数组和链表 结合在一起使用也就是链表散列。
    HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

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

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组,总是2的幂次倍
    transient Node<k,v>[] table;
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数,注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;
    // 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
}
  • loadFactor 加载因子
    loadFactor 加载因子是控制数组存放数据的疏密程度,loadFactor 越趋近于 1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于 0,数组中存放的数据(entry)也就越少,也就越稀疏。

    loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

    给定的默认容量为 16,负载因子为 0.75。Map 在使用过程中不断的往里面存放数据,当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容,而扩容这个过程涉及到 rehash、复制数据等操作,所以非常消耗性能。

  • threshold
    threshold = capacity * loadFactor,当 Size>=threshold的时候,那么就要考虑对数组的扩增了,也就是说,这个的意思就是 衡量数组是否需要扩增的一个标准。

2. 疑难点

hashCode()equals() 的相关规定:

  1. 如果两个对象相等,则 hashcode 一定也是相同的
  2. 两个对象相等,对两个 equals() 方法返回 true
  3. 两个对象有相同的 hashcode 值,它们也不一定是相等的
  4. equals() 方法被覆盖过,则 hashCode() 方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode(),则该 class 的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

HashMap和HashTable的区别

  1. 线程是否安全:HashMap 是非线程安全的,Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。
  2. 效率:因为线程安全的问题,HashMap 要比 Hashtable 效率高一点,Hashtable基本被淘汰
  3. 对 Null key 和 Null value 的支持: HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;Hashtable 不允许有 null 键和 null 值,否则会抛出 NullPointerException。
  4. 初始容量大小和每次扩充容量大小的不同 : ① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小。
  5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

ConcurrentHashMap 和 Hashtable 的区别

主要体现在实现线程安全的方式上不同

  • JDK1.8 ConcurrentHashMap 采用的数据结构跟 HashMap1.8 的结构一样,数组+链表/红黑二叉树.Hashtable的底层数据结构类似都是采用 数组+链表的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
  • ConcurrentHashMap采用 CAS 和 synchronized 来保证并发安全,synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍

3. 集合的线程安全

ArrayList线程安全

故障现象:java.util.ConcurrentModificationException

//1
List<String> synList = Collections.synchronizedList(new ArrayList<>());
//2高频
List<String> list = new CopyOnWriteArrayList<>();
//3
List<String> list = new Vector<>();

CopyOnWriteArrayList:
写操作在一个复制的数组上进行(容量+1),读操作还是在原始数组中进行,读写分离,互不影响。
写操作需要加锁,防止并发写入时导致写入数据丢失。
写操作结束之后需要把原始数组指向新的复制数组。

HashSet线程安全

//1
List<String> synSet = Collections.synchronizedSet(new HashSet<>());
//2,底层直接new CopyOnWriteArrayList<>()
Set<String> set = new CopyOnWriteArraySet<>();

HashMap线程安全

//1
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());
//2
Map<String, String> map=new ConcurrentHashMap<>();

Q.E.D.