个人主页:https://
接上篇.....
修改元素// 将指定位置的元素改为指定的值 public E set(int index, E element) { rangeCheck(index); // 检查index是否越界
E oldValue = elementData(index); elementData[index] = element; return oldValue; }
查找元素//判断ArrayList中是否包含Object(o) public boolean contains(Object o) { return indexOf(o) >= 0; }
//返回一个值在数组首次出现的位置,会根据是否为null使用不同方式判断。 //不存在就返回-1。时间复杂度为O(N) public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i ) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i ) if (o.equals(elementData[i])) return i; } return -1; }
//返回一个值在数组最后一次出现的位置,不存在就返回-1。时间复杂度为O(N) public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
//返回指定位置的值,因为是数组,所以速度特别快 @SuppressWarnings('unchecked') E elementData(int index) { return (E) elementData[index]; }
//返回指定位置的值,但是会检查这个位置数否超出数组长度 public E get(int index) { rangeCheck(index);
return elementData(index); //实质上return (E) elementData[index] }
序列化//保存数组实例的状态到一个流(即它序列化)。写入过程数组被更改会抛出异常 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ int expectedModCount = modCount; s.defaultWriteObject(); //执行默认的反序列化/序列化过程。将当前类的非静态和非瞬态字段写入此流 // 写入大小 s.writeInt(size); // 按顺序写入所有元素 for (int i=0; i<size; i ) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } //上面是写,这个就是读了。 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // 执行默认的序列化/反序列化过程 s.defaultReadObject(); // 读入数组长度 s.readInt(); if (size > 0) { ensureCapacityInternal(size); Object[] a = elementData; //读入所有元素 for (int i=0; i<size; i ) { a[i] = s.readObject(); } } }
为什么要自定义序列化、反序列化机制呢? 由于ArrayList实质上是一个动态数组,往往数组中会有空余的空间,如果采用默认的序列化机制,那些空余的空间会作为null写入本地文件或者在网络中传输,耗费了不必要的资源。所以,ArrayList使用自定义序列化机制,仅写入索引为【0,size)的有效元素以节省资源。
迭代器//返回ListIterator,开始位置为指定参数 public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException('Index: ' index); return new ListItr(index); }
//返回ListIterator,开始位置为0 public ListIterator<E> listIterator() { return new ListItr(0); }
//返回普通迭代器 public Iterator<E> iterator() { return new Itr(); }
//通用的迭代器实现 private class Itr implements Iterator<E> { int cursor; //游标,下一个元素的索引,默认初始化为0 int lastRet = -1; //上次访问的元素的位置 int expectedModCount = modCount; //迭代过程不允许修改数组,否则就抛出异常 //是否还有下一个 public boolean hasNext() { return cursor != size; } //下一个元素 @SuppressWarnings('unchecked') public E next() { checkForComodification();//检查数组是否被修改 int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i 1; //向后移动游标 return (E) elementData[lastRet = i]; //设置访问的位置并返回这个值 } //删除元素 public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification();//检查数组是否被修改 try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings('unchecked') 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 ]); } cursor = i; lastRet = i - 1; checkForComodification(); } //检查数组是否被修改 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
//ListIterator迭代器实现 private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings('unchecked') public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }
Iterator与ListIterator的区别: Iterator可以应用于所有的集合,Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型; Iterator只能实现顺序向后遍历,ListIterator可实现顺序向后遍历和逆向(顺序向前)遍历; Iterator只能实现remove操作,ListIterator可以实现remove操作,add操作,set操作。
其他方法//返回ArrayList的大小(元素个数) public int size() { return size; }
//判断ArrayList是否为空 public boolean isEmpty() { return size == 0; }
//返回此 ArrayList实例的浅拷贝 //(元素本身没有被复制,复制过程数组发生改变会抛出异常) public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { throw new InternalError(e); } } /* 浅克隆就是我们所看到的Arrays.copyOf, System.arraycopy, 数组是新的,但是里面N个元素全是引用的旧的。 浅拷贝(影子克隆):只复制基本类型。
深拷贝(深度克隆):基本类 对象。 */
//返回一个包含ArrayList中所有元素的数组 public Object[] toArray() { return Arrays.copyOf(elementData, size); }
// 返回一个数组,使用运行时确定类型,该数组包含在这个列表中的所有元素 //(从第一到最后一个元素) // 返回的数组容量由参数和本数组中较大值确定 @SuppressWarnings('unchecked') public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }
ArrayList相关问题Integer.MAX_VALUE - 8 这里为什么要减去8?主要是考虑到不同的JVM,有的VM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会去比较最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。 这个是从jdk1.7开始才有的。
jdk1.8的无参构造函数和之前版本的构造函数有什么区别?jdk1.6 public ArrayList() { this(10); }
jdk1.7 public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; }
jdk1.8 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
对比下可以看出:jdk1.6的无参构造方法(默认构造方法)构造的ArrayList的底层数组elementData大小(容量)默认为10;从1.7开始,无参构造方法构造的ArrayList的底层数组elementData大小默认为0。
java集合类在jdk1.7版本基本上都有一种改动:懒初始化。懒初始化指的是默认构造方法构造的集合类,占据尽可能少的内存空间(对于ArrayList来说,使用空数组来占据尽量少的空间,不使用null是为了避免null判断),在第一次进行包含有添加语义的操作时,才进行真正的初始化工作。
1.7开始的ArrayList,默认构造方法构造的实例,底层数组是空数组,容量为0,在进行第一次add/addAll等操作时才会真正给底层数组赋非empty的值。如果add/addAll添加的元素小于10,则把elementData数组扩容为10个元素大小,否则使用刚好合适的大小(例如,第一次addAll添加6个,那么扩容为10个,第一次添加大于10个的,比如24个,扩容为24个,刚好合适)
1.8版本,默认构造的实例这个行为没有改变,只是用的数组名字变了。
jdk1.6中扩容算法的缺陷(由于jdk1.7和jdk1.8在扩容算法方面差别不大,所以下面没有严格区分) //jdk1.6 public void ensureCapacity(int minCapacity) { modCount ; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }
从上面的代码可以看出jdk1.6的ensureCapacity方法只是简单进行了逻辑上的操作,没有过多考虑int型溢出的问题,从1.7开始对这个进行了完善。
而且没考虑入参minCapacity可能因为int溢出变为负数。这个方法可以外部手动调用,手动扩容传入负数这个肯定是应该拦截掉的。但是自动扩容会因为int溢出产生负数,碰到这种情况时应该特殊处理,而不是什么都不做,等着后面抛出一个ArrayIndexOutOfBoundsException。
还有就是下面这句代码会造成过早溢出 int newCapacity = (oldCapacity * 3)/2 1;
虽然上面这行代码和1.7开始的oldCapacity (oldCapacity >> 1) 差不多,都是相当于1.5倍,但实际上是有区别的。
这里主要有两个区别 第一个区别是jdk1.6的乘除运算的数学结果比后面一个大1比如oldCapacity=10,1.6的算法得到16,1.7开始的算法得到15,这个影响不大; 第二个区别就是两者在数字比较大时运算结果不一样,比如oldCapacity=10^9,这个数和Integer.MAX_VALUE位数一样,用1.6的算法得到的会是错误的-647483647,用1.7的则是正确的1500000000,这时候明明可以1.5倍扩容,但是jdk1.6却用的是按需扩容。
ensureCapacity(称之为手动,是因为此方法是public的,可以外部手动调用)。 在1.6版本是只有这个手动的方法,内部自动操作也是调用这个方法,1.7开始进行了区分,并且进一步改进了扩容操作。 newCapacity = oldCapacity (oldCapacity >> 1);
这行代码不仅仅是使用位运算加快执行速度,上面说了,这种做法才是对的,是真正的1.5倍。不仅仅因为那一个大小的差别,更重要的是避免过早出现int溢出的情况,保证了内部自动扩容会尽量按规定的策略执行。同时整个扩容处理流程中多增加了几处if判断,对各种情况处理更加完善。
为什么ArrayList自动容量扩充选择扩充1.5倍?这种算法构造出来的新的数组长度的增量都会比上一次大( 而且是越来越大) ,避免频繁newInstance 的情况。
为什么ArrayList 不适合频繁插入和删除操作?由上面分析的增加删除方法可以看出在ArrayList中经常会调用 System.arraycopy 这个效率很低的操作来复制数组,所以导致ArrayList在插入和删除操作中效率不高。
【Java知音】实时干货推荐栏
|