jdk1.8源码填坑计划-4-List、Set和Queue

这里是个开局两张图,内容全靠编系列。

集合

集合

java有好多个集合,各有各的用法,其中都继承于Collection接口和Map接口。对于Map接口的这个分支会在下一篇中谈到,这里仅讨论Collection接口下方的集合类。

Collection

Java的集合类均放在java.util包中,是存放多个对象的容器。集合中其实存放的都是对象的引用,所以集合中可以存储不的类型。
由图中可以看出Collection接口继承了 Iterable 接口,而Iterable的接口主要使用了Iterator,这一接口是用来遍历集合中的所有元素的,主要使用hasNext、next、remove这三个方法。Iterator又派生出ListIterator和LinkedIterator,实现了随机访问、向后遍历、向前遍历等功能。
继承Collection的接口有List Set Queue 这三个我们日常开发中都经常用到。

List

ArrayList LinkedList Vector这三个东西是List接口的三个实现,但是Vector由于古老并且效率底下,已经被淘汰,所以List的实现一般就ArrayList和LinkedList。
这三个的源码我没认真看过,但是我完全知道其内部构造。

List的实现

ArrayList 其底层就是数据,随机访问速度快,但是增加和删除慢,线程不安全,效率高。
Vector 这是线程安全的ArrayList,效率低,据说已经被淘汰了,我从没有用过。
LinkedList 底层是双向链表,随机访问速度慢,但是增加和删除快,线程不安全,效率高。

Vector和ArrayList

两个很相似,底层都是采用了数组的方式来完成。Vector有些特性导致了这成为了一些缺陷,最终已经不被推荐使用了。

  • Vector采用了synchronized来保证线程安全,效率自然就低。
  • Vector初始化空间要求是连续的存储空间,这导致内存较小的时候会分配失败。
  • Vector空间满了之后,会扩容一倍,而ArrayList扩容50% (Vector构造方法里有个扩容因子可以设定的,用来设定每次扩容多大,没设定就扩容为原来一倍)

后来就渐渐被遗弃了,为了让ArrayList实现线程安全,采用如下策略

1
2
List<String> list1 = Collections.synchronizedList(new ArrayList<String>());
List<String> list2 = Collections.synchronizedList(new LinkedList<String>());

当然如果要为了实现线程安全,肯定是优先使用java.util.concurrent包下的类,而不是用上面这个方法把java.util包下的类改造成线程安全的。

Set

日常使用的Set的实现有HashSet,LinkedHashSet,TreeSet,EnumSet这几个
我本来以为Set中我会写挺多东西,可是看了这几个的源码之后哈哈大笑,我从未见过如此厚颜无耻之人!当然这是开玩笑的,这样设计非常巧妙。
HashSet和HashMap其实是一样的,HashSet内部就是一个HashMap,只是value设置为了new Object(), 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
................
}

同样的LinkedHashSet只是把这里的HashMap换成了LinkedHashMap。
同样的TreeSet只是把这里的HashMap换成了NavigableMap。
但是EnumSet和EnumMap没有关系,这是专门给枚举写的一个抽象类,其实现由常规的和大量的两种:RegularEnumSet、JumboEnumSet,小于64个元素的情况就用常规的,这么做是因为EnumSet的实现非常像bitmap算法(有个专门的BitSet来做了bitmap算法),开辟一个64位的二进制数,然后根据坐标调整这个数坐标的值是0或者1,使用位运算来计算,因此EnumSet要比用HashSet什么的快不少。

这里列出这几个set的特点

名称 内部实现 是否有序 特点
HashSet HashMap 无序 查询效率高
LinkedHashSet LinkedHashMap 有序 继承自HashMap链表保证了添加顺序,哈希表保证唯一
TreeSet NavigableMap 红黑树 有序 必须放同样对象且实现Comparable 接口,擅长按照范围查找
EnumSet 类bitmap算法 无序 只能用Enum,速度快

对于Set中的这些源码要放到下一节Map中解析才合适。

异常ConcurrentModificationException

这是一个很容易搞出来的异常,写代码的时候还感觉理所当然,但是只要考虑到这些线程不安全的东西,应该不会犯这个错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//  阿里巴巴的java手册
// 【强制】不要在foreach循环里进行元素的remove/add操作。remove元素请使用Iterator方式,如果并发操作,需要对Iterator对象加锁。
Negative example:
List<String> originList = new ArrayList<String>();
originList.add("22");
for (String item : originList) {
//warn
list.add("bb");
}

Positive example:
Iterator<Integer> it=b.iterator();
while(it.hasNext()){
Integer temp = it.next();
if (delCondition) {
it.remove();
}
}

一个集合自己在遍历中修改自己,或者一个集合在被两个线程调用,一个遍历一个修改,经常会出现这个ConcurrentModificationException异常,这个异常抛出的地方在这里

1
2
3
4
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

modCount每被修改(包括add和remove等方法)一次就会变更一次,而expectedModCount是暂存在其迭代器iterator内部的,用来保证这些add和remove等危险操作导致集合数据混乱。用iterator的next来进行遍历修改,从根本上保证了modCount和expectedModCount相等。

Queue

队列是一种特殊的链表,这个链表中只能对头尾进行操作,LinkedList就实现了Dueue(Queue的子接口)接口,也不一定非得FIFO,LIFO也是完全可以的,对于Queue的大部分实现类都写在了java.util.concurrent下,只有LinkedList和ArrayDeque和PriorityQueue。
LinkedList和ArrayDeque就像LinkedList和ArrayList一样,只是双端队列的基于链表和数组的两种实现方式,所以这俩的区别就是的数组和链表的区别。
反而PriorityQueue是个奇葩,这并不是标准的队列,既不符合FIFO策略也不符合LIFO策略,而是按队列元素的大小进行重新排序!也就是说PriorityQueue中放的数据必须要实现Comparable接口,这点有点像TreeSet,但是我感觉更像的是Redis的Zset这个数据结构,会根据score进行排序,然后根据数据进行poll和offer。简直了。

0%