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

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

基础面试题

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是基于双向链表的存储结构,链表结构不要求元素的内存分配连续性,不支持索引访问,但是它的每个元素持有下一个元素的指针,或持有上一个元素的指针,所以它的访问方式是从链表头一个一个往后面取元素,或者从链表尾一个一个往前面取元素(双向链表),它的缺点是查找元素慢,因为要从前往后一个一个遍历,如果是查找第一个和最后一个元素一次查找就拿到了。它的有点就是增删了元素只需要改变元素之间的指针指向即可,不涉及到移位操作,所以增删快

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到新的数组中。

增加元素到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如何删除元素呢

删除元素和新增元素一样,都要涉及到移位操作,使用的都是数组拷贝的方式。

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位置的元素会被后面一个元素覆盖

目录
相关文章
|
13天前
|
存储 安全 Java
Android面试题之ArrayList源码详解
ArrayList是Java中基于数组实现的列表,提供O(1)的索引访问,但插入和删除操作平均时间复杂度为O(n)。默认容量为10,当需要时会通过System.arraycopy扩容。允许存储null,非线程安全。面试常问:List是接口,ArrayList是其实现之一,推荐使用List接口编程以实现更好的灵活性。更多详情见[ArrayList源码](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList.Node)。
12 2
|
14天前
|
存储
数据存储之数组的特点,长度固定,适应变化需求,集合类特点是空间可变,ArrayList泛型,ArrayList<String> array = new ArrayList<String>()
数据存储之数组的特点,长度固定,适应变化需求,集合类特点是空间可变,ArrayList泛型,ArrayList<String> array = new ArrayList<String>()
|
21天前
|
存储 安全 Java
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
17 0
|
24天前
|
存储 缓存 安全
java源码之String详解
java源码之String详解
16 0
|
29天前
|
Java Spring
深入解析Spring源码,揭示JDK动态代理的工作原理。
深入解析Spring源码,揭示JDK动态代理的工作原理。
22 0
|
1月前
|
安全 Java 数据安全/隐私保护
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
24 0
|
1月前
|
JSON 安全 Java
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
38 0
|
13天前
|
存储 算法 Java
Java面试之SpringCloud篇
Java面试之SpringCloud篇
30 1
|
13天前
|
缓存 NoSQL Redis
Java面试之redis篇
Java面试之redis篇
34 0
|
13天前
|
SQL 关系型数据库 MySQL
java面试之MySQL数据库篇
java面试之MySQL数据库篇
22 0
java面试之MySQL数据库篇