集合

总结

• 集合分为两大接口

1. Collection: 单一元素
   1. List: 有序可重复
      1. ArrayList: 底层Object[]数组，线程不安全，频繁查找搜索
      2. Vector: 底层Object[]数组，线程安全
      3. LinkedList: 双向链表
   2. Set: 不可重复
      1. HashSet: 无序，底层哈希表（基于 HashMap 实现）
         1. LinkedHashSet: 子类，底层链表和哈希表，通过LinkedHashMap实现，顺序FIFO
      2. TreeSet: 有序，红黑树，支持对元素自定义排序
   3. Queue: 有序可重复，先进先出，不支持null
      1. PriorityQueue
      2. DelayQueue
      3. ArrayDeque
2. Map: 键值对,键无序不可重复，值无序可重复，一个键映一个值
   1. HashMap: 非线程安全，数组+链表(解决哈希冲突)/红黑树(减少搜索时间)
      1. LinkedHashMap: 增加了双向链表，保证键值对插入顺序，
   2. HashTable: 线程安全，数组+链表，不可存储null键值
   3. SortedMap:
      1. TreeMap: 红黑树（自平衡的排序二叉树）
   4. 容量比较？

知识点

• ArrayList和数组的区别

数组是固定长度的，必须指定长度大小；ArrayList是动态的，可扩可缩；
ArrayList允许使用泛型来确保类型安全，数组则不可以；
只能存储对象，基础类型需使用包装类；数组都可以；
ArrayList提供了丰富的API操作元素；数组只能通过下标；

• ArrayList可以存储null值，不建议，取值容易造成空指针

• LinkedList 插入和删除元素的时间复杂度？

• ArrayList 与 LinkedList 区别

数据结构不同
线程安全 No! 都不是同步的
支持快速随机访问，ArrayList支持，实现了RandomAccess接口
内存空间占用？？

• Comparable 和 Comparator 的区别

Comparable java.lang compareTo(a)
    class Person implements Comparable<Person>
    比如存放于TreeMap，需要Person实现Comparable否则报错，用于排序
Comparator java.util compare(a, b)
    sort(List<T> list, Comparator<? super T> c)

• 集合去重

结合Set
    new HashSet(Collection<? extends E> c)
    效率高，底层HashMap containsKey 方法
ArrayList
    contains 比较    
    效率一般，底层遍历比较

深入理解

• ArrayList 扩容机制分析

参考

• JavaGuide(Java面试 + 学习指南)