ArrayList和Array、ArrayList和LinkedList、ArrayList扩容机制、 HashSet、LinkedHashSet和TreeSet |
您所在的位置：网站首页 › arraylist和linkedlist的扩容机制 › ArrayList和Array、ArrayList和LinkedList、ArrayList扩容机制、 HashSet、LinkedHashSet和TreeSet |
|
目录 List ArrayList和Array ArrayList和LinkedList ArrayList扩容机制 Vector和CopyOnwriteArrayList 线程安全 Set HashSet、LinkedHashSet和TreeSet List ArrayList和Array ArrayList是动态数组，创建时可以不指定长度，并且可以动态扩容，可以使用泛型，只能存储对象，基本类型需要使用包装类。 Array是静态数组，创建时必须指定长度，一旦创建，长度不能改变，不能使用泛型，可以存储对象和基本类型。 ArrayList和LinkedListArrayList 底层是Object数组，支持通过下标访问(内存地址连续)，内存空间上，尾部会预留扩容空间。 LinkedList底层是双向链表，不支持通过下标访问(内存地址不连续)，内存空间上，存储每个元素需要存储前驱后继节点。使用场景较少，可以使用ArrayList代替。 ArrayList扩容机制默认无参构造器 private static final Object[] EMPTY_ELEMENTDATA = {}; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }默认初始容量10 private static final int DEFAULT_CAPACITY = 10;使用无参构造器创建 ArrayList 时，实际上初始化的是一个空数组。 只有当真正对数组进行添加元素操作时，才真正分配容量（即向数组中添加第一个元素时，数组容量扩为 10）核心源码 /** * 默认扩容上限 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 扩容的核心方法。 */ private void grow(int minCapacity) { // oldCapacity扩容前的旧容量 int oldCapacity = elementData.length; // 将新容量更新为旧容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容之后如果还不够需要的最小容量，则以需要的最小容量minCapacity作为新容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //判断新容量有没有达到默认的扩容上限，防止内存溢出 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 复制旧数组到扩容后的新数组 elementData = Arrays.copyOf(elementData, newCapacity); }扩容上限的问题 private static int hugeCapacity(int minCapacity) { //判断是否已经发生了内存溢出 if (minCapacity < 0) throw new OutOfMemoryError(); //如果大于默认的最大值，则返回Integer的最大值 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }指定扩容的容量，这个方法是外部可以调用的 /** * 外部可以自定义扩容 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }总结： 1、无参构造器创建ArrayList，只创建一个空数组。 2、向当前数组添加元素，第一次添加会扩容到默认容量10。 3、当添加第11个元素时，扩容1.5倍。10+10>>2 4、当达到默认扩容上限Integer.MAX_VALUE - 8，防止内存溢出，将上限扩为Integer.MAX_VALUE ，即2^31-1=2147483647。补充：源码里向外部暴露了自定义扩容的方法ensureCapacity，在处理大量数据时，可提前自定义扩容，来减少自动扩容的开销。 Vector和CopyOnwriteArrayList 线程安全Vector使用同步锁Synchronized实现线程安全，性能非常低下。 CopyOnWriteArraylist使用了ReentrantLock锁，搭配COW(Copy-On-Write)策略(写时复制)，读取操作是完全不用加锁，写也不会阻塞读操作，只有写写才会互斥。这样一来，读操作的性能就可以大幅度提升。 当需要修改时，会将原数组复制一份，去做修改操作，修改完成之后，再将引用指向新的数组。 // 插入元素 public boolean add(E e) { final ReentrantLock lock = this.lock; // 使用ReentrantLock加锁 lock.lock(); try { // 得到原数组 Object[] elements = getArray(); int len = elements.length; // 复制原数组，给新数组长度+1 Object[] newElements = Arrays.copyOf(elements, len + 1); // 插入尾部 newElements[len] = e; // 引用指向新数组 setArray(newElements); return true; } finally { // 解锁 lock.unlock(); } } Set HashSet、LinkedHashSet和TreeSetHashSet基于HashMap实现，底层是哈希表，具有无序性。 LinkedHashset继承HashSet,使用链表按照插入顺序排序。 TreeSet底层是红黑树，使用自定义比较器来排序，使用更加灵活。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |