Skip to content

ArrayList

ArrayList是业务开发中最常用集合之一了,底层实现原理是数组,而数组是一块连续的内存空间,所以在查询时速度非常快。但是在新增和修改时速度慢一点。

为什么会在新增和修改的时候慢?

当元素数量超过当前数组的容量时,需要创建一个新的数组并将原有元素复制到新数组中。这个过程涉及到内存分配、数据复制等操作,因此新增元素时的效率较低。类似地,删除元素后,可能需要收缩数组,同样涉及到元素的复制和内存释放。

在极小的数据量下,查询、新增、修改之间的效率差别几乎可以忽略,只有在数据量大时才会有明显的感知

如果涉及到新增和修改,可以使用LinkedList,这个是基于链表实现的,新增和修改只需要调整相邻元素的指针指向即可,而不需要想数组一样移动大量的元素。

ArrayList初始化

在JDK1.7的版本中进行初始化时,会直接默认初始化容量为10。在JDK1.7之后呢,就默认走了空数组,只有在第一次添加元素时,才会初始化容量为10。

ArrayList扩容

以数组原长度的0.5倍进行扩容

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 注释: 10 >> 1 = 5

扩容方式

copy,复制

elementData = Arrays.copyOf(elementData, newCapacity);

ArrayList是非线程安全的

ArrayList不是线程安全的。如果想使用线程安全的数组容器,可以使用Vector或者使用Collections.synchronizedList包一下

Vector为什么是线程安全的?因为Vector的所有操作都加了synchronized了,所以使用Vector的效率非常低

ArrayList和LinkedList

  • ArrayList 查询速度快,新增和删除效率低
  • LinkedList 查询效率低,但是新增和删除效率高。

LinkedList原理 LinkedList的底层是一个一个的节点,节点之间通过next和prev节点连接🔗起来。(LinkedList需要存储额外的指针信息,这会导致在一定程度上占用更多的内存空间。)

private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

所以从底层的实现来讲,相较于ArrayList,查找会慢一点。但是LinkedList的新增和删除会很快,因为只需要改变next和prev的指向就可以了。

最后

不存在一个集合工具是查询效率又高,增删效率也高的,还线程安全的。因为数据结构的特性就是优劣共存的,想找个平衡点很难,牺牲了性能,那就安全,牺牲了安全那就快速。

网站当前构建日期: 2024.07.18