Java集合面试专题

1、ArrayList初始化容量是多少 

1.7之前是初始化就创建一个容量为10的数组，1.7以及1.7之后是初始化先创建一个空数组，第一次add时才扩容为10。

2、ArrayList是线程安全的吗？

ArrayList和linkedList都是线程不安全的。想要ArrayList和linkedList实现线程安全，可以使用Collections.synchronizedList()；使用方式：

List list = Collections.synchronizedList(new ArrayList<>());

从源码中我们可以看出，其实synchronizedList线程安全的原因是因为它几乎在每个方法中都使用了synchronized同步锁。

3、Hashtable 与 Collections.synchronizedMap(HashMap) 的区别

1、Hashtable 的 synchronized 是方法级别的；synchrnizedMap 的 synchronized 的代码块级别的

2、两者性能相近，但是 synchrnizedMap 可以用 null 作为 key 和 value

4、HashTable、ConcurrentHashMap为何不支持null键和null值

源码分析：

HashTable

 ConcurrentHashMap 

从分析中我们可以看到，hashtable，对于null值会抛出异常，而对于null键，则会调用null.hashCode()，从而导致空指针异常，而concurrenthashmap则对于null键值对，直接抛出空异常，这也就是为什么他们存入null键值对抛出异常的原因。

至于原因，如下：

ConcurrentHashMap和HashTable都是线程安全用来支持并发的，这样就会有一个问题，通过get(k)获取value时，如果得到的是null，无法判断它是put时候value为null，还是这个key根本不存在。

而HashMap是非线程安全的，不支持并发，可以通过contains(key)这个方法来判断，而支持并发的Map在调用m.contains(key)和m.get(k)时，m很可能已经不同了。

5、HashMap为什么不直接使用红黑树？为什么在链表长度为8的时候转成红黑树？

因为树结点所占空间是普通结点所占空间的两倍，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，而且红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡。综合考虑，认为只能在节点太多的时候，使用红黑树。不过，大部分情况下HashMap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。看源码：

在链表转变为红黑树方法中，有这样一个判断，数组长度小于MIN_TREEIFY_CAPACITY，大小是64，就会扩容，而不是直接转变为红黑树，可不是什么链表长度为8就变为红黑树，要仔细看代码，还有别的条件。 也就是说桶的数量必须大于64，小于64的时候只会扩容。 同样，元素个数小于6的时候也不是一定就会转换成链表。

那为什么选择8才会选择使用红黑树呢？

链表中的节点遵循泊松分布，根据统计，链表中节点数是8的概率已经接近千万分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。

6、ConcurrentHashMap在JDK1.7和JDK1.8中的底层原理

JDK1.7中，使用的是数组+Segment+分段锁的实现方式，结构图如下：

Segment通过继承ReentrantLock来进行加锁，每次锁住一个Segment来降低锁的粒度且保证了每个Segment内的操作的安全性。但是这么做的缺陷就是：ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

在JDK1.8中，对ConcurrentHashMap进行了优化，底层采用了数组+链表+红黑树的实现方式，取消了分段锁，取而代之的是CAS和Synchronized关键字来做优化，结构图如下：

ConcurrentHashMap采用了大量的分而治之的思想来降低锁的粒度，提升并发性能。其源码中大量使用了CAS操作保证数据的获取以及使用synchronized关键字对相应数据段加锁来实现线程安全，而不是和HashTable一样，不论什么方法，直接简单粗暴的使用 synchronized关键字来实现。

ConcurrentHashMap采用Node类作为基本的存储单元，每个键值对都存储在一个Node中，使用了volatile关键字修饰value和next，保证了并发的可见性

 volatile只能保证可见性，不能保证原子性

• 保证可见性是说在多线程的环境下：当这个变量修改时，所有的线程都会知道该变量被修改了，也就是所谓的“可见性”
• 不保证原子性是因为修改变量(赋值)实质上是在JVM中分了好几步，而在这几步内(从装载变量到修改)，它是不安全的

7、linkedList使用的是单向链表还是双向链表？是双向循环链表吗？

JDK1.7之前，使用的是双向循环链表。

JDK1.7及之后，使用双向链表 

 

8、linkedList为什么不用单链表，而是使用双链表？

linkedList因为底层使用链表，查询速度慢，只能依次遍历，使用双链表的话，遍历之前，都会先判断一下这个索引位于链表的前部分还是后部分，每次都会遍历链表的一半 ，而不是全部遍历。 

9、linkedList删除元素，默认是删除最后一个还是第一个元素？

    public E remove() {
        return removeFirst();
    }

remove()方法默认删除第一个元素。还提供了removeLast()和removeFirst()方法删除元素。