2021-02-25 11:39 已编辑阿里巴巴_阿里云弹性计算_基础平台开发工程师

关注

JAVA面试必问之Collection要点

JAVA集合之Collection

JAVA提供的数组是用来存储固定大小的同类型元素。其具有以下两个缺点：
1.数组一旦初始化后，长度就确定了，无法进行数组的动态扩展；
2.数组存储元素是确定的，且一个数组中只能存储同一类型的。
为了改进以上缺点，JAVA提供了一个集合框架供我们使用，其中最主要的接口为Collection和Map，集合框架图如下：

集合和数组的区别

属性	数组	集合
长度	固定	动态扩展
存储内容	同一类型元素	不同类型元素（但一般不会这样做）
存储元素类型	基本类型和引用类型	引用类型

Collection常用方法

方法名	说明
boolean add(E e)	向集合添加元素e，若指定集合元素改变了则返回true
boolean addAll(Collection<? extends E> c)	把集合C中的元素全部添加到集合中，若指定集合元素改变返回true（相当于集合取并）
void clear()	清空所有集合元素
boolean contains(Object o)	判断指定集合是否包含对象o
boolean containsAll(Collection<?> c)	判断指定集合是否包含集合c的所有元素
boolean isEmpty()	判断指定集合的元素size是否为0
boolean remove(Object o)	删除集合中的元素对象o,若集合有多个o元素，则只会删除第一个元素
boolean removeAll(Collection<?> c）	删除指定集合包含集合c的元素（集合取补）
boolean retainAll(Collection<?> c)	从指定集合中保留包含集合c的元素,其他元素则删除（集合取交）
int size()	集合的元素个数
T[] toArray(T[] a)	将集合转换为T类型的数组
Interator it = collection.iterator()	获取集合迭代器

Collection中的List

Collection中的List常用的实现类有两个：ArrayList和LinkedList。其两者区别如下：

属性	ArrayList	LinkedList
扩容方式	1.5倍扩容	直接增加
默认空实例初始化方式	懒惰（即第一次添加元素之后才初始化数组，之前任为空数组）	不同类型元素（但一般不会这样做）
初始容量	10	引用类型
支持随机访问	是	否
随机访问的时间复杂度	O(1)	O(n)
增删元素的时间复杂度	O(n)	O(1)
内存要求	必须连续	不连续

ArrayList源码部分分析

ArrayList源码比较长，在这里不全部展示，只挑选一些经典方法进行分析。

从源码中可以看出ArrayList 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。　　
ArrayList 实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。　　
ArrayList 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。

ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。

1.ArrayList初始化

  // 默认初始容量大小为10
  private static final int DEFAULT_CAPACITY = 10;
  //默认空实例
  private static final Object[] EMPTY_ELEMENTDATA = {};

   //用于默认大小空实例的共享空数组实例。
    //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  //保存ArrayList数据的数组，即ArrayList底层实际上还是一个数组
  transient Object[] elementData; 

  //ArrayList 所包含的元素个数
  private int size;

  //带初始容量参数的构造函数。（用户自己指定容量）
  public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
          //创建initialCapacity大小的数组
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
          //创建空数组
          this.elementData = EMPTY_ELEMENTDATA;
      } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }

  //默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
  public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

2.扩容机制

ArrayList的扩容机制提高了性能，如果每次只扩充一个，那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制使用每次扩容1.5倍大小的方式避免了这种情况。

   //扩容函数，确保ArrayList能容纳元素，其中minCapacity 为所需的最小容量
  public void ensureCapacity(int minCapacity) {
      //若当前ArrayList还没有初始化时，minExpand=0
      int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
      //若所需大于当前的容量，则扩容
      if (minCapacity > minExpand) {
          ensureExplicitCapacity(minCapacity);
      }
  }
 //得到最小扩容量
  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 获取默认的容量和传入参数的较大值
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }

      ensureExplicitCapacity(minCapacity);
  }
