您的位置 首页 java

集合篇-ArrayList(JAVA)

前言

在官方jdk的文档中有这么一段话,大致的意思就是ArrayList是List接口的一种实现,该类是可调整大小的数组,并允许所有元素包括null值;这个类大致相当于Vector,只是它不是同步的(也就是存在在并发的情况下,会存在线程安全问题)。注:从上面文档中,可以证明ArrayList的数据结构是数组。

使用案例

 public class ArrayListDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("123");
        list.add("123");
        list.add("124");
        list.add("123");
        list.forEach(System.out::println);
    }
}  

运行后的效果:

源码剖析

1、大致看一下该类所提供的一些方法

2、从我们demo中的案例进行源码解析,先看看add方法

 //new ArrayList<>();创建个空的数组
public ArrayList() {
  //transient Object[] elementData; 
  //private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}  
 // java.util.ArrayList#add(E) add 添加元素
public boolean add(E e) {
  // 修改次数,只要涉及到操作,都会对该对象的值+1
    modCount++;
    add(e, elementData, size);
    return true;
}  
 //java.util.ArrayList#add(E, java.lang.Object[], int)
//
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
      //调整数组,可能需要调整数组长度,然后再重新copy一份数组出来,然后重新指定
        elementData = grow();
  //将元素放在数组最后
    elementData[s] = e;
    size = s + 1;
}  
 //java.util.ArrayList#grow()
private Object[] grow() {
  //size+1
    return grow(size + 1);
}  
 //java.util.ArrayList#grow(int)
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

//新的容量,也就是重新定义数组大小,这里就会涉及到扩容,minCapacity=size+1
private int newCapacity(int minCapacity) {
        // overflow-conscious code
  //先获取elementData数组的长度
        int oldCapacity = elementData.length;
  //oldCapacity + oldCapacity/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
  
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
              //private static final int DEFAULT_CAPACITY = 10;
              //所以一开始默认的数据长度是10
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
}  
 //java.util.Arrays#copyOf(T[], int)
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}  
 //java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}  
 //通过jndi调用java虚拟机中的本地方法。src源对象,从src源srcPos位置开始,dest目标对象,destPos目标位置,copy的元素长度,也就是多少个元素
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);  

从上面可以知道,其实ArrayList就是个数组来的,该类只是帮我们封装好一些处理方法,让我们可以更便捷的使用。下面我们再看该类中的其他public方法。

3、trimToSize

 //扩容后的多余未赋值的空间给去掉,简单的处理方法就是将实际存在的元素重新copy到另一个数据对象中,长度大小等于size
//这样的做法是为了减少没必要的内存空间
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}  

4、ensureCapacity

 //确保容量
public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}  

5、indexOf

 //返回元素在数组中的下标,也就是元素在数组中的位置,如果该元素不存在则返回-1
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}  
 // o需要查抄的对象,start起始位置,end结束位置
// 通过简单的遍历对比,时间复杂度为O(n)
int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}  

6、contains

 public boolean contains(Object o) {
    return indexOf(o) >= 0;
}  

7、lastIndexOf

 //查询元素存在数组中最末尾的位置,如果不存在则返回-1
public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}  
 int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = end - 1; i >= start; i--) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = end - 1; i >= start; i--) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}  

8、clone

 //深度克隆一个对象
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}  

9、toArray

 //返回一个数据
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}  

10、get

 public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}  
 E elementData(int index) {
    return (E) elementData[index];
}  

11、set

 //给某个位置的元素重新赋值,返回旧值
public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}  

12、java.util.ArrayList#remove(int)

 //删除index对应下标元素,返回以前的值,然后后面元素向前移
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}  
 private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}  

13、java.util.ArrayList#remove(java.lang.Object)

 public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
  // found是break found的一个标识,也就是说break后,从found出去。
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                  // 这里break后,就会跳到下面执行fastMove方法,而不是继续往下执行return false;句柄
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}  

上面是我们使用ArrayList对象常用的一些方法的简单解析。如果还有问题可以留言讨论

文章来源:智云一二三科技

文章标题:集合篇-ArrayList(JAVA)

文章地址:https://www.zhihuclub.com/182937.shtml

关于作者: 智云科技

热门文章

网站地图