1. List 和 Map、Set 的区别（必会）
2. List 和 Map、Set 的实现类（必会）
3. HashMap 的底层原理（高薪常问）
- map.put(k,v)实现原理
- map.get(k)实现原理
4. HashMap 和 HashTable ConcurrentHashMap区别(高薪常问)

1. List 和 Map、Set 的区别（必会）

List 和 Set 是存储单列数据的集合，Map 是存储键值对这样的双列数据的集合；
List 中存储的数据是有顺序的，并且值允许重复；
Map 中存储的数据是无序的，它的键是不允许重复的，但是值是允许重复的；
Set 中存储的数据是无顺序的，并且不允许重复，但元素在集合中的位置是由元素的 hashcode 决定，即位置是固定的（Set 集合是根据 hashcode 来进行数据存储的，所以位置是固定的，但是这个位置不是用户可以控制的，所以对于用户来说 set 中的元素还是无序的）。

2. List 和 Map、Set 的实现类（必会）

(1)Collection 接口:

List 有序,可重复
1. ArrayList 优点: 底层数据结构是数组，查询快，增删慢。缺点: 线程不安全，效率高
2. Vector 优点: 底层数据结构是数组，查询快，增删慢。缺点: 线程安全，效率低, 已给舍弃了
3. LinkedList 优点: 底层数据结构是链表，查询慢，增删快。缺点: 线程不安全，效率高
Set 无序,唯一
1. HashSet 底层数据结构是哈希表。(无序,唯一) 如何来保证元素唯一性? 依赖两个方法：hashCode()和 equals()
2. LinkedHashSet 底层数据结构是链表和哈希表。(FIFO 插入有序,唯一) 1.由链表保证元素有序 2.由哈希表保证元素唯一
3. TreeSet 底层数据结构是红黑树。(唯一，有序) 1. 如何保证元素排序的呢? 自然排序比较器排序 2.如何保证元素唯一性的呢? 根据比较的返回值是否是 0 来决定

(2)Map 接口有四个实现类：

HashMap 基于 hash 表的 Map 接口实现，非线程安全，高效，支持 null 值和 null 键，线程不安全。
HashTable 线程安全，低效，不支持 null 值和 null 键；
LinkedHashMap 线程不安全，是 HashMap 的一个子类，保存了记录的插入顺序；
TreeMap 能够把它保存的记录根据键排序，默认是键值的升序排序，线程不安全。

3. HashMap 的底层原理（高薪常问）

HashMap 在 JDK1.8 之前的实现方式数组+链表,
但是在 JDK1.8 后对 HashMap 进行了底层优化,改为了由数组+链表或者数值+红黑树实现,
主要的目的是提高查找效率

Jdk8 数组+链表或者数组+红黑树实现，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，当红黑树节点小于等于 6 时又会退化为链表。
当 new HashMap():底层没有创建数组，首次调用 put()方法示时，底层创建长度为 16 的数组，jdk8 底层的数组是：Node[],而非 Entry[]，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用 rehash 方法将数组容量增加到原来的两倍，专业术语叫做扩容，在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能. 默认的负载因子大小为 0.75，数组大小为 16。也就是说，默认情况下，那么当 HashMap 中元素个数超过 160.75=12 的时候，就把数组的大小扩展为 216=32，即扩大一倍。
在我们 Java 中任何对象都有 hashcode，hash 算法就是通过 hashcode 与自己进行向右位移 16 的异或运算。这样做是为了计算出来的 hash 值足够随机，足够分散，还有产生的数组下标足够随机

map.put(k,v)实现原理

（1）首先将 k,v 封装到 Node 对象当中（节点）。
（2）先调用 k 的 hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
（3）下标位置上如果没有任何元素，就把 Node 添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着 k 和链表上每个节点的 k 进行 equal。如果所有的 equals 方法返回都是 false，那么这个新的节点将被添加到链表的末尾。如其中有一个 equals 返回了 true，那么这个节点的 value 将会被覆盖。

map.get(k)实现原理

(1)、先调用 k 的 hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
(2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回 null。如果这个位置上有单向链表，那么它就会拿着参数 K 和单向链表上的每一个节点的 K 进行 equals，如果所有 equals 方法都返回 false，则 get 方法返回 null。如果其中一个节点的K 和参数 K进行 equals返回true，那么此时该节点的 value就是我们要找的 value 了，get 方法最终返回这个要找的 value。

4. Hash 冲突不同的对象算出来的数组下标是相同的这样就会产生 hash 冲突，当单线链表达到一定长度后效率会非常低。

5. 在链表长度大于 8 的时候，将链表就会变成红黑树，提高查询的效率。

4. HashMap 和 HashTable ConcurrentHashMap区别(高薪常问)

区别对比一(HashMap 和 HashTable 区别)：
1、HashMap 是非线程安全的，HashTable 是线程安全的。
2、HashMap 的键和值都允许有 null 值存在，而 HashTable 则不行。
3、因为线程安全的问题，HashMap 效率比 HashTable 的要高。
4、Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更适合于单线程环境，而 Hashtable 适合于多线程环境。一般现在不建议用 HashTable, ① 是 HashTable 是遗留类，内部实现很多没优化和冗余。②即使在多线程环境下，现在也有同步的 ConcurrentHashMap 替代，没有必要因为是多线程而用 HashTable。

区别对比二(HashTable 和 ConcurrentHashMap 区别)：

HashTable 使用的是 Synchronized 关键字修饰，
ConcurrentHashMap 是 JDK1.7 使用了分段锁技术来保证线程安全的。
JDK1.8ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。
数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。
synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突,就不会产生并发,效率又提升N倍。

面试题-Java