fail-fast机制
在java集合类中,使用modCount来检查数组的状态.
当在迭代集合的时候,(通常会实现 iterator()方法来获取迭代对象,或者 foreach),
集合里面的数据,在其他地方被修改了,这个时候 modCount就会被修改,与迭代过程的modCount不一致.将抛出ConcurrentModificationException异常,这个过程就叫 fail-fast
List 篇
主要介绍 ArrayList,Vector和LinkedList,CopyOnWriteArrayList
ArrayList
是一个数组长度可自增长的线程不安全的列表.内部使用数组实现. Object[] elementData.
- 默认的长度为 10.
- fail-fast
- 自动扩容(每次扩容为原来的1.5倍)
- 线程不安全
- 使用连续控件存储
- 继承自
List,RandomAccess等.
- 允许添加
null值
时间复杂度 :
根据索引查询,复杂度为 O(1).
根据元素查询,复杂度为 O(N).
插入和删除,如果在列首复杂度为 O(N);在列尾复杂度为 O(1);平均复杂为 O(N)
插入和删除非列尾数据, 将会导致数组移动数据.
RandomAccess 接口
RandomAccess 是一个标记接口(没有任何方法).
如果实现了 RandomAccess 接口,表示该集合可以进行随机快速访问(通常底层是 数组形式的集合),如 ArrayList.
可以快速访问的集合,使用
for (int i=0, n<size; i++)
list.get(i);
未实现 RandomAccess接口的集合,如LinkedList,使用迭代器效率更高.
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
使用 instanceof RandomAccess来判断是否 支持随机快速访问.
Vector
是一个数组长度可自增长的线程安全的列表,内部使用数组实现.
- 默认的长度为 10.
- fail-fast
- 自动扩容(可设置每次扩容的增量值,默认扩容为原来的2倍.)
- 线程安全(
synchronized)
- 使用连续控件存储
- 继承自
RandomAccess,List
- 允许添加
null值
线程安全的vector,照样可以触发 fail-fast.
时间复杂度与 arraylist 一样.
在不涉及线程安全的前提下,arraylist效率更高.
fun main(args: Array<String>) {
val vector = Vector(listOf(1, 2, 3, 4, 5))
singleThread(vector)
multiThread(vector)
multiThreadSynchronized(vector)
}
/**
* 单线程下,迭代抛出 ConcurrentModificationException
*/
fun singleThread(vector: Vector<Int>) {
val it = vector.iterator()
while (it.hasNext()) {
println(it.next())
vector.add(1)
}
}
/**
* 多线程下,迭代抛出 ConcurrentModificationException
*/
fun multiThread(vector: Vector<Int>) {
thread {
repeat(10000) {
vector.add(it)
}
}
thread {
vector.forEach { println(it) }
}
}
/**
* 多线程下,修改vector是添加同步锁,避免同时迭代同时修改
*/
fun multiThreadSynchronized(vector: Vector<Int>) {
thread {
synchronized(vector) {
repeat(10000) {
vector.add(it)
}
}
}
thread {
vector.forEach { println(it) }
}
}
Stack
继承自 vector,线程安全,栈结构,先进后出.
LinkedList
是以双向链表方式实现的非线程安全的集合.
- 一个元素节点包含 上一个节点和下一个节点的引用,以及自身的值.
- 内存空间可不连续
- 线程不安全
- fail-fast
- 继承自
List,Deque等.
- 允许添加
null值
时间复杂度:
删除和插入元素,复杂度为 O(1).
查询时,由于采用双向链表,判断离哪头近,从哪头开始找.
最糟糕的情况是O(N/2),所以它的复杂度为 O(N).
CopyOnWriteArrayList
CopyOnWriteArrayList是并发包中的实现.使用 ReenterLock和System.arraycopy来实现数组读写的线程安全.
在读取的时不加锁,所以可以支持多线程同时读取数据,并且同时读取数不受限制.
在写入(add,set,remove等操作)的时候,使用 ReenterLock锁住方法,然后操作数据时先将原数组拷贝一份,对拷贝数据进行操作,操作完后将拷贝的原来的数据引用指向拷贝的数组引用,实现数据的更新操作,更新完后释放锁. 和其名字操作一致(写时拷贝).
没有设置初始长度的方法和扩容的策略. 因为该数组在每次 添加数据是, 都会使用 System.arraycopy拷贝一份比当前数据 +1 的数组.
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
ArrayList,Vector和LinkedList的区别
ArrayList和Vector内部都是使用数组实现的.它们的主要区别在于
-
ArrayList 是线程不安全的,Vector是线程安全的.
-
ArrayList 自动扩容时固定增长为原来的1.5倍,不可指定增量值. Vector可指定每次的增量值,如果没指定,则扩容为原来的2倍.
在不考虑线程安全的情况下,优先使用 ArrayList,如果在使用前,能够预估大概有元素,创建时指定个数,效果更好.
LinkedList 使用双向链表实现,也是线程不安全的.与ArrayList的区别在于
- 实现方式不同.
ArrayList使用数组,Vector使用双向链表.
- 内存空间管理不同,
LinkedList可以是不连续的空间,ArrayList需要连续的内存空间.
-
LinkedList 在删除和插入上的性能较好, ArrayList在查询上的效率更好.
-
ArrayList 一个item只存自己的值,比较省空间, LinkedList一个item除了自己的值,还需要存放上一个和下一个元素的引用,比较费空间.
如果主要需要对列表进行遍历,以及增删操作,使用LinkedList其他情况使用ArrayList.
如果需要用到线程安全的列表,请使用 CopyOnWriteArrayList
Map篇
Map 是以键值对形式存储的集合.
主要介绍 HashMap,TreeMap和 Hashtable,ConcurrentHashMap
HashMap
HashMap 内部混合使用数组,链表,红黑树的结构来构建的键值对集合.
HashMap的本质基础是基于数组的. 数组的各个元素,使用单向链表的结构.(Node(int hash, K key, V value, Node<K,V> next)).
HashMap通过哈希函数(hash())来完成key对index的映射.
当出现hash后index冲突(index位置已经存在不同的key的键值对)时,数据将在index位置,使用单向链表或红黑树(当链表长度大于等8个时,链表中的所有元素改用红黑树存放)来存放元素.
当使用掉的索引 占用了 数组长度的一定比例时(填装因子),HashMap将进行扩容(扩容为原来的两倍,key与index重新映射).
HashMap的性能瓶颈:
- 优良的 哈希函数.
理想的状态是,每一个键值对的存放,能够比较均匀适当的分布在数组的索引上,尽量避免过多的hash值冲突.
// java 8 中的实现
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// index = (n - 1) & hash , 2的次方来说就是取余操作.
// 由于 (n -1)的二进制 高位都是0,地位都是1.
// hashcode 与 它进行 & 操作的话, hashcode的高位变化低位不变,则计算出来的index值讲不变.
// 为了消除高位变化 不影响 index 的值, 于是将 hashcode 的 高16位 移动到低16位,再和 hashcode进行 ^ 操作.
// 这样高位的变化,也能影响index值, 降低了冲突的概率.
- 填装因子
过低的填装因子,如填装因子=0.5,容量剩余一半的时候就扩容,可能导致空间上的浪费.
过高的填装因子,可能导致为了命中未使用的索引,而频繁出现 冲突.
HashMap实现中,填装因子默认使用 0.75的值.
特点 :
- 默认的长度为 16,默认填装因子为 0.75.
- fail-fast
- 自动扩容(默认扩容为原来的2倍.)
- 线程不安全
- 混合使用数组,链表和红黑树
- 继承自
Map
-
key和value都可以添加 null
- 插入和遍历顺序不一致
时间复杂度 :
查询,插入和删除操作的平均时间复杂度为 O(1).
极端情况下(全部发生冲突),若长度小于8,使用单项链表,复杂度为 O(n),如果长度大于等于8,使用红黑树,复杂度为O(logn)
LinkedHashMap
继承自 HashMap, 底层使用哈希表与双向链表来保存元素,与HashMap的差异就在于 访问顺序上.
构造中,accessOrder 默认为 false，代表按照插入顺序进行迭代；为 true，代表以访问顺序进行迭代(最常访问的在前,最不经常访问的在后LRU)。
TreeMap
TreeMap内部使用 红黑树来实现的键值对集合.与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序.
特点 :
- fail-fast
- 线程不安全
- 使用红黑树实现
-
key和value都可以添加 null
- 插入和遍历顺序不一致
- 支持对
key排序
- 继承自
NavigableMap,拥有强大的搜索功能.
时间复杂度 :
红黑树是自平衡的二叉搜索树, 查询,添加删除 效率都是 O(logn).
HashTable
HashTable 内部使用数组和单项链表实现的键值对集合.
HashTable的哈希函数 (hash & 0x7FFFFFFF) % tab.length,只是对key的hashcod进行取整和取余操作.
HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。
也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。
由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。（这个是可以证明出来 的，可参考：http://zhaox.github.io/algorithm/2015/06/29/hash）
特点 :
- 默认的长度为 11,默认填装因子为 0.75.
- fail-fast
- 自动扩容(扩容为原来的2n+1)
- 线程安全
- 混合使用数组,链表
- 继承自
Map
-
key和value都不能使用null值,否则抛出空指针异常.
- 插入和遍历顺序不一致
时间复杂度 :
和HashMap一致
ConcurrentHashMap (java.util.concurrent)
和HashMap一样,是内部使用数组,链表,红黑树的结构来构建的键值对集合,因为需要保证线程安全,所以内部实现更加复杂.
哈希函数 (h ^ (h >>> 16)) & HASH_BITS , 和HashMap类似,与高位进行异或操作的方式,来消除高位数据变化导致索引不变的情况,多加了一步正数的操作.
当冲突的链表中个数超过8个, 如果数组长度小于64,则扩容,否则,将链表数据转化为 红黑树结构存储.
ConcurrentHashMap 采用 CAS(Compare and Swap)原子类型操作,来保证线程的安全性. 较 jdk1.7 的分段锁机制性能更好.
特点 :
- 默认长度为16,无默认的装填因子
构造函数为 : ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
没有默认的装填因子,传入 初始容量和装填因子后,会被算法调整为 2次方,最小容量为 16.
并发级别,表示 可以同时对数据进行写操作的线程数, 最大可达16. 读取不受限制.
- 没有 fail-fast, 将保证线程安全.
- 自动扩容为原来的 2 倍.
- 线程安全
- 混合使用数组,链表和红黑树
- 继承自
ConcurrentMap
-
key和value都不可以添加 null
- 插入和遍历顺序不一致
时间复杂度 :
和HashMap一致
HashMap和HashTable , ConcurrentHashMap对比
HashMap 线程不安全 , HashTable线程安全,但还是存在fail-fast问题 , ConcurrentHashMap线程安全,不存在fail-fast问题.
HashMap 和 ConcurrentHashMap 内部都是用 数组,链表 加红黑树来构建.(较高效) HashTable 使用数组加链表.
HashMap 和 ConcurrentHashMap 都是用 高位异或的哈希算法. HashTable 采用 数组长度为素数,直接取余的哈希算法.
HashMap 允许插入 null键值对, HashTable , ConcurrentHashMap 不允许.
结论 : 不考虑线程安全的情况下使用 HashMap, 线程安全则使用 ConcurrentHashMap.
如果知道 大概会存多少数据,指定 初始容量 会更高效, 避免扩容和重新hash映射产生的效率问题.
Set篇
Set 是没有重复元素的单元素集合.
TreeSet 内部使用 TreeMap实现.
HashSet 内部使用 HashMap实现. 当构造参数为三个时 LinkedHashMap实现.
LinkedHashSet 继承自 HashSet,但是都是调用 HashSet中有三个构造参数的LinkedHashMap来实现.
