一、集合家谱

  1. 单列集合 Collection：
    1. List：
      1. ArrayList
      2. LinkedList
      3. Vector
    2. Set：
      1. HashSet
        1. LinkedHashSet
      2. TreeSet
  2. 双列集合 Map：
    1. HashMap
      1. LinkedHashMap
    2. TreeMap
    3. Hashtable

单列集合

List

  1. ArrayList 底层：
    ArrayList 底层是动态数组，数组在内存上开辟一段连续的内存空间，有索引时查找，可以根据寻址公式：目标地址 = 起始地址 + i * 单个元素所占空间，时间复杂度为 O(1)，增加和删除最后一个一位，时间复杂度为 O(1)，其他部分由于需要移位，时间复杂度为 O(n)

  2. ArrayList 扩容机制：
    ArrayList 初始容量为0，在第一次 add 时会初始化为 10，当容量小于当前占用容量(size)+1时，会使用 grow 扩容1.5倍，每次扩容时都要拷贝数组
    扩容大小设为1.5倍的原因：是为了在减少扩容次数和降低空间浪费之间取得平衡，扩容倍数过小则会导致频繁扩容和大量数组复制，过大会导致内存浪费

  3. LinkedList 底层：
    LinkedList 底层是双向链表，双向链表具有多个节点，每个节点都有前驱指针指向前一个节点和后继指针指向后一个节点，查找时需要遍历双向链表，会根据实际来选择从头节点或者尾节点开始遍历，时间复杂度为 O(n)，插入和删除时，除了头尾节点时间复杂度为 O(1)，其他部位由于需要遍历链表，时间复杂度为 O(n)

  4. 如何保证 ArrayList 和 LinkedList 线程安全：
    使用线程安全的 ArrayList 和 LinkedList 

    1
    2
    List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
    List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());

    在方法内部使用，局部变量线程安全

  5. 如何实现数组和 List 之间的转换：

    1. 数组转 List：使用 JDK 中 java.util.Arrays 工具类的 asList 方法
      修改数组内容后，List 受影响
    2. List 转数组：使用 List 的 toArray 方法，无参 toArray 方法返回 Object 数组，传入初始化长度数组对象，返回该数组对象
      修改 List 后，数组不受影响