转载

【金三银四】ArrayList图解存储原理与数据结构揭秘

你好，早上、中午、下午、晚上好。我是辛巴哥。一名无缘985，日常996工程师。

今天我辛巴哥来教娜娜学ArrayList

开始快速

import java.util.ArrayList;
/****
 * 求关注 微信搜：Java大型网站架构
 */
public class ArrayListDemo {


    public static void main(String[] args) {
       ArrayList<String> arrayList= new ArrayList<String>();
       arrayList.add("辛巴");
       arrayList.add("娜娜");
       arrayList.add("微信搜：Java大型网站架构");
       for (String s:arrayList){
           System.out.println(s);
       }
    }
}
复制代码

大家在日常开发的中我们是这样去使用的，只要是java开发人员，无论你是1年工作还是10年工作。我相信Arraylist都是非常熟悉使用的。对我说的是熟悉使用，但是知道其底层实现的人就少很多了，这发生在我身边的事情，小编我现在在某大厂上班，经常面试一些工作5-6年的程序员，问问他们hashmap和arraylist底层实现，都知道是数组、链表、hash算法，但是细问下就露馅了，所以今天有必要和大家分享下arraylist底层实现。当然hashmap的底层实现我也讲过，可以看我之前的文章。

技术本质

很多老铁都知道arraylist底层是用数组为存储结构的。我们先来熟悉下数组

数组

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

Java代码表示

//数组:采用一段连续的存储单元来存储数据。
   //特点:指定下标O(1) 删除插入O（N） 数组：查询快 插入慢 ArrayList
   public static void main(String[] args) {
      Integer[] integers = new Integer[10];
      integers[0]=1;
      integers[1]=2;
      integers[2]=3;
      integers[9]=4;
复制代码

插入原理

我们熟悉了数组的特性之后，我们在回到刚才我们快速入门的代码，我们add三个字符串是怎么插入到我们数组里面去的了，是怎么插（吃啊插）入进去的了？我们来看下源码：

arrayList.add("辛巴"); arrayList.add("娜娜"); arrayList.add("微信搜：Java大型网站架构");

通过上述代码我们可以确定泛型e插入到elementData数组里并且size++。ensureCapacityInternal方法我们先放放等会说。

我们先说下说怎么插入到数组中，从0开始按顺序size++插入到数组中分别为：

如果有一天插入的数据不数组长度还多了怎么办？

扩容

刚才在add方法有ensureCapacityInternal方法还没说，这个方法我们来看下源码。

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
复制代码

源码意思：计算最小容量,DEFAULTCAPACITY_EMPTY_ELEMENTDATA（默认容量）是DEFAULTCAPACITY_EMPTY_ELEMENTDATA=10

算出最小容量在看下：

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
复制代码

传入最小容量值，修改+1。 minCapacity - elementData.length > 0判断需要的容量与默认容量的大小，差为负值是不需要扩容的。如果大于0说正数就需要扩容调用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);
    }
复制代码

源码意思：数组扩容第一个if条件是：首先把数组的长度赋给老的容量，也就是10，然后新的容量newCapacity=老的容量（10）+老的容量右移一位（5），第二个if条件是：如果新容量-(size+1)为负数，把size+1赋给新容量。如果新容量比数组的最大扩容量都大，会报异常，或者把最大的赋给它。如果都不是，就把新容量拷贝给数组，扩容完成。对应图如下：

删除原理

我们知道add插入的原理，删除其实也不难了吧。大致意思就是通过下表找到数组对应的对象让其为null，但是我们之前插入时扩容的数组怎么处理了？我们现在不需要这么多数据了呀？

下标位置删除：

public E remove(int index) {
        rangeCheck(index);／／检查index这个值是否有在size里面，保证其正确合法性
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;/ /将index+1以及之后的元素向前移动一位，覆盖被删除的值
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // 该对应下表值赋值为null。

        return oldValue;
    }
复制代码

对象元素删除：

指定元素删除:首先判断是否为空，空的时候直接删除

public boolean remove(Object o) {   
 //判断元素是否为空
 if (o == null) {   
     for (int index = 0; index < size; index++)    
         if (elementData[index] == null) { 
             fastRemove(index);      
             return true;    
         }   
 } else {     
     for (int index = 0; index < size; index++)   
         if (o.equals(elementData[index])) {  
             fastRemove(index);      
             return true;       
         }   
 }  
 //如果没有匹配元素，返回false
 return false;
}
复制代码

快速删除：不需要检测index，直接删除

private void fastRemove(int index) {   
modCount++;   
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
}
复制代码

总结：

现在知道为什么数组：插入删除慢，查询快（这个下篇文章证明）因为插入有可能需要库容。因为删除需要重新分配数组中数据元素。比如图中删除“娜娜” 娜娜下标为1，凡是在下标为1之后的元素都需要往前挪一个位置，这是件很可怕的事情。因为删除的元素越靠前，那就意味着需要挪动的数据就越多。因此数组插入和删除会变慢的原因在于此了明白的牛人点个赞或者回复下吧。

好了各位，以上就是这篇文章的全部内容了，能看到这里的人呀，都是牛人。白嫖不好，创作不易，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！