1，常见数据结构-数组

基础知识

数组是具有相同类型的数据的集合，也就是说数组的所有元素的类型都是相同的，在所有的数据结构中，数组算是最常见也是最简单的一种数据结构，我们最常见的也就是一维数组，当然还有二维，三维……，数组需要先声明才能使用，数组的大小一旦确定就不可以在变了。比如我们声明一个长度为10的数组

    int[] array = new int[10];

数组的下标是从0开始的，比如上面数组的第一个元素是array[0]，最后一个元素是array[9]。

在这里插入图片描述

我们还可以在声明的时候直接对他进行初始化，比如

    int[] array = new int[]{1, 2, 3};

上面我们声明了一个长度为3的数组。

源码分析

操作数组的类我们常见的估计也就是ArrayList了，他对数组的操作非常简单，所有的数据都会存放到这个数组中

    transient Object[] elementData;

我们来看一下他常见的几个方法，首先是get方法

    public E get(int index) {
     if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

      return (E) elementData[index];
    }

首先判断是否越界，如果越界直接抛异常，否则就根据他的下标从数组中直接返回，在看一下他的set方法

    public E set(int index, E element) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

         E oldValue = (E) elementData[index];
         elementData[index] = element;
     return oldValue;
    }

和get方法一样，也是先判断是否越界，然后再操作，代码比较简单，我们再来看一个add方法

    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
           size++;
        }

这里也是先判断是否越界，然后再判断是否需要扩容，最后在操作，接着我们来看一下ensureCapacityInternal方法

    private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

       ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

       // overflow-conscious code
        if (minCapacity - elementData.length > 0)
           grow(minCapacity);
    }

他的默认初始化大小是10

    private static final int DEFAULT_CAPACITY = 10;

上面代码第13行，如果我们需要的空间大于数组长度的时候，说明数组不够用了，要进行扩容，就会执行下面的grow方法，我们来看一下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);
    }

代码也比较简单，扩容的时候在第4行还会增加一半的大小，比如原来数组大小是10，第一次扩容后会是15。在ArrayList中无论使用add还是remove都会使用这样一个方法

        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);

这说明对数组的查找是比较方便的，但对数组的增删就没那么方便了，因为数组是一块连续的内存空间，如果在前面增加和删除，都会导致后面元素位置的变动。

ArraList是线程不安全，如果使用线程安全的可以用Vector，还有一个线程安全的类

CopyOnWriteArrayList，他只在add和remove的时候，也就是修改数据的时候会先synchronized，在get的时候没有，我们来看一下代码

    private E get(Object[] a, int index) {
       return (E) a[index];
    }

我们再来看一下他的add方法

    public boolean add(E e) {
        synchronized (lock) {
            Object[] elements = getArray();
           int len = elements.length;
           Object[] newElements = Arrays.copyOf(elements, len + 1);
           newElements[len] = e;
           setArray(newElements);
           return true;
       }
    }

他不像ArrayList每次扩容的时候，size都会增加一半，他是每次add一个元素的时候size只会加1，同理remove的时候size只会减1。