//判断是否需要扩容
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

  // 如果说minCapacity也就是所需的最小容量大于保存ArrayList数据的数组的长度的话，就需要调用grow(minCapacity)方法扩容。 
  //这个minCapacity到底为多少呢？举个例子在添加元素(add)方法中这个minCapacity的大小就为现在数组的长度加1
      if (minCapacity - elementData.length > 0)
          //调用grow方法进行扩容，调用此方法代表已经开始扩容了
          grow(minCapacity);
  }

  //要分配的最大数组大小
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  //ArrayList扩容的核心方法。
  private void grow(int minCapacity) {
      // oldCapacity为旧容量，newCapacity为新容量
      int oldCapacity = elementData.length;
      //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
      //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      //再检查新容量是否超出了ArrayList所定义的最大容量，
      //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
      //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);

      elementData = Arrays.copyOf(elementData, newCapacity);
  }
  //比较minCapacity和 MAX_ARRAY_SIZE
  private static int hugeCapacity(int minCapacity) {
      if (minCapacity < 0) 
          throw new OutOfMemoryError();
      return (minCapacity > MAX_ARRAY_SIZE) ?
          Integer.MAX_VALUE :
          MAX_ARRAY_SIZE;
  }

ArrayList中的数组拷贝方法：System.arraycopy()和Arrays.copyof()

在ArrayList的add(int index, E element)方法中使用到了 arraycopy() 方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:

    //在此列表中的指定位置插入指定的元素。
    public void add(int index, E element) {
        //先调用 rangeCheckForAdd 对index进行界限检查
        rangeCheckForAdd(index);
        //然后调用 ensureCapacityInternal 方法保证capacity足够大
        ensureCapacityInternal(size + 1);  
        //arraycopy()方法实现数组自己复制自己:从最后开始将成员后移一个位置，直到将element插入index位置；最后size加1
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

在ArrayList的toArray()方法中用到了 copyOf() 方法：

    //以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
     //该方法必须分配一个新的数组
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData, size);
    }

以上二者的联系：看两者源代码可以发现copyOf()内部调用了System.arraycopy()方法
以上二者的区别：arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位；copyOf()是系统自动在内部新建一个数组，并返回该数组。

LinkedList源码部分分析

LinkedList是一个实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性; LinkedList不是线程安全的。

LinkedList的内部节点Node

LinkedList会将存入的对象包装为一个节点Node，并记录其前驱节点和后继节点，因此LinkedList是一个双端队列，其插入和删除都可以指明方向。

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;
        }
    }

LinkedList的增加元素的方法

add（E e）：将元素添加到链表尾部

public boolean add(E e) {
        linkLast(e);//这里就只调用了这一个方法
        return true;
    }

   //linkLast方法：链接使e作为最后一个元素。
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;//新建节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;//指向后继元素也就是指向下一个元素
        size++;
        modCount++;
    }

addFirst(E e)：将元素添加到链表头部

 public void addFirst(E e) {
        linkFirst(e);
    }
//linkFirst方法：链接使e作为第一个元素。
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);//新建节点，以头节点为后继节点
        first = newNode;
        //如果链表为空，last节点也指向该节点
        if (f == null)
            last = newNode;
        //否则，将头节点的前驱指针指向新节点，也就是指向前一个元素
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

addLast(E e)：将元素添加到链表尾部，与 add(E e) 方法一样
```
public void addLast(E e) {
      linkLast(e);
  }
```

add(int index, E e):在指定位置添加元素

public void add(int index, E element) {
      checkPositionIndex(index); //检查索引是否处于[0-size]之间

      if (index == size)//添加在链表尾部
          linkLast(element);
      else//添加在链表中间
          linkBefore(element, node(index));
  }
//返回下标为index的node节点
Node<E> node(int index) {
  //使用对半查找，如果在index前半部分，则从头部使用next开始找
  if (index < (size >> 1)) {
      Node<E> x = first;
      for (int i = 0; i < index; i++)
          x = x.next;
      return x;
  } else { //如果在index后半部分，则从尾部prev开始找
      Node<E> x = last;
      for (int i = size - 1; i > index; i--)
          x = x.prev;
      return x;
  }
}

LinkedList的获取元素的方法

根据索引获取元素

get(int index)：根据指定索引返回数据

public E get(int index) {
      //检查index范围是否在size之内
      checkElementIndex(index);
      //调用Node(index)去找到index对应的node然后返回它的值(node源码见上)
      return node(index).item;
  }

获取头节点

getFirst():获取链表头节点，若链表为空抛出异常；
element():本质就是getFirst(),性质同上。
peekFirst():获取链表头节点，若链表为空返回null；
peek():本质就是peekFirst()，性质同上；

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
public E element() {
    return getFirst();
}

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

