高频面试题-JDK集合源码篇(String,ArrayList)

约定不等于承诺〃 2023-01-21 14:24 46阅读 0赞

## 前言 ##

一直想做这么一件事情，就是把一些高频面试题做一个整理，方便你我他，当然我不光是整理面试题和答案，我还会从原理及源码的角度去诠释这些答案。

正好自己也一直在负责招人这一块，对于面试有一些心得，做了一些总结写下来，不喜勿喷，因为自己写这些东西一直也不收费，把自己的一些心得总结下来，方便新入行的朋友，只要你认真看完我相信面试中小型企业是没有任何压力的，如喜请给好评，如喜请给好评，如喜请给好评 重要事情说三遍。

## 基础面试题 ##

#### 1.String 和 StringBuilder 和 StringBuffer ####

*  String 和 StringBuilder 和 StringBuffer的区别
    
    区别就是String是不可变的，每次创建一个字符串，不管是用New的方式，还是使用“”引号声明,亦或是“”+“”拼接字符串都会在内存中开辟新的内存空间。而后2者都是可变的它们都继承与AbstractStringBuilder 。在JDK8及以前，他们都是使用char\[\] 存储数据，在JDK9往后为了节约内存采用了byte\[\]存储数据。
 *  String为什么不可变StringBuilder为什么可变
    
    因为String底层的 char\[\] 前面加了一个final 修饰符，我们知道加了final修饰的变量是不可被重新赋值的，所以它是不可变的,来看一下源码
    
    String源码 : `char数组前面有final`
    
        public final class String
        implements java.io.Serializable, Comparable<String>, CharSequence { 
        /** The value is used for character storage. */
        private final char value[];
    
    StringBuilder和StringBuffer源码
    
        public final class StringBuilder
            extends AbstractStringBuilder
            implements java.io.Serializable, CharSequence
        { 
        
            /** use serialVersionUID for interoperability */
            static final long serialVersionUID = 4383685877147921099L;
        
            /** * Constructs a string builder with no characters in it and an * initial capacity of 16 characters. */
            public StringBuilder() { 
                super(16);	//初始容量16
            }	
            ...省略...
        }
    
    AbstractStringBuilder源码 : `char数组前面没有final`
    
        abstract class AbstractStringBuilder implements Appendable, CharSequence { 
            /** * The value is used for character storage. * 存储元素的char数组 */
             
            char[] value;
        
            /** * The count is the number of characters used. */
            int count;
        
            /** * This no-arg constructor is necessary for serialization of subclasses. */
            AbstractStringBuilder() { 
            }
        
            /** * Creates an AbstractStringBuilder of the specified capacity. */
            AbstractStringBuilder(int capacity) { 
                value = new char[capacity];
            }
 *  StringBuilder为什么线程不安全StringBuffer为什么安全  
    要安全就是要加锁，所以SpringBuffer暴露给外界的方法是加了synchronized同步锁的所以它安全，而StringBuilder并没有加，所以它不安全。这就导致了另外一个区别，就是加了锁安全，但是性能变低了，没加锁不安全，但是性能高。
    
    StringBuffer源码：比如append方法加了synchronized
    
        @Override
        public synchronized StringBuffer append(Object obj) { 
            toStringCache = null;
            super.append(String.valueOf(obj));
            return this;
        }
        
        @Override
        public synchronized StringBuffer append(String str) { 
            toStringCache = null;
            super.append(str);
            return this;
        }
    
    StringBuilder源码：append方法并没有加synchronized
    
        @Override
        public StringBuilder append(Object obj) { 
            return append(String.valueOf(obj));
        }
        
        @Override
        public StringBuilder append(String str) { 
            super.append(str);
            return this;
        }
 *  什么场景下使用StringBuilder什么场景使用StringBuffer
    
    因为StringBuilder和StringBuffer是可变的，所以如果要拼接字符串尽量用这两个家伙，由于StringBuidler是线程不安全的，所以在多线程环境中，要使用StringBuffer保证线程安全，如果不是在多线程情况下，使用StringBuilder就好了，性能更高。

#### 2.ArrayList和LinkedList的区别 ####

都是List的子集合，LinkedList继承与Dqueue双端队列，看名字就能看出来前者是基于`数组实现`,底层采用Object\[\]存储元素，数组中的元素要求`内存分配连续`，可以使用索引进行访问，它的优势是`随机访问快`，但是由于要保证内存的连续性，如果删除了元素，或者从中间位置增加了元素，会设计到`元素移位`的操作，所以`增删比较慢`。

ArrayList源码如下：

public class ArrayList<E> extends AbstractList<E>
    		        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    			{ 
    		    private static final long serialVersionUID = 8683452581122892189L;
    		
    		    /**容量 * Default initial capacity. */
    		    private static final int DEFAULT_CAPACITY = 10;
    		
    	   	    //存储元素的对象数组
    	
    			transient Object[] elementData; // non-private to simplify nested class access
    			
    			//当前元素数量
    			 private int size;
    			...省略...
    			
    			//可手动指定初始容量
    			public ArrayList(int initialCapacity) { 
    	        if (initialCapacity > 0) { 
    	            this.elementData = new Object[initialCapacity];
    	        } else if (initialCapacity == 0) { 
    	            this.elementData = EMPTY_ELEMENTDATA;
    	        } else { 
    	            throw new IllegalArgumentException("Illegal Capacity: "+
    	                                               initialCapacity);
    	        }
    	    }

而LinkedList是基于`双向链表`的存储结构，链表结构`不要求元素的内存分配连续`性，不支持索引访问，但是它的每个元素持有下一个元素的指针，或持有上一个元素的指针，所以它的访问方式是从链表头`一个一个往后面取元素`，或者从链表尾一个一个往前面取元素(双向链表)，它的缺点是`查找元素慢`，因为要从前往后一个一个遍历，如果是查找第一个和最后一个元素一次查找就拿到了。它的有点就是增删了元素只需要改变元素之间的指针指向即可，不涉及到移位操作，所以`增删快`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70]

LinkedList源码如下：

public class LinkedList<E>
    	    extends AbstractSequentialList<E>
    	    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    	{ 
    	    transient int size = 0;
    	
    	    /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
    	    transient Node<E> first;	//第一个节点
    	
    	    /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
    	    transient Node<E> last;	//最后一个节点
    
    		//一个节点对象
    		private static class Node<E> { 
            E item;	//存储节点数据
            Node<E> next;	//下一个节点
            Node<E> prev;	//上一个节点
    
            Node(Node<E> prev, E element, Node<E> next) { 
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

当然如果是ArrayList和LinkedList都进行遍历，其实性能也就差不多。

#### 3.ArrayList的扩容机制 ####

ArrayList默认初始容量为 10 也可以在 new ArrayList(容量) 指定容量大小，当存储新的元素的时候，ArrayList会判断容量来决定是否扩容, `新的容量 = 老的容量 + 老容量/2` ， 成1.5倍扩容。其实就是以新的容量创建一个新的数组，然后把老的数组中的元素copy到新的数组中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 1]

增加元素到ArrayList末尾

public boolean add(E e) { 
    	//判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //把新元素放到数组的 seize+1 位置
        elementData[size++] = e;
        return true;
    }
    
    //扩容方法
     private void grow(int minCapacity) { 
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            //数组拷贝操作
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

这就是扩容长度：`int newCapacity = oldCapacity + (oldCapacity >> 1);新的容量 = 老的容量 + 老容量/2` ， 而 `elementData = Arrays.copyOf(elementData, newCapacity);` 就是以新的容量创建一个新的数组，然后把老的数组中的元素copy到新的数组中。

#### 4.ArrayList如何删除元素呢 ####

删除元素和新增元素一样，都要涉及到移位操作，使用的都是数组拷贝的方式。  
![在这里插入图片描述][20210521153547760.png]

ArrayList\#remove(index) 源码：

/**删除此列表中指定位置的元素。 将所有后续元素向左移动（从其索引中减去一个）。 * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */
        public E remove(int index) { 
            rangeCheck(index);
    
            modCount++;
            //要删除的索引位置的老的元素
            E oldValue = elementData(index);
    	
            int numMoved = size - index - 1;
            if (numMoved > 0)
            	//拷贝数组：把index位置后面的往前移动
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            //size减少1
            elementData[--size] = null; // clear to let GC do its work
    		
            return oldValue;
        }

拷贝数组：把index位置后面的往前移动，index位置的元素会被后面一个元素覆盖。

文章太长影响阅读，就到这里结束把，喜欢的话请给个好评吧！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70]: /images/20221020/d9e5ab34e8cc49b695b62a978ad804a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0OTQxNDg_size_16_color_FFFFFF_t_70 1]: /images/20221020/35d5f0c70bf54b36a6605ea6be537575.png
[20210521153547760.png]: /images/20221020/efb204f8be5a4023878655cf8527f8d8.png