一、集合框架

1.1 HashMap和HashTable的区别

HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，主要区别在于 HashMap 允许 null key 和 null value,由于非线程安全，效率上可能高于 Hashtable。

1.2 HashMap 的底层结构

1. HashMap由数组+链表组成的。
2. HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。
3. 数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的
   1. 如果定位到的数组位置不含链表（当前entry的next指向null），那么对于查找，添加等操作很快，仅需一次寻址即可。
   2. 如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增。
   3. 对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。

1.3 为什么HashMap线程不安全

1. 在jdk1.7中，在多线程环境下，扩容时使用的是头插法，链表的顺序会翻转，这会造成环形链或数据丢失。
2. 在jdk1.8中，对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况。但在多线程环境下，put操作可能会发生数据覆盖的情况。

1.4 ArrayList 和 LinkedList 的区别

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

1.5 ArrayList 和 Vector 的区别

同步性

1. Vector是线程安全的，也就是说是它的方法之间是线程同步的，而ArrayList是线程序不安全的，它的方法之间是线程不同步的。
2. 如果只有一个线程会访问到集合，那最好是使用ArrayList，因为它不考虑线程安全，效率会高些；如果有多个线程会访问到集合，那最好是使用Vector，因为不需要我们自己再去考虑和编写线程安全的代码。

数据增长

1. ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，每次要增加存储空间时，不是只增加一个存储单元，而是增加多个存储单元，每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡。

2. Vector默认增长为原来两倍，而ArrayList的增长策略在文档中没有明确规定（从源代码看到的是增长为原来的1.5倍）。ArrayList与Vector都可以设置初始的空间大小，Vector还可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法。

1.6 Array 和 ArrayList 的区别

1. Array 可以包含基本数据类型和引用类型，ArrayList只能包含引用类型。
2. ArrayList是基于数组实现的，Array大小不可以调整大小，但ArrayList可以通过内部方法自动调整容量。
3. ArrayList是List接口的实现类，相比Array支持更多的方法和特性。

1.7 HashSet 的实现原理

1. HashSet是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
2. 当我们试图把某个类的对象当成 HashMap的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的equals(Object obj)方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
3. HashSet的其他操作都是基于HashMap的

1.8 HashMap 和 TreeMap 的区别

1. TreeMap<K,V>的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。
2. HashMap<K,V>的Key值实现散列hashCode()，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。
3. 如果需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候会使用HashMap。

1.9 List、Set、Map 之间的区别

List

List的元素以线性方式存储，可以存放重复对象，List主要有以下两个实现类：

1. ArrayList: 长度可变的数组，可以对元素进行随机的访问，向ArrayList中插入与删除元素的速度慢。
2. LinkedList: 采用链表数据结构，插入和删除速度快，但访问速度慢。

Set

Set中的对象不按特定(HashCode)的方式排序，并且没有重复对象，Set主要有以下两个实现类：

1. HashSet：HashSet按照哈希算法来存取集合中的对象，存取速度比较快。
2. TreeSet：TreeSet实现了SortedSet接口，能够对集合中的对象进行排序。

Map

Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一个键对象和值对象。Map主要有以下实现类：

1. HashMap：基于散列表实现，其插入和查询<K,V>的开销是固定的，可以通过构造器设置容量和负载因子来调整容器的性能。
2. LinkedHashMap：类似于HashMap，但是迭代遍历它时，取得<K,V>的顺序是其插入次序，或者是最近最少使用(LRU)的次序。
3. TreeMap：TreeMap基于红黑树实现。查看<K,V>时，它们会被排序。TreeMap是唯一的带有subMap()方法的Map，subMap()可以返回一个子树。

1.10 HashMap解决hash冲突

1. 每个 Map.Entry 其实就是一个 key-value 对，当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。
2. HashMap采用链表法解决散列值冲突的问题，链表是单向链表
3. 对哈希表的散列可以用取模实现，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，效率要高很多，这也是HashMap对Hashtable的一个改进。。

二、HashMap的实现原理

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表。

3.1 jdk1.7和jdk1.8中HashMap的变化

1. 1.7中采用数组+链表，1.8采用的是数组+链表/红黑树，即在1.7中链表长度超过一定长度后就改成红黑树存储。
2. 1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
3. 在1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在1.8中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

3.2 HashMap实现原理

1. HashMap的主干是一个Entry数组（长度是2的次幂）。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。
2. HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的

Q.E.D.