第七章:深入集合Collection

7.1 集合框架与ArrayList

如图1所示,是Java常见的一些集合框架的类。最上面是Collection,它有两个子接口,List和Set。这些List有一些类来实现这个借口,比如说AbstractList,在AbstractList下面还有Vector Stack,还有ArrayList等。但是对于set这个接口来说,下面也实现了很多类。最右端是Map这个借口,实现它的有HashMap等等。

1523867566600983.jpg

图1

1.ArrayList

List借口的可变数组实现。实现了所有可选列表操作,并允许包括null在内的所有元素,它是非线程安全。它的底层使用的数据结构是数组,适合查找修改,弱于删减

例:ArrayList实现分析

第四行是用来检查index是否符合范围要求。下面这一行取出index值保存在oldValue中,将下标为index的值设置为新的,然后把旧的元素值返回。

下面是增加元素的方法。首先确保还有一个额外容量,然后把值赋值给最后一个元素,返回true代表增加成功了。

首先判断下标index是否大于尺寸,或者index小于0,这就说明数组长度不足,需要对数组进行扩容,这个时候就抛出一个错误来。接下来确定数组的容量是能够容纳的。arraycopy就是把列表中若干值进行拷贝,也就是说所有元素往后拷贝1位。然后把值复制给空的那个地方。这样的操作代价还是很大的,所以性能并不好。

    获取旧容量大小给oldcapacity。如果指定最小的容量比原有还要大,那么先扩大1.5,如果扩充后这个长度比需要的最小长度还要小,那么直接设置为mincapacity的大小。然后把原来列表的数据直接复制给新的数组。

7.2 LinkedList

LinkedList是List借口的链接列表实现,它可以实现所有的可选列表操作,并且允许所有元素(包括null),它实现Deque借口,为add、poll提供FIFO队列操作以及其他堆栈和双端队列操作。该实现是非线程安全的。当我们在编程序时,如果用到这个链表,并且是多线程去访问这个链表的时候,需要自己加XX(没听清),LinkedList不做同步与互斥来控制,需要你自己写程序来解决这个问题。它适合增减,弱于查改

例:LinkedList数据结构

header是链表的头,三个空在后面有指。这个结点中包含三个元素,element是值,next是当前节点的下一个节点是什么,previous是前一根节点是什么。后面的构造方法指定了这三个元素的内容。

这个方法是用来根据给定序号获取这个节点的值。首先判断序号是否越界,若越界则抛出异常类,否则继续进行。然后先设置链接到链表的头部,也就是从头部开始进行遍历。然后开始判断所给定的序号比列表一半的长度小还是长度达。若比长度右移一位(this.size>>1代表右移一位,实际上也就代表着长度除以2,这是我们在学二进制的时候就学过的)小,那么就从表头开始,一步一步往下找,直到找到我们需要的序号的元素,然后输出值。若大于,则同理。

实例化一个新的节点,这个时候我们必须指定这个结点放在哪里。

List的适用范围

(1)ArrayList适用于对于数据查询修改大于数据增加删除的场合;

(2)LinkedList适用于对于数据增删大于数据查询的场合。

7.3 HashMap与HashTable

1.HashMap(哈希映射)

它是基于哈希表的Map借口的实现,提供所有可选的映射操作,并允许使用null值和null键。它是非线性安全的。它不保证映射的顺序,特别是不保证顺序恒久不变的。HashMap的数据结构如图2所示。

1523867648129678.jpg

图2

代码描述版:

第一行就是设置一个数组,类型是Entry。第二行说明这个Entry。后面说明是Entry是一个列表等等。

总结来说,HashMap底层就是一个数组结构,数组中的每一项又是一个链表,先建一个的时候就会初始化这么一个数组,Entry就是数组中的元素,那么每个Map Entry就是一个K value对,它只有一个向下的指针来指示我们下一个元素,这就构成了链表。

例:如何向HashMap中添加元素

例:hash函数,加入高位计算,防止地位不变,高位变化时,造成hash冲突

代码:

例:HashMap的get操作

2.HashTable(哈希表)

    HashTable和HashMap采用相同的存储机制,二者的实现基本一致。但是HashTable不允许NULL存在。HashTable是线程安全的,内部的方法基本都是synchronized。它的迭代器具有强一致性。

7.4 TreeMap与LinkedHashMap

1.TreeMap

它实际上是Map接口的树实现,不允许null值存在,非线性安全,键值有序。它的数据结构实际是采用了红黑二叉树,是一个自平衡二叉查找树,在进行插入和删除操作时,通过特定的操作能够保持二叉查找树的平衡,从而获得较高的查找性能。它的优点是做查找、插入和删除操作的时间是O(logn)。

如图3所示,Entry是红黑树的结点,它包含了红黑树的6个基本组成成分:key、value、left(左孩子)、right(右孩子)、parent、color。Entry节点根据key进行排序,本身entry节点包含的内容为value。红黑树排序时,根据entry中的key进行排序,entry中的key比较大小是根据比较器comparator来进行判断的。

1523867700555969.jpg

图3

TreeMap的优点:

(1)空间利用率高:HashMap的数组大小必须为2的n次方;TreeMap中树的每一个节点就代表了一个元素。

(2)性能稳定:Hash碰撞会导致HashMap查询开销提高;HashMap扩容时会rehash,开销高;TreeMap的操作均能在O(logn)内完成。

2.LinkedHashMap

Map接口的哈希表和链接列表实现,提供所有可选的映射操作,并允许使用null值和null键,非线程安全,具有可预知的迭代顺序。

例:LinkedHashMap实现分析

如图4所示。

1523867722709780.jpg

图4

HashMap第一级是数组,第二级是单向链表;而这个第二级结构是一个双向链表。

3.Map的适用范围

(1)HashMap适用于一般的键值映射需求;

(2)HashTable适用于有多线程并发的场合;

(3)TreeMap适用于要按照键排序的迭代场合;

(4)LInkedHashMap适用于特殊顺序的迭代场合(如LRU算法)。

7.5 HashSet

1.HashSet

它实现Set借口,由哈希表支持,允许使用null元素。非线程安全,不保证set的迭代顺序,特别是不保证该顺序恒久不变。

例:HashSet的实现分析

1523867741571214.jpg

图5

2.Set的特点

(1)HashSet通过HashMap实现;

(2)TreeSet通过TreeMap实现;

(3)LinkedHashSet通过LinkedHashMap实现;

(4)Set类与Map类拥有近似的使用特性。