服务器之家

服务器之家 > 正文

Java中ArrayList的工作原理详解

时间:2020-08-24 10:46     来源/作者:躲在魚缸里的徐小波

1.ArrayList

以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组。因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。按数组下标访问元素-get(i)、set(i,e)的性能很高,这是数组的基本优势。如果按下标插入元素、删除元素-add(i,e)、remove(i)、remove(e),则要用System.arraycopy()来复制移动部分受影响的元素,性能就变差了。越是前面的元素,修改时要移动的元素越多。直接在数组末尾加入元素-常用的add(e),删除最后一个元素则无影响。

ArrayList是一个相对来说比较简单的数据结构,最重要的一点就是它的自动扩容。

2.构造方法

ArrayList提供了三个构造方法:

?
1
2
3
ArrayList(int initialCapacity):指定容量
ArrayList():构造一个默认容量为10的ArrayList
ArrayList(Collection<? extends E> c):构造一个指定Collection的ArrayList

3.add

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 添加指定元素到list末尾
 public boolean add(E e) {
   // 检查是否需要扩容
   ensureCapacityInternal(size + 1); // Increments modCount!!
   // 赋值
   elementData[size++] = e;
   return true;
 }
 private void ensureCapacityInternal(int minCapacity) {
   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     // 比较默认的容量10和传入的容量,返回大点的数
     minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
   }
   //扩容
   ensureExplicitCapacity(minCapacity);
 }
 private void ensureExplicitCapacity(int minCapacity) {
   // 记录修改次数
   modCount++;
   // overflow-conscious code
   if (minCapacity - elementData.length > 0)
     grow(minCapacity);
 }
 private void grow(int minCapacity) {
   // overflow-conscious code
   // 记录当前list的容量
   int oldCapacity = elementData.length;
   // 扩展为原来的1.5倍
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   // 如果扩展1.5倍还不能满足,直接扩展为需求值
   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);
 }

也就是说,当增加数据的时候,如果ArrayList的大小已经不满足需求时,那么数组大小就会变为原来的1.5倍,之后就是把老的数据拷贝新的数组里面。例如我创建的list的容量时10,当我们已经添加了10个元素的之后,再添加就会进行自动扩容到15。

get,set

?
1
2
3
4
5
6
7
8
9
10
public E get(int index) {
  rangeCheck(index);
  return elementData(index);
}
public E set(int index, E element) {
  rangeCheck(index);
  E oldValue = elementData(index);
  elementData[index] = element;
  return oldValue;
}

get()和set()就比较简单了,进行范围检查后就可以进行对应的操作了。由于ArrayList是动态数组,所以我们完全可以根据下标来获取ArrayList中的元素,而且速度还比较快,故ArrayList长于随机访问。

remove

?
1
2
3
4
5
6
7
8
9
10
11
public E remove(int index) {
  rangeCheck(index);
  modCount++;
  E oldValue = elementData(index);
  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
  return oldValue;
}

remove()首先进行范围检查,然后计算移动的开始位置,如果大于0的话就进行移动并返回旧值

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持服务器之家!

原文链接:http://www.cnblogs.com/lebo0425/p/6504658.html

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
返回顶部