1、ArrayList与LinkedList的异同

同：

• 是否可扩展：ArrayList和LinkedList都属于可扩展的
• 是否同步安全：ArrayList和LinkedList都是不同步的，线程不安全

异：

• 底层数据结构：ArrayList底层实现是数组，LinkedList底层实现是双向链表
• 是否支持随机访问：ArrayList支持随机访问，可通过索引随机访问，LinkedList只能遍历访问。所以ArrayList查询快，LinkedList查询慢。
• 插入和删除是否受元素位置的影响：ArrayList插入删除元素受操作位置影响，插在列表末尾不受影响，插在列表中间，则插入位置后面的元素都需要移动。LinkedList插入不受位置影响。所以ArrayList增删慢，LinkedList增删快。
• 内存地址是否连续：ArrayList在内存中的空间是物理上，逻辑上都是连续的，LinkedList在内存的空间物理上可以是不连续的，逻辑上是连续的。
• 内存空间浪费：ArrayList在列表的末尾总是要预留一定容量的空间，LinkedList存储时要存储节点的前驱和后继。

2、ArrayList 与 Vector 区别

ArrayList是线程不安全的，Vector是线程安全的。所以ArrayList适合在单线程下使用，Vector适合在多线程下使用。

3、Array 和 ArrayList 有什么区别？什么时候该应 Array 而不是 ArrayList 呢？

• Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
• Array 大小是固定的，ArrayList 的大小是动态变化的。
• ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。

对于处理固定大小的基本数据类型用Array，其他情况尽量用ArrayList。

4、HashMap的数据结构是什么

jdk1.7中HashMap是采用“数组+链表”的数据结构。在jdk1.8中，HashMap采用“数组+链表+红黑树”的数据结构。

image.png

5、HashMap中的常见参数

• HashMap默认初始化容量（数组大小）为16。
• HashMap默认最大容量（数组大小）为2的30次方。
• HashMap链表转红黑树链表的长度需要达到8。
• HashMap红黑树转链表红黑树中节点个数需要达到6。
• HashMap默认装载因子为0.75，当数组实际占用容量超过数组长度的0.75时，对HashMap扩容。
• HashMap链表转红黑树的条件之一，哈希表长度大于等于64。

6、HashMap.put()方法步骤

image.png

7、HashMap怎么确定元素索要插入桶的位置？

1、拿到所导入元素key的hashcode做hash运算，得到一个hash值。
2、hash值和（哈希表长度-1）做与运算得到桶的位置。

8、什么是哈希冲突？HashMap怎么解决哈希冲突？

什么是哈希冲突：当两个不同的输入值，根据同一hash函数计算出相同的hash的现象，我们就把它叫做碰撞（哈希碰撞、哈希冲突）

HashMap解决哈希冲突：

• 使用链地址法，使得具有相同hash值的不同对象都能在HashMap中存储。
• 使用两次扰动函数（Hash函数）来降低哈希冲突的概率

9、什么是hash函数？HashMap为什么要实现hash函数？

hash函数是HashMap中实现的根据对象hashcode值来计算出一个hash值。使用hash函数主要是因为，如果使用hashcode取余来定位key，这样hashcode只有低位参与了运算，高位没有参与，哈希冲突的概率比较大。hash函数是对象的hashcode值与自己右移16位得到的值进行异或运算得到hash值。使得hashcode每一位都参与了运算，降低哈希冲突的概率。

10、什么是HashMap 2次扰动？

HashMap两次扰动指的是hash函数，一次是hashcode位运算，一次是异或运算。2次扰动降低哈希冲突的概率。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}

11、为什么HashMap数组长度要保证为2的幂次方呢？

因为HashMap定位key在数组中的位置是

(n - 1) & hash  //数组长度-1 和 hash值做按位与运算

只有数组长度（n）为2的幂次方，n - 1的二进制数才能全为1。这样与hash值做按位与运算时，hash值参与运算的位才会有意义，避免有的位置永远不能存储元素，增加空间的利用率，避免浪费。
例子：
如果 length 不是 2 的次幂，比如 length 为 15，则 length - 1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0 ，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大

12、HashMap中什么时候链表会转为红黑树？什么时候红黑树会转为链表？

1：链表转红黑树
同时满足两个条件：

• 链表的长度大于等于8
• 数组长度大于等64时

2：红黑树转链表
当数组扩容时，若存在红黑树的节点数小于等于6，则将其转为链表

13、HashMap数组什么时候扩容，怎么扩容？

• 插入元素后数组实际占用长度超过数组长度的0.75时扩容
• 两倍扩容

14、HashMap与HashTable的区别

• HashMap是非线程安全的，HashTable是线程安全的。
• HashMap的键和值都允许有null值存在，而HashTable则不行。
• 因为线程安全的问题，HashMap效率比HashTable的要高。
• Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。

14、ConcurrentHashMap

ConcurrentHashMap是升级版的HashTable，采用分段式锁。

• 底层实现：数组+链表+红黑树
• 通过把整个Map分为N个Segment，分别加锁。执行修改操作时只需要获得对应段的锁，而不用获得整个Map的锁。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
• 执行某些方法时（size()、containsValue()）仍然需要获取全部的锁。按顺序获取所有的锁，执行完后又按顺序释放所有锁。

15、HashSet是如何保证数据不可重复的？

HashSet底层的实现是HashMap，HashSet把数据作为key值保存，而value用一个相同的虚值保存。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
}

16、List和Map的区别

• List是存储单列数据的集合，Map存储的是键值对，是双列数据。
• List存取是有序的，Map的存取是无序的。

17、什么fail-fast、fail-safe机制？

fail-fast：“快速失败”也就是 fail-fast，它是Java集合的一种错误检查机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。记住是有可能，而不是一定，例如，假设存在线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
fail-safe：任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出ConcurrentModificationException。
区别：