探索Java集合框架—数据结构、ArrayList集合

一、背景介绍

Java集合的使用相信大家都已经非常得心应手，但是我们怎么做到知其然，更知其所以然这种出神入化的境界呢？我们揭开集合框架底层神秘面纱来一探究竟

二、思路&方案

在说集合之前我们要先了解数据结构这一概念

数据结构是什么？

数据结构时对数据进行组织和存储一种方式，数据使用不同的数据结构组织和存储时所带来的时间和空间性能也是不同的。List、Set、Map集合背后使用了不同的数据结构，我们理解为集合是一种数据结构的具体实现。例如：可以使用数组结构来实现集合，当访问数组元素的时候通过数组下标查找时更快。

程序=数据结构+算法。数据结构还提供了一些各种查找、排序算法，集合可以用来解决一堆数据的处理问题，如：查找、排序、去重等等

数据结构可以分为线性和非线性两种数据结构

线性数据结构：

特点：

一对一的关系并且逻辑上有序，数据元素之间存在一个前后关系，每个元素只有一个直接前驱和一个直接后去

组成：

• 数组（Array）：相同类型元素并且连续存储
• 链表（LinkedList）：一系列node节点，每个节点包括数据、指向下一个节点的指针
• 栈（Stack）：先进后出(LIFO)，在栈顶进行删除和插入操作
• 队列（Queue）：先进先出（FIFO），在队尾插入、对头删除元素

非线性数据结构：

特点：

多对多关系，数据元素之间不存在直接的前后关系，元素和元素之间通过指针相连，

包括：

• 树（Tree）：一组node节点组成，每个父节点下级可以有子节点，节点之间是上下层次关系
• 图（Graph）：一组节点、边之间的关系
• 堆（Heap）：实现优先队列
• 散列表（Hash Table）：根据关键字可以直接查询数据，通过散列函数确认存储位置

结合上面讲到的数据结构，我们来看下Java究竟是如何应用的

Java集合分类

集合相关类和接口都在java.util中，从宏观上我们把Java集合分为了以Collection为中心的实现类、以Map为中心的实现类， Collection和Map两个接口下面分别有不同的实现类，它们都是用来存储和操作数据的集合

Collection接口：

特点：

一组对象的集合，通过索引或迭代器访问元素，元素可以重复

包括：

• List：有序集合
• Set：无序集合
• Queue：先进先出集合

Map接口：

特点：

键值对映射的集合，通过key查找value，每个key是唯一的

包括：

• HashMap：通过哈希表实现，无序
• TreeMap：基于红黑树实现，有序
• LinkedHashMap：哈希表+双向链表实现，顺序插入

今天先重点来讲讲List集合中ArrayList增删改查是如何实现的

三、过程

ArrayList和LinkedList的区别有哪些？

ArrayList是如何存储数据的？

底层是数组，数组存储的数据的特点是元素类型相同并且数组容量固定

数组存储容量固定？那在实际业务场景中数据肯定是不固定的呀？如何解决？

ArrayList扩容机制

ArrayList提供了自动扩容机制，当插入数据时候底层会先判断是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容，反之。

①、如何进行扩容的？

ArrayList内部封装了一个动态再分配的对象数组，ArrayList的底层数据库初始容量为10，扩容因子为1.5

②、增加元素

当我们第一次添加元素使用add（）方法添加元素的过程中，底层的流程是这样的：

内部会调用ensureExplicitCapacity（）方法判断添加元素之后的数组长度是否大于数组容量，如果超出数组容量调用grow（）方法扩容，否则给数组长度+1

当第一次对数组进行add添加元素的时候，才会把内部的数组扩容为10，这也是数组的第一次扩容

** 注意：**

• 数组长度是指当前数组内元素的个数
• 数组容量是指数组所能容纳的长度

示意图：

那如果要添加的元素不足数组容量呢？现在我们来看下具体是如何扩容的？

假设场景：数组中已经有10个元素，需要添加第11个元素

**calculateCapacity方法内部首先会判断elementData数组是否是默认的空数组（看是否往数组里面添加了元素），如果不是默认数组则返回添加元素之后数组所需要的长度**

如果添加元素之后的数组长度超出了数组容量，则说明需要扩容，调用grow（）方法进行扩容

** grow（）方法内部会调用一个交copyOf方法进行扩容，会创建一个1.5倍的新数组，将原来的数组元素挪到新数组中**

此时ArrayList扩容为原来的大小+原来大小/2=10+5=15，数组扩容后容量为15

扩容后的数组示意图如下：

add(E e)添加元素的流程为：

第一步、判断是否需要扩容：

    需要扩容

            ①、计算新数组容量：newCapacity = oldCapacity + (oldCapacity >> 1)

            ②、创建新数组：elementData = Arrays.copyOf(elementData, newCapacity)

第二步、追加元素到数组末尾 。 elementData[size++] =element;

第三步、添加成功

③、ArrayList给指定位置插入元素

示例：

添加指定位置流程如下：

第一步、检查下标是否越界

    越界：抛出

IndexOutOfBoundsException

异常

第二步、判断是否需要扩容，如果需要扩容则扩容

**第三步、后移元素.**从指定要插入元素位置依次向后移动一个位置，此时指定要插入的位置为空

第四步、插入新元素。将要插入的元素放入指定位置

第五步、更新数组大小。size+1

注意： 其中rangeCheckForAdd(index)方法会检查下标是否越界，如果要插入的元素位置超出了当前数组的容量，会抛出”IndexOutOfBoundsException“的异常

示意图：

④、删除元素

按照下标位置删除元素

按照内容删除元素

四、总结

通过分析源码我们了解了ArrayList底层增删改查操作具体的细节，再次总结