作者: Stanley 罗昊
集合分为三个系列, 分别为: List,set,map
List 系列
特点: 元素有序可重复
有序指的是元素的添加顺序, 也就是说, 元素被第一个存进去的时候, 它就在第一位, 这就是 list 集合的元素添加顺序;
通常情况下我们所说的有序有两个概念, 第一个是添加顺序, 第二个是大小顺序 (实际上就是元素值的大小)
List 下面重点关注两个实现类分别是:
- ArrayList LinkedList
- ArrayList
ArrayList 底层实现是数组, 既然是数组, 那它就必然有数组的特点: 查找快, 增删慢;
这里简单解释一下:
首先我们建立一个数组, 一旦建立一个数组, 那么程序就会在内存中开辟一个连续的内存存储空间, 并且它是有下标的, 从 0 开始, 一旦定义长度就无法发生改变.
现在, 假设我们往数组里面存值, 当然是你定义什么类型, 你就存什么类型的值进去, 如果现在想获取, 我们直接通过下标就可以进行获取了, 但是我删除元素的时候, 是怎么删除的呢?
数组删除过程
假设我定义一个数组如下图:
红框内, 代表我存的值, 黑线上方则是他们值对应的下标
假设我现在想删除 c 这个元素, 这个时候 d 就会向前移动 e 也会移到 d 的位置 f 也会移到 e 的位置上, 结果后面会空出来的那个就被删掉了, 结果就成了下面这张图 B-1:
这个就是数组的删除过程.
数组添加过程
刚讲了删除过程, 现在我们就来看看数组的添加过程:
添加元素首先会给即将进来的这个元素分配一个空间在如图 B-1f 后面, 如果你想添加到如图 B-1 下标为 1 的空间里, 那么它就会开始依次向后移, b 占领 d 的位置 d 占领 e 的位置 f 占领后面新开辟空间的位置上.
这就是它的增加与删除过程, 所以它增删慢, 查询快;
那既然我刚讲了, 数组一旦定义, 长度不能发生改变, 那么在咱们 List 集合底层是数组实现的, 你 List 集合定义的时候你给过长度吗? 很显然并没有给长度, 那就可以无限添加元素, 你填 100 个也行, 你添 10k 也无所谓, 既然数组长度不变, 你说它底层怎么搞的呢? 接下来我们就定义一个数组并且查看它的底层代码.
List 集合底层源码详解
我用的是 IDEA, 按两下 Shift 键输入 ArrayList 回车即可查看源码, 首先刚进来我们看到的是版本号:
- private static final long serialVersionUID = 8683452581122892189L;// 版本号
- /**
- * Default initial capacity.(默认初始容量, 也就说, 当我们定义一个 List 集合没有给他指定长度的时候, 默认长度就是 10)
- */
- private static final int DEFAULT_CAPACITY = 10;
那如果我添加 11 元素的时候怎么办?
答: 扩容, 下面我会详讲扩容
刚开始建这个集合的时候, 默认长度是 10
- /**
- * Increases the capacity to ensure that it can hold at least the
- * number of elements specified by the minimum capacity argument.
- *
- * @param minCapacity the desired minimum capacity
- */
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;// 你现在数组的长度
- int newCapacity = oldCapacity + (oldCapacity>> 1);// 新数组的长度 = oldCapacity + (oldCapacity>> 1) 其中 >> 符号是右移符, 也就是 / 2 的意思, 算出来的结果是 1.5, 所以它扩容的时候是 1.5 倍 1.5 倍的扩的
- if (newCapacity - minCapacity <0)
- newCapacity = minCapacity;
- if (newCapacity - MAX_ARRAY_SIZE> 0)(按住 Ctrl 键 点进去 MAX_ARRAY_SIZE 就可以查看数组的最大容量, 下面我有详讲)
- newCapacity = hugeCapacity(minCapacity);
- // minCapacity is usually close to size, so this is a win:
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
上面这个源码, 就是数组初始化与扩容的方法, 也就是说 ArrayList 里面它数组初始化是在你添加第一个元素的时候, 当它扩完容后接下来就是数组的拷贝
你在创建 List 集合的时候, 你也可以给它传一个初始容量, 如何操作请继续向下阅读.
在 ArrayList 集合底层源码里有一个有参构造跟无参构造, 它们分别在什么时候使用呢?
首先先看一下有参构造:
- /**
- * Constructs an empty list with the specified initial capacity.
- *
- * @param initialCapacity the initial capacity of the list
- * @throws IllegalArgumentException if the specified initial capacity
- * is negative
- */
- public ArrayList(int initialCapacity) {
- if (initialCapacity> 0) {
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);
- }
- }
什么时候用有参构造: 当你向集合中添加元素数量比较多的时候, 你最好给它指定初始容量, 因为这样就可以减少很多次的扩容和元素拷贝.
原理: 如果你 10000 个元素, 你让它 10 个以上扩一次容, 扩完容后你再让它连续扩容必然会造成元素拷贝, 元素拷贝它的性能就高不了, 这样如此反复的话必然会拉低它的性能, 如果你元素过多的话, 你给它指定初始容量, 这样我就能减少了很多次扩容和元素拷贝, 从而提升性能 (在一定程度上提升性能),
当元素比较少的时候, 你就可以默认不指定初始容量
ArrayList 容量有上限吗?
元素是有上限的, 它的容量是 Integer 的最大值, 在源码里面可以清楚的看到它的设定:
- /**
- * The maximum size of array to allocate.
- * Some VMs reserve some header words in an array.
- * Attempts to allocate larger arrays may result in
- * OutOfMemoryError: Requested array size exceeds VM limit
- */
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;(写的很清楚, 它的大小不能超过 Integer 的最大值 (21 亿))
我们可以看到它减了一个 8, 因为到后期就已经不需要扩容了, 最后几个元素它是一个一个添加的, 添加一个扩一个容, 添加一个扩一个容.
值得一提的是, 当它的容量超过 10 亿后, 性能就有所衰减, 这个实验是有人做过的, 也被证实了, 10 亿之前它的性能都表现良好.
今日感悟:
很多人辞职的时候都会被老板挽留, 误认以为自己是公司里不可取代的人, 可实际上, 没有人的工作是不可取代的.
老板在你辞职的时候挽留你, 不过是说明: 你是在可以取代你的那群人中, 价格最便宜的.
--- 恢复内容结束 ---
来源: https://www.cnblogs.com/StanleyBlogs/p/10396253.html