JAVA ArrayList学习笔记

2018-05-31 本文已影响0人 luoyoub

ArrayList

ArrayList类支持能够按需增长的动态数组，增长策略oldCapacity + (oldCapacity >> 1)即原来的长度+原长度的一半

int newCapacity = oldCapacity + (oldCapacity >> 1);

默认容量大小是10

private static final int DEFAULT_CAPACITY = 10;

主要API

add(E e)
add主要的执行逻辑如下：
1）确保数组已使用长度（size）加1之后足够存下下一个数据
2）修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组，grow方法会将当前数组的长度变为原来容量的1.5倍。
```
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
```
3）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
4）返回添加成功布尔值；
```
public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
  }
```
add(int index, E element)

这里写图片描述

这个方法其实和上面的add类似，该方法可以按照元素的位置，指定位置插入元素，具体的执行逻辑如下：
1）确保数插入的位置小于等于当前数组长度，并且不小于0，否则抛出异常
2）确保数组已使用长度（size）加1之后足够存下下一个数据
3）修改次数modCount标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组
4）grow方法会将当前数组的长度变为原来容量的1.5倍。
5）确保有足够的容量之后，使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位。
6）将新的数据内容存放到数组的指定位置（index）上

grow()扩容

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

get(int index)

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

remove(int index)
根据索引remove
1）判断索引有没有越界
2）自增修改次数
3）将指定位置（index）上的元素保存到oldValue
4）将指定位置（index）后的元素都往前移动一位
5）将最后面的一个元素置空，好让垃圾回收器回收
6）将原来的值oldValue返回

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

注意：调用remove方法不会缩减数组的长度，只是将最后一个数组元素置空而已

trimToSize()缩小集合容量
toArray()将集合转换为数组

Arrays初始化

List list = Arrays.asList("a", "b");
List list = new ArrayList(){};

知识点

ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
ArrayList基于数组方式实现，无容量的限制（会扩容）
添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。添加删除某个索引的数据时，需要整体移动数组所以效率比较低
线程不安全
add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
remove(Object o)需要遍历数组
remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
contains(E)需要遍历数组
使用iterator遍历可能会引发多线程异常

中文排序

Collator collator = Collator.getInstance(Locale.CHINA);
List list = Arrays.asList("罗友宝", "黄慧", "阿伟", "车晓");
Collections.sort(list, collator);   
list.stream().forEach(System.err::println);

List和Set的区别

List和Set之间很重要的一个区别是是否允许重复元素的存在，在List中允许插入重复的元素，而在Set中不允许重复元素存在，即使插入相同元素也会进行替换；
List和Set之间另外一个很重要的区别与元素先后存放顺序有关。List是有序集合，而Set是无序集合。List会保留元素插入时的顺序，也就是说之前插入的元素的索引要比之后插入的元素的索引要小。而Set不会保留插入时的顺序；【PS：ArrayList中使用对象数组来存储对象，在每次插入新的对象时会插入到size大小处；至于HashSet，前面说到是通过HashMap来实现的，存入的对象作为HashMap的key，如果key相同会替换value。当然，SortedSet（继承了Set接口）能够以指定的排序方式来保存元素】
List可以通过下标来访问，而Set不能

JAVA ArrayList学习笔记

ArrayList

主要API

知识点

List和Set的区别

猜你喜欢

热点阅读