面试篇(JavaSE)：集合部分

集合框架

Collection 接口
定义接口基础功能
- List
  1.有序的集合
  2.元素有特定位置
  3.可以存放相同的元素
  - ArrayList
    1.在底层采用数组实现方式
    2.线程非安全
    3.查询元素根据索引，查找元素比较方便
    4.增加删除要考虑其他元素位置移动，索引效率低
  - LinkedList
    1.采用链表实现
    2.线程非安全
    3.增加和删除效率高
    4.查询的效率低
  - Vector
    1.在底层采用数组实现方式
    2.线程安全
- Set
  不包含重复元素的集合
  - HashSet
    1.线程非安全
    2.存取顺序不一样
  - LinkedHashSet（HashSet的子类）
    1.具有可预知迭代顺序
    2.线程非安全
  - treeSet
    1.线程非安全
    2.可以进行排序操作

ArrarList 和 LinkedList 区别

ArrayList 基于动态数组实现，LinkedList 基于双向链表实现。
对于随机访问 get 和 set，ArrayList 绝对优于 LinkedList，因为 LinkedList 要移动指针。
对于新增和删除操作 add 和 remove，LinkedList 比较占优势，因为 ArrayList 要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList 的速度反而优于 LinkedList。但若是批量随机的插入删除数据，LinkedList 的速度大大优于 ArrayList. 因为 ArrayList 每插入一条数据，要移动插入点及之后的所有数据。

HashMap 和 HashTable 区别

线程安全性不同
HashMap 是线程不安全的，HashTable 是线程安全的，其方法是 Synchronized 的，在多线程并发的情况下，可以直接使用 HashTable，但是使用 HashMap 时必须自己增加同步处理。由于线程安全，所以 HashTable 的效率不如 HashMap。
是否提供 contains 方法
HashMap 只有 containsValue 和 containsKey 方法；HashTable 有 contains、 containsKey 和 containsValue 三个方法，其中 contains 和 containsValue 方法功能相同。
key 和 value 是否允许 null 值
HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable 不允许。
数组初始化和扩容机制
HashTable 在不指定容量的情况下的默认容量为 11，HashMap 为 16，HashTable 不要求底层数组的容量一定要为 2 的整数次幂，而 HashMap 则要求一定为 2 的整数次幂。
HashTable 扩容时，将容量变为原来的 2 倍加 1，而 HashMap 扩容时，将容量变为原来的 2 倍。

HashMap 底层

JDK1.7及之前：数组+链表
JDK1.8：数组+链表+红黑树

简单一句话数组链表结构存储，这里Entry[]是map中的静态类。

entry[]数组默认长度为16，每个数组上跟着一个链表。

链表什么时候出现呢？就是在hashcode相同时出现，当put时候会生成一个hashcode便于存储位置。

但是不避免hashcode相同的情况这个时候就存在链表中（但是链表中虽然hashcode相同但是对象在jvm地址中可是不同的，可以用eques去判断）

当entry[]的大小超过负载因子0.75的时候开始扩容到自身的2倍（这是最大扩容）

在jdk1.8中当entry[]大于8个时，后面的数组将进行红黑树数据接口存储，大大提高了效率。

哈希表去重原理

去重：在添加方法中，先获取添加元素的hashcode值。

判断数组中是否存在相同元素，如果没有存在，则在数组中保存其hashcode值，并将元素以链表形式添加在数组元素的下面。如果存在（哈希冲突），就依次去判断当前数组下链表中的每一个元素进行对比，如果结果返回false，将元素添加链表末尾，如果返回true，说明链表中有该元素，则元素不添加到链表中。

注：当跟链表中的元素比对时，才用的是当前对象的equals方法和链表中的每一个元素对比，返回true不添加，比对结果都为false时，将元素添加到链表末尾。

TreeSet 和HashSet 区别

HashSet 是采用 hash 表来实现的。其中的元素没有按顺序排列，add()、remove()以及 contains() 等方法都是复杂度为 O(1)的方法。

TreeSet 是采用树结构实现(红黑树算法)。元素是按顺序进行排列，但是 add()、remove()以及 contains()等方法都是复杂度为 O(log (n))的方法。它还提供了一些方法来处理排序的 set，如 first(), last(), headSet(), tailSet()等等。