Collection

Set

• TreeSet：
  • 底层基于红黑树实现
  • 支持有序性操作，查找，删除，添加等操作都是基于红黑树
  • 不允许插入为空
  • 线程不安全
  • 查找时间复杂度为O(logN)
• HashSet：
  • 底层基于哈希表实现
  • 不支持有序性操作，并且失去元素插入顺序信息
  • 允许插入为空，但是最多一个
  • 线程不安全
  • 查找时间复杂度：O(1)
• LinkedHashSet：
  • 继承自HashSet，同时使用双向链表维护元素的插入顺序

List

• ArrayList

  • 基于动态数组实现
  • 适合于顺序添加、随机访问(RandomAccess 接口标识该类支持快速随机访问)的场景
  • 允许插入为空，允许插入重复数据
  • 线程不安全

  数组的默认大小为10；添加元素时候，如果容量不足，需要使用 grow() 方法进行扩容，新容量是旧容量的1.5倍，扩容操作还需要将旧数组中的元素copy到新数组中，该过程比较耗费性能。
  添加一个元素，同样需要copy一次，因此该过程是比较耗费性能的。
  删除中间某个元素时候，后面元素需要整体向前移动，因此该过程也是耗费性能，而对于删除最后一个元素，则可以直接设为null，让gc垃圾回收机制去回收。

• LinkedList

  • 基于双向链表实现
  • 允许插入为空，允许插入重复数据
  • 线程不安全

• Vector

  • 原理与ArrayList相同
  • 允许插入为空，允许插入重复数据
  • 线程安全(采用synchronized同步实现)

  Vector与ArrayList类似，扩容是原大小的2倍，采用synchronized同步实现，因此开销就比ArrayList大。
  可以使用Collections.synchronizedList();得到一个线程安全的ArrayList。也可以使用concurrent并发包下的CopyOnWriteArrayList类。

Queue

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

Map

• Hashtable

  • 基于哈希表实现
  • key、value均不能为null，且key不能重复，value允许重复
  • 失去元素插入顺序信息
  • 线程安全(采用synchronized同步实现)

• HashMap

  • 基于哈希表实现
  • key、value允许为null，重复性：key重复会覆盖，value允许重复
  • 失去元素插入顺序信息
  • 线程不安全

  capacity：默认table容量为16，扩容时候保证为2的n次方
  loadFactor：装载因子，默认是0.75
  Java8之前：桶存储的是用链表。而Java8之后：链表长度大于8。时会将链表转换为红黑树。

• LinkedHashMap

  • 基于双向链表实现
  • key、value都允许为空，重复性：key重复会覆盖 value允许重复
  • 线程不安全

• TreeMap

  • 基于红黑树实现
  • key不能为null，value允许为空，重复性：key重复会覆盖，value允许重复
  • 根据key值进行排序
  • 线程不安全