获取尾节点

getLast()：获取尾节点，在链表为空时，会抛出NoSuchElementException；

peekLast() : 获取尾节点，在链表为空时，返回null;

public E getLast() {
  final Node<E> l = last;
  if (l == null)
      throw new NoSuchElementException();
  return l.item;
}
public E peekLast() {
  final Node<E> l = last;
  return (l == null) ? null : l.item;
}

根据对象获取对应索引

int indexOf(Object o)：从头遍历找

public int indexOf(Object o) {
  int index = 0;
  if (o == null) {
      //从头遍历
      for (Node<E> x = first; x != null; x = x.next) {
          if (x.item == null)
              return index;
          index++;
      }
  } else {
      //从头遍历
      for (Node<E> x = first; x != null; x = x.next) {
          if (o.equals(x.item))
              return index;
          index++;
      }
  }
  return -1;
}

int lastIndexOf(Object o)：从尾遍历找

public int lastIndexOf(Object o) {
  int index = size;
  if (o == null) {
      //从尾遍历
      for (Node<E> x = last; x != null; x = x.prev) {
          index--;
          if (x.item == null)
              return index;
      }
  } else {
      //从尾遍历
      for (Node<E> x = last; x != null; x = x.prev) {
          index--;
          if (o.equals(x.item))
              return index;
      }
  }
  return -1;
}

LinkedList检查是否包含某对象的方法

contains(Object o)：检查对象o是否存在于链表中
```
public boolean contains(Object o) {
  return indexOf(o) != -1;
}
```
LinkedList删除元素
remove() ,removeFirst(),pop(): 删除头节点，本质都是removeFirst()，若为空链表则抛出异常；
removeLast(),pollLast(): 删除尾节点，区别在于在空链表时前者抛出异常，后者只返回null；
remove(Object o): 删除指定元素，且一次只会删除一个匹配的对象，如果删除了匹配对象，返回true，否则false。
remove(int index)：删除指定位置的元素

ArrayList和LinkedList的线性安全

ArrayList和LinkedList都不是线性安全，如果想要使用线性安全的集合，可以调用静态类Collections类中的synchronizedList方法，在里面传入相应的集合。例子如下：

List list=Collections.synchronizedList(new LinkedList(...));

最后是广告时间~
我们阿里云最核心部门弹性计算21年暑假实习招聘还在火热进行中。我可继续帮助大家内推简历。收到同学们的简历后，会进行评估，合适的话后续会由面试官进行进一步的交流！所以欢迎大家踊跃投递，越早投递越先人一步抓住机会！

部门简介：
这里是阿里云最核心的ECS团队，这里能接触到众多大佬，与王坚院士做同事！在这里你将体验极致性能与架构的复杂挑战；在这里你将体验超大规模集群调度及管理。暑期实习可能是你最容易进入阿里的渠道！同学们也可提前了解下阿里云，阿里云官方网站： https://www.aliyun.com/ ，看看弹性计算的位置就知道我们的部门有多么的核心！而且在实习期间每位实习生都会分配师兄一对一负责，帮助实习生更快更好的成长，能够参与甚至负责具有挑战性的实习项目！

招聘对象及要求：
毕业于985/211或者海外知名高校，计算机或相关专业，2021年11月-2022年10月毕业，具备良好的计算机专业基础，包括操作系统与计算机网络，熟悉常见的数据结构和算法；熟悉至少一种编程语言，包括但不限于Java、C++、JavaScript、Golang、Python、Node.js、Php、C#、Rust、Typescript或者操作系统开发。

招聘岗位：
研发工程师java
研发工程师C++
Web前端开发工程师
算法工程师-机器学习
算法工程师
基础平台研发工程师
数据挖掘分析
实习地点：北京/杭州任选

投递邮箱：kate_yan4@163.com (我是2020年的转正的实习生，因为离职后公司邮箱冻结了，只能先用个人邮箱啦😂)

注：邮件名称或备注请按“职位+学校+姓名+手机号+实习地点”格式，因工作时间，每天在饭后及早晚集中处理大家邮件，有任何问题可以直接留言或私聊我。投递成功后也在请帖子下面回复“已投递”

#内推##实习##阿里巴巴##春招##字节跳动##腾讯##面经#