ArrayList 源码分析
发布时间:2020-12-15 07:52:12 所属栏目:Java 来源:网络整理
导读:目录 ArrayList 源码分析 1. 数组介绍 2. ArrayList 源码分析 ArrayList 源码分析 1. 数组介绍 数组是数据结构中很基本的结构,很多编程语言都内置数组。 在 Java 中当创建数组时会在内存中划分一块连续的内存,然后当有数据进入的时候会将数据按顺序的存储
目录
ArrayList 源码分析1. 数组介绍数组是数据结构中很基本的结构,很多编程语言都内置数组。 在 Java 中当创建数组时会在内存中划分一块连续的内存,然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时,需要提供数组中的索引,然后数组根据索引将内存中的数据取出来,返回给读取程序。在 Java 中并不是所有的数据都能存储到数组中,只有相同类型的数据才可以一起存储到数组中。 注意: 2. ArrayList 源码分析
构造方法// 指定长度 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 创建指定长度的 Object 数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // 空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } // 空参构造方法 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 传递集合对象方法 public ArrayList(Collection<? extends E> c) { // 转换为数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) // 这是一个 bug,c.toArray 有可能返回的不是 Object[] 类型,此问题在 JDK9 已经被修复 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData,size,Object[].class); } else { // 数组长度为0,返回空数组 this.elementData = EMPTY_ELEMENTDATA; } } 插入数据// 插入元素 public boolean add(E e) { // 检测是否扩容 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } // 指定位置插入元素 public void add(int index,E element) { // 判断 index 是否越界 rangeCheckForAdd(index); // 检测是否需要扩容 ensureCapacityInternal(size + 1); // 将 index 之后的所有元素向后移动一位 System.arraycopy(elementData,index,elementData,index + 1,size - index); // 将 index 位置覆盖新值 elementData[index] = element; // 长度加 1 size++; } 扩容操作// 扩容的入口方法 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData,minCapacity)); } // 计算最小容量 private static int calculateCapacity(Object[] elementData,int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 默认容量 10 return Math.max(DEFAULT_CAPACITY,minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 超过过数组长度则进行扩容,若没有初始化容量大小,则默认为10 // 是否满足扩容的条件 最小容量 - object 数组的长度 if (minCapacity - elementData.length > 0) grow(minCapacity); } // 数组扩容方法 private void grow(int minCapacity) { // 当前数组长度 int oldCapacity = elementData.length; // 新的数组容量 = 老容量 + 老容量 / 2(1.5倍)【右移一位即 / 2】 // eg: oldCapacity = 10 // oldCapacity >> 1 // 0000 1010 >> 1 // 0000 0101 = 5 int newCapacity = oldCapacity + (oldCapacity >> 1); 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); } 删除方法// 指定下标删除 public E remove(int index) { // 检测 index 值是否越界,IndexOutOfBoundsException rangeCheck(index); modCount++; // 返回要删除的元素 E oldValue = elementData(index); // 将 index+1 及之后的元素向前移动一位,覆盖被删除的值 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData,index+1,numMoved); // 将最后一个位置的元素清空 elementData[--size] = null; return oldValue; } // 指定元素删除 public boolean remove(Object o) { // 判断元素是否为 null if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } // 如果没有匹配,返回 false return false; } // 快速删除,没有检测 index 下标 private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData,numMoved); elementData[--size] = null; } 遍历ArrayList<Integer> list = new ArrayList<>(); list.add(10); list.add(11); list.add(12); list.add(13); list.add(15); // for-each 删除 for (Integer num : list) { if (num == 12) { list.remove(num); } } // 报错 // Exception in thread "main" java.util.ConcurrentModificationException // 因为 ArrayList 源码中 final void checkForComodification() { // modCount 值和 expectedModCount 值不相等就异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); } // 解决异常问题 Iterator<Integer> it = list.iterator(); while (it.hasNext()) { Integer num = it.next(); if (num == 12) { // 使用迭代器的删除方法 it.remove(); } }
public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); }
public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; // 修改 expectedModCount 值和当前 modCount 一样 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } 可以看到 Iterator 类中的 remove() 方法中将 总结:我们应该使用 迭代器 Iterator 来删除元素而不应该使用 for-each 方法。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |