ArrayList和LinkedList学习
摘要
arraylist和linkedlist是对list接口的不同数据结构的实现。它们都是线程不安全的,线程不安全往往出现在数组的扩容、数据添加的时候。
一、arraylist和linkedlist是什么?
arraylist:arraylist是list接口的可变数组的实现。
linkedlist:linkedlist是list接口的(双向)链表实现。
二、两个list的数据结构
1、arraylist的数据结构
arraylist的类继承图如下:
存储
arraylist使用数组(elememntdata)存储数据,默认构造方法创建arraylist时,会初始化一个空数组。
扩容
arraylist使用数组存储数据,因此在添加数据的时候需要做容量检查,如果容量不足则需要进行扩容。
其新容量大小公式为:新容量=旧容量+旧容量/2
扩容过程请看下面源码:
public boolean add(e e) { // 容量检查 ensurecapacityinternal(size + 1); // increments modcount!! elementdata[size++] = e; return true; } // 计算数组需要的最小容量 private void ensurecapacityinternal(int mincapacity) { if (elementdata == defaultcapacity_empty_elementdata) { mincapacity = math.max(default_capacity, mincapacity); } ensureexplicitcapacity(mincapacity); } // 判断是否需要扩容,如果需要则扩容 private void ensureexplicitcapacity(int mincapacity) { // modcount表示list结构修改的次数,快速失败机制会用到,快速失败机制在后面会详细说明。 modcount++; // overflow-conscious code if (mincapacity - elementdata.length > 0) grow(mincapacity); } private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; // 新容量=旧容量+旧容量/2 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); }
2、linkedlist的数据结构
linkedlist的类继承图如下:
存储
linkedlist使用双向链表来存储数据。其中链表结点定义如下:
private static class node<e> { e item; node<e> next; node<e> prev; node(node<e> prev, e element, node<e> next) { this.item = element; this.next = next; this.prev = prev; } }
添加/删除元素操作
linkedlist添加删除元素,实际上就是对链表进行结点添加/删除,下面给出实现细节,以供后面的线程安全讨论使用(注意modcount发生了变化)。
// 添加元素 public boolean add(e e) { // 往链表末尾添加元素 linklast(e); return true; } // 添加结点 void linklast(e e) { final node<e> l = last; final node<e> newnode = new node<>(l, e, null); // 新结点作为尾结点 last = newnode; if (l == null) first = newnode; else l.next = newnode; // 连接结点 size++; modcount++; } // 删除元素(删除第一个匹配的元素) public boolean remove(object o) { if (o == null) { for (node<e> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (node<e> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } // 删除结点 e unlink(node<e> x) { // assert x != null; final e element = x.item; final node<e> next = x.next; final node<e> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modcount++; return element; }
三、线程安全讨论
首先确认一点的是,arraylist和linkedlist均是线程不安全的,下面将分析多线程情况下会出现的一些问题。
1、快速失败(fail-fast)
快速失败,指的是使用遍历器对list进行遍历时,如果在遍历过程中,对list进行了修改,则会触发快速失败机制,抛出java.util.concurrentmodificationexception异常。
快速失败触发机制
前文谈到modcount的作用用于记录list的修改次数,在遍历器进行遍历时,代码正是通过这个值触发快速失败的。
相关核心代码如下:
int expectedmodcount = modcount; public e next() { checkforcomodification(); try { int i = cursor; e next = get(i); lastret = i; cursor = i + 1; return next; } catch (indexoutofboundsexception e) { checkforcomodification(); throw new nosuchelementexception(); } } // 检查修改次数,该方法在类中多次会被调用 final void checkforcomodification() { if (modcount != expectedmodcount) throw new concurrentmodificationexception(); }
2、arraylist添加元素时的数组越界问题
添加元素时的数组越界问题发生在扩容判断上,当当前数组容量还差一个元素达到数组扩容的临界值时。并发插入元素时对数组大小的判断均是无需扩容,但是当前数组实际上仅有一个空闲位置,因此数组越界异常就发生了。
3、添加元素被覆盖
这种异常出现情况如下面代码注释所示:
多个线程对数组同一个位置进行赋值,导致元素被覆盖。
elementdata[size++] = e; // elementdata[size] = e; --- thread1 // elementdata[size] = e; --- thread2 // size++; --- thread1 // size++; --- thread2
类似的分析,linkedlist添加元素时也会出现这种情况。
4、线程安全的list
同步方法
全部使用同步方法,如:vector、collections.synchronizedlist(list)
其它加锁
其它加锁实现线程安全,如:concurrentlinkeddeque(自旋+cas)、copyonwritearraylist(读写锁)
参考资料
上一篇: 不需任何软件 图片水印怎么快速去掉?
下一篇: 竟然也是满满的套路
推荐阅读
-
java 学习笔记(入门篇)_程序流程控制结构和方法
-
java语法ArrayList、LinkedList、HashSet、HashMap、HashTable、Collection、Collections详解
-
Python3.4学习笔记之常用操作符,条件分支和循环用法示例
-
Linux内核学习笔记(4)-- wait、waitpid、wait3 和 wait4
-
Mybatis中SqlSessionFactory和SqlSession学习和原理
-
SQL学习笔记:库和表的创建
-
这个机器人厉害了 具备行为学习和云备份功能
-
python中学习K-Means和图片压缩
-
Linux学习笔记(二):文件目录管理和VIM编辑器的使用
-
PHP学习之字符串比较和查找