集合框架
Collection
Collection 就是最常规意义的集合.是List,Set和Queue的父接口
List
List元素有序并且允许重复
List可以精确的控制插入位置或直接删除某个位置的元素
ArrayList
- 排列有序,允许元素重复
- 底层使用数组,遍历速度快,随机读取快,增删节点慢
- 线程不安全集合
- 扩容策略为每次50%,相对节约内存
Vector
- 排列有序,允许元素重复
- 底层使用数组,遍历速度块,随机读取快,增删节点慢
- 线程安全集合,这是Vector与ArrayList最大区别
- 扩容策略为每次扩容1倍,相对ArrayList会更加浪费内存
LinkedList
- 排列有序,允许元素重复
- 底层使用双向链表.遍历速度块,增删节点也快,但随机读取慢
- 线程不安全
- 没有扩容策略,链表本身属于无界集合
Set
HashSet
- 排列无序,不可重复
- 底层使用Hash表实现
- 内部本质是HashMap,随机读取快,增删节点快,遍历速度慢(Map的通病)
- 线程不安全
TreeSet
- 有序存储
LinkedHashSet
- 采用Hash表存储,并于双向链表记录插入顺讯
- 内部本质是LinkedHashMap
Queue
本质是在两端出入的list,一般就是数组或链表List的特殊进出规则封装
Map
Map提供一种基于映射关系的键值对存储,它的元素实际以Entry形式存储
对Map来说键不可以重复,但值可以重复
HashMap
- 键不可重复,值允许重复
- 底层哈希表
- 线程不安全
- 允许Key为null,允许值为null.但基于键不重复,null只会存在一个
HashTable
- 键不可重复,值允许重复
- 底层哈希表
- 线程安全
- Key,Value都不允许为null
TreeMap
- 底层二叉树
- 键不可重复.值允许重复
Concurrent
ConcurrentHashMap
- 线程安全
- 更加高效的线程安全模式(锁分段)
重要知识点
集合类型的选择
- 首先是根据自己的实际场景需要选择是否需要线程安全集合
普遍来说,线程安全因为同步块的存在其效率会明显不如非线程安全集合
注意线程安全集合仅仅只能保证自身提供操作的线程安全,不能保证组合操作的线程安全 - 总体来说
数组系的优势在于遍历快随机读取快,缺点是增删慢,扩容策略有内存浪费.
链表系的优势在于遍历快增删快,无界优势表示没有扩容带来的内存浪费,缺点是随机读取慢
哈希系的优势在于随机读取快增删快,缺点是遍历慢.
equals&hashCode
原则上一个对象如果重写了hashCode方法,必须同时重写equals.这是因为难以预料该对象是否会用于哈希键中.反过来说,如果使用一个非基本类型的对象作为键,也需要检查其对象hashCode和equals是否匹配
保证两个对象如果equals相同,则hashCode必须相同
根本原因在于,基于哈希散列不允许键重复.其判定规则如下
- 首先比较两个对象的hashCode是否一致,如果不一致将直接视为不重复
-
但hashCode冲突(两个不同对象的哈希值相同)是非常普遍的,所以哈希比较之后会进一步调用equals方法比对是否是相同对象,equals的判定结果将作为最终结果
- 一个更好的hashCode,可以加快存取速度
- 而一个不匹配的hashCode,会造成无法判定唯一而不断写入对象,造成内存泄露
哈希冲突
哈希冲突是基于哈希表的集合都必须解决的问题
哈希冲突是指两个不同对象有一样的hash值.也就是说通过无法一个哈希值判定两个对象唯一
解决哈希冲突的常见思路有
- 再哈希
再哈希是一种最简单的解决方案,并且性能也相当不错.但问题是在于不能保证第二次哈希唯一,所以极端情况下,需要N次哈希才能解决 - 链表法
链表法也是一种相当简单的思路.优势在于一次链表必定解决哈希冲突,劣势在于哈希冲突激烈时性能骤降.极端情况下可能会有彻底失去哈希优势蜕变了链表的可能
java.util.ConcurrentModificationException
快速失败(fail-fast)机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。 例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的数量被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
// 抛出 java.util.ConcurrentModificationException
list.remove(integer);
}
要避免这个Exception，可以使用递归器的remove()方法
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
//这种在没有线程安全的情况下没有问题的
//因为递归器remove方法会同步一次集合数量
//但因为这只是一次非线程安全的同步集合数量,所以多线程下依然会有问题
//此时还必须使用同步块才能真正解决
iterator.remove(integer);
}
常见集合对比
HashMap & HashTable & ConcurrentHashMap
- HashMap不是线程安全,允许K,V为null(K为null时固定写在0处)
- HashTable是线程安全的,但因为锁全段所以线程安全性能较低,K,V都不允许为null
- ConcurrentHashMap是高效的线程安全(1.8前锁分段机制,以及final,volatile修饰带来的无锁读取)
注意ConcurrentHashMap在诸如size,contains时会锁全段
JDK1.8后锁Node,并且加入了CAS以提高性能,不过依然采用synchronized而没有使用ReentrantLock