今天我们要学习的,是数组这种数据结构在JDK集合中的应用。
数组作为最简单的一种线性结构,操作也比较简单。虽说简单,但它却是编程语言底层实现不可缺少的。
它的特点是,按索引随机查找快,插入和删除比较慢。因为按照索引可以直接定位到某个元素,而插入或删除通常会涉及到数据的迁移。
数组的元素前后之间是连续存储的,因此有利于CPU进行缓存,从而提高访问速度。
在JDK的集合中,ArrayList、Vector和Stack的底层存储结构,都是数组。
接下来,我们就从数组的基本操作开始,一步步实现我们的目标。
数组主要有三个基本操作:查找、插入和删除。
/** 创建一个数组 */ int[] elementData = new int[10]; /** 数组已存储的元素个数 */ int size = 0; 复制代码
/** * 添加. 将新元素添加到数组尾部. */ public void add(int e) { elementData[size++] = e; } 复制代码
/** * 查找. 获取指定索引位置的元素 */ public int get(int index) { return elementData[index]; } 复制代码
/** * 插入. * 1.指定索引位置及之后的所有元素先往后移动1位; * 2.将新元素插入到指定索引位置. */ public void add(int index, int e) { // 1.index及之后的元素后移1位. index移动到index+1的位置,移动的数量为size-index个. System.arraycopy(elementData, index, elementData, index + 1, size - index); // 2.保存元素,已存储数量加1 elementData[size++] = e; } 复制代码
/** * 删除. 删除指定索引位置的元素,指定索引位置后面的所有元素往前移动1位. */ public void remove(int index) { // 1.计算出需要往前移动的元素个数. // index+1代表区间[0,index]的数量,size-(index+1)代表index之后元素的个数. int numMoved = size - index - 1; // 2.将index后面的所有元素往前移动1位. // 伪代码:for (numMoved) elementData[index]=elementData[index+1]; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 3.已存储数量减1 size--; } 复制代码
/** * 更新. 更新指定索引位置的元素,并返回旧值. */ public int set(int index, int newValue) { int oldValue = elementData[index]; elementData[index] = newValue; return oldValue; } 复制代码
/** * 查找元素. 返回首次出现的索引位置,如果元素不存在则返回 -1. */ public int indexOf(int o) { for (int i = 0; i < size; i++) if (o == elementData[i]) return i; return -1; } 复制代码
/** * 默认进行2倍扩容. */ private void resize() { if (size == elementData.length) { // 1.按2倍大小创建新数组,并将已存储的数据迁移到新数组 int[] copy = new int[size * 2]; System.arraycopy(elementData, 0, copy, 0, elementData.length); // 2.使用扩容后的新数组替换旧数组 elementData = copy; } } 复制代码
/** * System.arraycopy的简化实现. */ public void arraycopy(int[] src, int srcPos, int[] dest, int destPos, int length) { for (int i = 0; i < length; i++) { dest[destPos++] = src[srcPos++]; } } 复制代码
通过以上内容,我们可以了解到,数组稍微复杂一点的操作是插入、删除和扩容。
共同点如下:
插入1个元素
删除1个元素
插入需要移动的元素个数为:size - index
删除需要移动的元素个数为:size - (index + 1)
根据前面2点得到的开始移动索引位置和移动个数,循环移动数据。
虽然可以自己实现数据的移动,但借助于System.arraycopy()更加高效。因为高性能的JVM都会将System.arraycopy()实现为intrinsic方法,也就是说,JVM内部会提供一套更高效的实现。
将上面数组的这些操作组合起来,就可以实现ArrayList的核心功能了。
主要思路如下:
Vector的实现基本和ArrayList是一样的,主要区别是Vector是线程安全的。
Vector实现线程安全的方法很简单,就是在ArrayList的基础之上,一视同仁对每个方法都加上同步原语synchronized。
简单粗暴的结果,就是在高并发的情况下效率比较低下,因此一般也比较少使用。
Stack继承了Vector,简单复用了Vector的相关方法。并基于这些方法,封装了栈的入栈出栈操作。
可想而知,Stack的相关操作也是线程安全的,效率依赖于Vector的实现。
数组索引位置0代表栈底,索引位置 size-1 代表栈顶。
相当于查找索引号为 size-1 的元素:get(size - 1)。
将元素推入栈顶,即将元素添加到数组尾部:add(e)。
栈顶元素出栈,即删除数组的最后一个元素:remove(size - 1)。
写到这里,我们来总结一下掌握本篇内容的核心步骤:
通过以上几个步骤,能够更加高效的学习,更好的理解ArrayList、Vector和Stack这几个类的实现原理。
那么,现在就只差最后一步了:打开电脑,开始徒手实现吧^_^
最后,附上我对ArrayList的简化实现:
/** * java.util.ArrayList的核心实现. * * @param <E> */ public class MyArrayList<E> { /** 用于存储元素的数组. 其大小,即为底层存储的容量. */ private Object[] elementData; /** 已存储元素的个数 */ private int size; /** * 默认构造函数 */ public MyArrayList() { this(10); } /** * 构造函数 * * @param initialCapacity 初始化容量 */ public MyArrayList(int initialCapacity) { this.elementData = new Object[initialCapacity]; } /** * 添加元素 * * @param e * @return */ public boolean add(E e) { // 1.检查容量与扩容 resize(); // 2.保存元素,已存储数量加1 elementData[size++] = e; return true; } /** * 插入. 将元素插入到指定索引位置,索引位置及之后的元素往后移动1位 * * @param index * @param e */ public void add(int index, E e) { // 1.索引范围检查 rangeCheckForAdd(index); // 2.检查容量与扩容 resize(); // 3.index及之后的元素后移1位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 4.保存元素,已存储数量加1 elementData[size++] = e; } /** * 获取指定索引位置的元素 * * @param index * @return */ @SuppressWarnings("unchecked") public E get(int index) { // 1.索引范围检查 rangeCheck(index); // 2.返回元素 return (E) elementData[index]; } /** * 更新指定索引位置的元素,同时返回旧值. * * @param index * @param element * @return */ @SuppressWarnings("unchecked") public E set(int index, E element) { // 1.索引范围检查 rangeCheck(index); // 2.暂存旧值,在最后返回 E oldValue = (E) elementData[index]; // 3.更新指定索引位置的数量 elementData[index] = element; return oldValue; } /** * 删除指定索引位置的元素,并返回该元素 * * @param index * @return */ @SuppressWarnings("unchecked") public E remove(int index) { // 1.索引范围检查 rangeCheck(index); // 2.获取待删除后返回的元素 E oldValue = (E) elementData[index]; // 3.将index后面的所有元素往前移动1位 // 计算出需要往前移动的元素个数. index+1代表区间0~index的数量,size-(index+1)代表index之后元素的个数. int numMoved = size - index - 1; if (numMoved > 0) // 将[index+1, size)区间的numMoved个元素往前移动1位 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 4.已存储数量减1. 同时末尾元素设置为null,便于GC. elementData[--size] = null; return oldValue; } /** * 是否包含指定元素 * * @param o * @return */ public boolean contains(Object o) { return indexOf(o) >= 0; } /** * 返回首次出现指定元素的索引位置. 如果元素不存在则返回 -1. * * @param o * @return */ public int indexOf(Object o) { // 从前往后遍历 for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; return -1; } /** * 返回最后一次出现指定元素的索引位置. 如果元素不存在则返回 -1. * * @param o * @return */ public int lastIndexOf(Object o) { // 从后往前遍历 for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; return -1; } /** * 以数组形式返回列表的所有元素,支持泛型 * * @param a * @return */ public <T> T[] toArray(T[] a) { System.arraycopy(elementData, 0, a, 0, size); return a; } /** * 返回列表大小 * * @return */ public int size() { return size; } /** * 列表是否为空 * * @return */ public boolean isEmpty() { return size == 0; } /** * 索引范围检查 * * @param index */ private void rangeCheck(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("size: " + size + ", index: " + index); } /** * 索引范围检查 * * @param index */ private void rangeCheckForAdd(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("size: " + size + ", index: " + index); } /** * 检查数组存储空间是否已满,如果满了进行1.5倍扩容. */ private void resize() { if (size == elementData.length) { // 1.默认按1.5倍扩容 int newCapacity = size + (size >> 1); if (newCapacity <= size) { newCapacity = size + 1; } // 2.扩容,将元素迁移到新的数组 elementData = copyOf(elementData, newCapacity); } } /** * 从源数组复制指定长度的元素到新数组. 用于扩容或缩容 * * @param original * @param newLength * @return */ private Object[] copyOf(Object[] original, int newLength) { Object[] copy = new Object[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } } 复制代码
题图:thejavaprogrammer.com
更多文章,请关注公众号:二进制之路