Java集合面试必备-蒲公英云

集合是Java的核心东西，应该是面试必问的东西，我下面就把集合常见的面试题来分享下

分享的过程中将会有很多知识点的穿插，不是很懂的可以百度，后续我还会一直跟进这篇博客的，我相信这些东西能够让你和面试官吹一个小时的。

1.ArrayList的源码分析：

1.1底层的数据结构：object数组

Java中transient关键字的作用，简单地说，就是让某些被修饰的成员属性变量不被序列化（这里如果你不知道序列化是啥的你可以自己百度解决，我这里就不一一介绍了，不然东西太多了，有点抓不住重点）

你回答这个问题的时候，可以说数组被transient修饰，下面面试官可能会问为啥要被这个关键字修饰，你就可以回答：

ArrayList中elementData为什么被transient修饰？

transient用来表示一个域不是该对象序行化的一部分，当一个对象被序行化的时候，transient修饰的变量的值是不包括在序行化的表示中的。但是ArrayList又是可序行化的类，elementData是ArrayList具体存放元素的成员，用transient来修饰elementData，岂不是反序列化后的ArrayList丢失了原先的元素？
其实玄机在于ArrayList中的两个方法：

/**
     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();
        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);
        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        // Read in size, and any hidden stuff
        s.defaultReadObject();
        // Read in capacity
        s.readInt(); // ignored
        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);
            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }
 ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。  
   为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证**只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间**。

ArrayList初始化问题

jdk8：ArrayList中维护了Object[] elementData，初始容量为0.第一次添加时，将初始elementData的容量为10再次添加时，如果容量足够，则不用扩容直接将新元素赋值到第一个空位上如果容量不够，会扩容1.5倍

jdk7:ArrayList中维护了Object[] elementData，初始容量为10.添加时，如果容量足够，则不用扩容直接将新元素赋值到第一个空位上如果容量不够，会扩容1.5倍

jdk7和jdk8：区别：jdk7 相当于饿汉式，创建对象时，则初始容量为10 jdk8 相当于懒汉式，创建对象时，并没有初始容量为10，而在添加时才去初始容量为10

扩容的代码分析：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29sZHNoYXVp_size_16_color_FFFFFF_t_70

2.LinkedList源码分析

1.底层结构：双向链表

LinkedList中维护了两个重要的属性 first和last，分别指向首节点和尾节点。
每个节点（Node类型）里面又维护了三个属性item、next、prev，分别指向当前元素、下一个、上一个元素。最终实现手拉手的链表结构！

2.ArrayList和LinkedList的对比

3.HashMap集合源码分析

底层结构：哈希表
jdk7:数组+链表
jdk8:数组+链表+红黑树

源码分析：

jdk8：HashMap中维护了Node类型的数组table，当HashMap创建对象时，只对加载因子初始化为0.75，table还是默认保存为null，当第一次添加的时候，将table的容量设为16，临界为12，每次调用putVal方法

1.先获取key的二次hash值（h = key.hashCode()) ^ (h >>> 16)），并进行取与运算，得出存放的位置

2.判断该存放的位置上是否有元素，如果没有直接存放，如果有就进行判断，如果相等就直接覆盖，如果不相等，判断是否为链表结构还是树状结构，按照对应结构的判断方式判断是否相等

3.将size更新，判断是否超过了临界值，如果超过了，则需要重新resize()进行2倍扩容，并打乱原来的顺序，重新排列（当链表的节点数据大于八并且当前的容量小于64的时候，也会进行扩容）

4.当一个桶中的链表的节点数>=8 && 桶的总个数（table的容量）>=64时，会将链表结构变成红黑树结构

4.concurrentHashMap分析

底层采用分段的数组+链表实现，线程安全
通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容