宣传部网站建设方案,wordpress 外部链接,北京优化seo排名优化,国内购物平台都有哪些内部结构
ArrayList内部核心是一个Object数组elementDataObject数组的长度#xff08;length#xff09;视为ArrayList当前的容量#xff08;capacity#xff09;size对象表示ArrayList当前的元素个数
类上的重要注释
内部是Object数组
允许put null值,会自动扩容
size、…内部结构
ArrayList内部核心是一个Object数组elementDataObject数组的长度length视为ArrayList当前的容量capacitysize对象表示ArrayList当前的元素个数
类上的重要注释
内部是Object数组
允许put null值,会自动扩容
size、isEmpty、get、set、add 等方法时间复杂度都是 O (1);
多个线程操作一个ArrayList实例如果有改变结构的操作就一定要在外部进行线程同步推荐的做法List list Collections.synchronizedList(new ArrayList(...))
增强for循环,或者使用迭代器迭代过程中如果数组大小被改变会快速失败抛出异常。如何初始化一个有元素的ArrayList
普通方式
ArrayListString list new ArrayList();
list.add(1);
list.add(2);内部类方式
ArrayListString list new ArrayList(){add(aaa);add(bbb);
}Arrays.asList
ArrayListString list new ArrayList(Arrays.asList(aaa, bbb);Collections.ncopies
例子初始化一个由10个0组成的集合
ArrayListInteger list new ArrayList(Collections.nCopies(10, 0));重要源码
构造
ArrayList有三种构造方法
public ArrayList()//elementData初始化一个空数组
public ArrayList(int initialCapacity) //this.elementData new Object[initialCapacity]
public ArrayList(Collection? extends E c) 这里主要关注new ArrayList()和new ArrayList(0)的区别两者都是初始化一个空数组但是
无参构造得到的ArrayList容量一开始是0初次add时会直接扩容到10重新申请一个length为10的数组并且拷贝过来
但new ArrayList(0)得到ArrayList按照扩容核心方法grow()中的写法从0开始增长容量前期容量增长的会很慢0-1-2-3-4-6-9-13)
一般情况下为了避免扩容造成的造成的损耗new ArrayList(0)不推荐使用
add 尾部添加
//要点添加前会确认容量,防止数组越界public boolean add(E e) {ensureCapacityInternal(size 1);elementData[size] e;return true;
}//扩容
//1.先确认是否需要扩容,当期望容量(size(元素数)1)超过当前容量了就需要扩容
//2.一般期望容量都是size1,除了无参构造的空数组第一次扩容时,期望容量是10
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private void ensureExplicitCapacity(int minCapacity) {modCount;// overflow-conscious codeif (minCapacity - elementData.length 0) //所需的最小容量超过当前容量了就需要扩容grow(minCapacity);
}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //无参构造,默认初始化容量为10return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}//扩容本质是按照新容量创建一个新数组然后把老数组数据用Arrays.copyOf复制过去
//新容量的计算规则//1.一般是原容量的3/2用oldold1实现//2.3/2可能都不够比如0*3/2,直接扩容成期望容量(其实就是1)//3.3/2超过最大容量了 Integer.MAX_VALUE - 8,看看期望容量和Integer.MAX_VALUE - 8哪个更适合
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity elementData.length;int newCapacity oldCapacity (oldCapacity 1); //3/2if (newCapacity - minCapacity 0) //比如0的3/2倍还是0,直接扩容到1就好了newCapacity minCapacity;if (newCapacity - MAX_ARRAY_SIZE 0) //newCapacity超大了,就不能用3/2规则了,看看minCapacitynewCapacity hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData Arrays.copyOf(elementData, newCapacity); //浅拷贝
}private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // overflowthrow new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}指定位置插入
从逻辑上看指定位置插入是四步
查看index是否越界容量检查不够扩容数据迁移将插入位置之后的所有元素拷贝到1的位置element插入到指定位置
注意这个方法上面的注释
rangeCheck越界的标准是看size而不是capacity 对于ArrayList来说内部数组的长度就是capacity也就是容量当前数组的元素个数是size这两个数据并不见得相等比如无参构造生成的ArrayListsize可能为1capacity为10但从使用者的角度来看ArrayList就是个动态增长的list使用者感知不到容量、扩容使用者看起来这个ArrayList的末尾就是size调用add只能在数据中间插入或者在数据末尾下标为size的位置插入否则即使插入的下标没有超过capacity但是超过了size也算越界。删除,同理,也会有rangeCheck 固定位置的插入删除,每次都会涉及大量的数据迁移,在拥有大量数据的ArrayList中不建议这么做 public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size 1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index 1,size - index);elementData[index] element;size;
}指定位置删除
可类比上个方法 public E remove(int index) {
//溢出校验rangeCheck(index);modCount;E oldValue elementData(index);int numMoved size - index - 1;if (numMoved 0)
//被删除元素后边元素前移System.arraycopy(elementData, index1, elementData, index,numMoved);elementData[--size] null;// clear to let GC do its work//返回被删除元素return oldValue;}按元素删除
方法注释
新增的时候是没有对 null 进行校验的所以删除的时候也是允许删除 null 值的找到值在数组中的索引位置是通过 equals 来判断的如果数组元素不是基本类型需要我们关注 equals 的具体实现。
public boolean remove(Object o) {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;}}return false;}private void fastRemove(int index) {modCount;int numMoved size - index - 1;if (numMoved 0)System.arraycopy(elementData, index1, elementData, index,numMoved);elementData[--size] null;// clear to let GC do its work}重点迭代器
迭代器模式简介
我们遍历一个一维的集合时经常会使用for循环或者foreach循环
for (String item : list) {System.out.println(item);
}如果我们要遍历一个二维的图简单的for循环就做不到了这时我们可能会采用DFS或者BFS之类的办法相信大家刷算法的时候都写过。
这时就会存在以下问题同时也引出迭代器模式
我肯定不想每次遍历时都把DFS的代码重新在客户端代码里写一遍这意味着客户端代码需要关心数据结构的具体实现一旦数据结构的具体实现变了比如邻接矩阵变成邻接表了或者遍历方法变了DFS变成BFS了就需要把客户端代码的遍历代码全都修改一遍如果将这部分遍历的逻辑封装到到容器类中也会导致容器类代码的复杂性。
因此我们可以将遍历操作拆分到迭代器类中。比如针对图的遍历我们就可以定义 DFSIterator、BFSIterator 两个迭代器类让它们分别来实现深度优先遍历和广度优先遍历容器类和迭代器之间用组合方式关联。
并且容器和迭代器都提供了抽象的接口方便我们在开发的时候基于接口而非具体的实现编程。当需要切换新的遍历算法的时候比如从前往后遍历链表切换成从后往前遍历链表客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可其他代码都不需要修改。除此之外添加新的遍历算法我们只需要扩展新的迭代器类也更符合开闭原则。 总结起来迭代器模式有以下的好处
封装复杂数据结构的遍历代码简单的数据结构我可以直接用for循环遍历但是复杂数据结构的遍历代码没必要在自己的客户端代码里再实现一遍于是拆分出迭代器接口容器类和迭代器之间用组合方式关联。扩展性我们也不想把遍历方法写在容器类中容器类更加复杂变化原因增加不符合单一职责我需要更改或添加迭代方式时只需要扩展新的迭代器类而不需要去更改其他地方的代码更符合开闭原则基于接口编程容器和迭代器都提供了抽象的接口方便我们在开发的时候基于接口而非具体的实现编程。当需要切换新的遍历算法的时候比如从前往后遍历链表切换成从后往前遍历链表客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可其他代码都不需要修改
ArrayList的迭代器
Java中如果要自己实现迭代器实现java.util.Iterator类就好了ArrayList就是这样做的
ArrayList实现了两个迭代器类Itr和ListItr后者继承了前者先看看第一个
这里先省略方法的具体实现看看一个迭代器的主要参数和方法
private class Itr implements IteratorE {int cursor; // 迭代过程中下一个元素的位置默认从0开始int lastRet -1; // 一般情况下表示上一次迭代过程中索引的位置删除一次后为-1int expectedModCount modCount; //expectedModCount表示迭代过程中期望的版本号Itr() {}public boolean hasNext() { //查看还有没有值可以迭代}public E next() { //如果有值可以迭代迭代值是多少}public void remove() { //删除当前迭代的值}public void forEachRemaining(Consumer? super E consumer) {}final void checkForComodification() {}
}常规情况下遍历一个list的代码以及删除元素的代码如下
// 获取迭代器并遍历 ArrayList
IteratorString iter list.iterator();
while (iter.hasNext()) {String item iter.next(); //next的关键无非是cursor如何移动if (item.equals(banana)) {// 使用迭代器删除元素iter.remove(); //cursor指向的是下一个元素的位置lastRet是cursor的前一个位置所以remove操作实际上删除的是lastRet指向的元素}
}需要注意删除操作
cursor指向的是下一个元素的位置lastRet是cursor的前一个位置所以remove操作实际上删除的是lastRet指向的元素执行remove之后cursorlastRet退回到前一个位置防止遍历时丢失元素lastRet-1这也就导致了remove操作不能连续执行必须是先执行next操作(会将lastRet重新变为cursor-1)才能执行一次remove
modCount有什么作用与一个Fail-Fast 机制有关
首先ArrayList中有一个modCount属性所有更改数据结构的操作addremove都会将modCount可以被视作更改了ArrayList的版本号
另外迭代器Itr中有属性expectedModCount初始化为modCount。每次next()都会先检查expectedModCount有没有发生改变如果改变就抛异常。
也就是说从Itr创建开始就不允许当前ArrayList有结构上的改变避免可能存在的错误
private class Itr implements IteratorE {int expectedModCount modCount; //expectedModCount表示迭代过程中期望的版本号public E next() { //如果有值可以迭代迭代值是多少checkForComodification();}final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();}
}那可能会出什么错呢
一句话总结就是遍历过程中在当前游标之前包括当前游标的位置插入或删除元素会导致某个元素重复遍历或者丢失遍历
因此在ArrayList实现的Iterator逻辑中每次cursor指向的都是下次元素的位置而lastRet指向最后一次遍历元素的位置 每次remove操作因为调用了arraylist的remove方法modCount会自增这时会将expectedModCount重置为modCount防止fail-fast并且将cursor回退为lastRet避免丢失元素
Fail-Fast 机制通常设计用于停止正常操作而不是试图继续可能出错的过程。注意这个并不能防止多线程操作出现异常只是防止单线程操作迭代器遍历过程中被其他方式改变了集合结构那么继续使用迭代器是有可能报异常的因为从使用者的角度看这不属于使用者的逻辑错误但是可能会出错所以在设计上应当主动报异常
ArrayList还实现了一个迭代器ListIterator
private class ListItr extends Itr implements ListIteratorE {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();}}
}区别
1.使用范围不同Iterator可以应用于所有的集合Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。
2.ListIterator有add方法可以向List中添加对象而Iterator不能。
3.ListIterator和Iterator都有hasNext()和next()方法可以实现顺序向后遍历但是ListIterator有hasPrevious()和previous()方法可以实现逆向顺序向前遍历。Iterator不可以。
4.ListIterator可以定位当前索引的位置nextIndex()和previousIndex()可以实现。Iterator没有此功能。
5.都可实现删除操作但是ListIterator可以实现对象的修改set()方法可以实现。Iterator仅能遍历不能修改。
参考资料
王争. 设计模式之美
