1.Java中的集合框架有哪些？

  • Java中的集合框架主要包含两种类型的容器，一种是集合（Collection）,储存一个元素集合，另外一种是图（Map），储存键/值对映射。
  • Collection接口又有3种子类型，List,Set和Queue,再下面是一些抽象类，最后是具体实现类，常用的有ArrayList, LinkedList, HashSet, LinkedHashSet, HashMap, TreeMap, LinkedHashMap等。 alt

2.ArrayList和LinkedList的底层实现和区别？

  • ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构。
  • ArrayList:增删慢、查询快，线程不安全，对元素必须连续存储；
  • LinkedList:增删快、查询慢，线程不安全。

追问1.谈谈ArrayList的扩容机制？

  • 从ArrayList的源码可知，当以无参数构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量为10. 当插入的元素个数大于当前容量时，就需要进行扩容，ArrayList每次扩容之后容量都会变为原来的1.5倍左右。

3.HashMap的底层实现？扩容？

  • 在jdk1.7之前HashMap是基于数组和链表实现的，而且采用头插法。
  • 而jdk1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）（将链表转换为红黑树（二叉排序树）之前会判断，如果当前数组的长度小于64，那么会选择进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。采用尾插法。
  • HashMap默认的初始化大小为16。当HashMap中的元素个数之和大于负载因子*当前容量的时候就要进行扩充，容量变为原来的2倍。（这里注意不是数组中的个数，而是数组和链表/树中的所有元素个数之和！）

注意： 可以在预知存储数据量的情况下，提前设置初始容量（初始容量 = 预知数据量 / 加载因子）。以减少resize()操作，提高HashMap()效率。

HashMap是线程不安全的，其主要体现在：

  1. 在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失；
  2. 在Jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

追问1.HashMap扩容时为什么是2的n次幂？

  • 数组下标的计算方法是 （n-1）& hash,取余（%）操作中如果除数是2的幂次则等价于其除数减一的与（&）操作（即hash%length == hash&(length-1) 的前提是length是2的n次方；）。并且采用二进制位操作&，相对于%能够提高运算效率，这就解释了HashMap的长度为什么是2的幂次方。
  • tip:hash()方法的具体实现方式，简而言之，就是尽量打乱hashCode真正参与运算的低16位。

4.Java中线程安全的集合有哪些？

  • Vector:就比ArrayList多了个同步化机制（线程安全）。
  • Hashtable:就比HashMap多了个线程安全。
  • ConcurrentHashMap:是一种高效但是线程安全的集合。
  • Stack：栈，也是线程安全的，继承于Vector。

追问1.ConcurrentHashMap的底层实现，它为什么是线程安全的？

  • 在JDK1.7是 分段的数组（Entry）+链表，JDK1。8的时候跟HashMap1.8一样都是基于数组(Node)+链表/红黑树。
  • ConcurrentHashMap是线程安全的
  1. 在jdk1.7的时候是使用Segment,每一把锁只锁容器中的一部分数据，多线程访问容器里不同的数据段的数据，就不会存在锁竞争，提高并发访问率。
  2. 在jdk1.8的时候摒弃了Segment的概念，而是直接使用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。synchronized只锁定当前链表或红黑树的首节点。

5.HashMap和Hashtable的区别？

  1. 线程是否安全：HashMap是非线程安全的，Hashtable是线程安全的，因为Hashtable内部的方法基本都经过synchronized修饰。（如需线程安全，可用ConcurrentHashMap）。

  2. 对 Null key 和 Null value 的支持：HashMap可以存储null的key和value，但是Null作为键只能有一个，null作为值可以有多个；Hashtable则不允许，否则会抛出NullPointerException.

  3. 初始容量大小和每次扩容量大小的不同：

    1). Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n + 1。HashMap默认的初始大小为16。之后每次扩容，容量变为原来的2倍。

    2).如果创建时给定了容量初始值，Hashtable会直接使用给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说HashMap总是使用2的幂次作为哈希表的大小。

  4. 底层数据结构：而jdk1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）（将链表转换为红黑树（二叉排序树）之前会判断，如果当前数组的长度小于64，那么会选择进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。采用尾插法。Hashtable没有这种机制。

  5. 效率：因为线程安全的问题，HashMap要比Hashtable效率高一点。另外Hashtable基本被淘汰，不要使用！

6.HashMap和TreeMap的区别？

  1. HashMap是通过hash值进行快速查找的：HashMap中的元素是没有顺序的；TreeMap中所有的元素都是有某一固定顺序的，如果需要得到一个有序的结果，就应该使用TreeMap;
  2. HashMap和TreeMap都是线程不安全的；
  3. HashMap继承AbstractMap类；覆盖了hashCode()和equals()方法，以确保两个相等的映射返回相同的哈希值(类型相同，各个字段相同，则哈希值相同)；TreeMap继承SortedMap类：他保持键的有序顺序。
  4. HashMap:基于hash表实现的；使用HashMap要求添加的键类明确定义了hashCode()和equals()（可以重写该方法）；为了优化HashMap的空间使用，可以调优初始化容量和负载因子；TreeMap:基于红黑树实现的；TreeMap就没有调优选项，因为红黑树总是处于平衡的状态；
  5. HashMap:适用于Map插入，删除，定位元素；TreeMap:适用于按自然顺序或自定义顺序遍历键(key).