Java集合面试必备

系统管理员 2022-10-01 05:56 21阅读 0赞

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

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

1.ArrayList的源码分析：

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

![2019061116213222.png][]

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

扩容的代码分析：

![20190611164805763.png][]

![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的对比 ###

![20190611171431813.png][]

## 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)），并进行取与运算，得出存放的位置

![20190611211449451.png][]

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进行扩容），插入前检测需不需要扩容，有效避免无效扩容

[2019061116213222.png]: /images/20220119/f65629957bc74941a81eab85ef961dba.png
[20190611164805763.png]: /images/20220119/a5152ca9063543bbac3a7459cc781434.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29sZHNoYXVp_size_16_color_FFFFFF_t_70]: /images/20220119/6bf17e4636a144b08c41a1414d7764d5.png
[20190611171431813.png]: /images/20220119/e89b2fbca3b847248d8e3ecfb21b908f.png
[20190611211449451.png]: /images/20220119/cc5999a9e4bf4d40a83b9504c4642712.png