疯狂Java笔记之常见java集合的实现细节

Set和Map

1.Set和Map的关系

首先Set是一种集合元素无序，不可重复的集合。而Map则代表一种有多个key-value对组成的集合，Map集合类似于传统的关联数据。看起来他们没哟什么关联，实际上Set和Map是有莫大的关联的。可以说Map是Set集合的扩展。

当我们只看Map的Key时，会发现所有的key不能重复，key之间没有顺序。也就是说将Map所有的key集合起来就组成了一个set集合。Map也提供了如下方法来返回组成的set集合

Set<K> keySet()

对于一个Map集合而言，它本质上是一个关联数组，关联数组中的key-value对之间有严格的对应关系，那将key-value对捆绑在一起对待，如下所示：

java4.PNG

2.HashMap和HashSet

在HashSet里，系统采用Hash算法决定集合元素的存储位置，这样可以保证快速存，取集合元素；对于HashMap而言，系统将value当初key的‘附属物’，系统根据Hash算法开决定key的存储位置，这个可以保证快速存，取集合key,而value总是紧随key存储。

集合号称存储的是Java对象，但实际上并不会真正将Java对象放入Set集合中，而只是在Set集合中保留这些对象的引用而己。也就是说，Java集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的Java对象。对于java集合他只是多个引用变量的集合。

当程序试图将一个key-value对放入HashMap中时，首先根据该key的hashCade()返回值决定该Entry的存储位置—如果两个Entry的key的hashCade返回值相同，那么它们的存储位置相同:如果这两个Entry的key通过equals比较返回true，则新添加Entry的value将覆盖集合中原有Entry的value，但key不会覆盖;如果这两个Entry的key通过equal比较返回false ,则新添加的Entry将与集合中原有的Entry形成Entry链，而且新添加的Entry位于Entry链的头部

当系统开始初始化HashMap时，系统会创建一个长度为capacity的Entry数组。这个数组可以存储元素的位置被称为“桶(bucket)”,每个bucket都有其指定的索引，系统可以根据其索引快速访问该bucket里存储的元素。

无论何时，HashMap的每一个“桶”只存储一个元素(即一个Entry).由于Entry对象可以包含一个引用变量（就是Entry构造器的最后一个参数）用于指向下一个Entry，因此可能出现：HashMap的bucket中只有一个Entry,但这个Entry指向另一个Entry这就形成一个Entry链，如图:

set.PNG

HashMap在每一个bucket里只有一个Entry,所以可以根据索引快速取出该bucket里的Enrty.当发生hash冲突时，单个bucket里存储的不是一个Entry,而是一个Entry链，系统会按顺序遍历每个Entry,知道找到想搜到的Entry为止，即使要搜索的末端，系统也会循环到最后找到该元素。

3.TreeMap和TreeSet

TreeSet底层实际使用的容器就是TrenMap.绝大部分的方法都是直接调用TreeMap的方法来实现的。而对于TreeMap而言，它采用一种被称为‘红黑树’的排序二叉树来保存Map中的每个Entry即每个Entry都是红黑树的一个节点。

对于TreeMap向言，由于它底层采用一棵红黑树来保存集合中的Entry，这意味着TreeMap添加元素、取出元素的性能都比HashMap低。当TreeMag添加元素时，需要通过循坏找到新 增Entry的插入位置，因此比较耗性能;当从TreeMap中取出元素时，需要通过循环才能找到合适的Entry，也比较耗性能·但TreeMap, TreeSet相比HashMag,HashSet的优势在于:'TreeMap中的所有Entry总是按key根据指定的排序规则保持有序状态，TreeSet中的所有元素总是根据指定的排序规则保持有序状态。

Map和List

1.Map的values()方法

不管是HashIvlap，还是TreeMap，它们的values()方法都可返回其所有value组成的Collection集合。按照通常理解，这个Collection集合应该是一个List集合，因为Map的多个valu。允许重复。 但实际上，HashMap,TreeMap的values()方法的实现要更巧妙。这两个Mad对象的values()方法返回的是一个不存储元素的Collection集合，当程序遍历Collection集合时，实际上就是遍历Map对象的value

HashMap和TreeMap的values()方法并未把Map中的value重新组合成一个包含元素的集合对象，这样就可以降低系统内存开销。

2.Map和List的关系

• 从底层实现来看，Set和Map很相似；从用法的角度来看，Map和List也有很大的相似之处。

1.Map接口提供了get(K key)方法，允许Map对象根据key来取得value. 2.List接口提供了get(int index)方法，允许list对象根据元素索引来取得value

Map和List在底层实现上没有太大的相似之处，只是用法有一些相似之处。

ArrayList和LinkedList

1.Vector和ArrayList的区别

Vector和ArrayList这个两个集合类的本质并没有太大的不同，它们都实现了List接口，而且底层都是基于Java数组来存储集合元素的。

此外从序列化机制的角度看，ArrayList的实现比Vector的实现更安全 另外Vector是ArrayList的线程安全版本，ArrayList和Vector觉大部分方法的实现都是相同的，只是Vector的方法增加了synchronized修饰。

2.ArrayList和LinkedList的实现差异

List代表一种线性表的数据结构。ArrayList则是一种顺序存储的线性表，ArrayList底层采用数组来保存每个集合元素，LinkedList则是一种链式存储的线性表，其本质上就是一个双向链表，但它不仅实现了List接口，还实现了Deque接口。也就是说，LinkedList既可以当成双向链表使用，也可以当成队列使用，还可以当成栈来使用(Deque代表双端队列，既具有队列的特征.也具有栈的特征)。

ArrayList 因为ArrayList底层数据结构是数组，所以我们插入元素是需要完成两件事:

• 保证ArrayList底层封装的数组长度大于集合数据长度
• 插入之前将所有元素“整体搬家”，向后移动一格

同理在删除元素是也要对元素进行“整体搬家”，这就导致增加和删除的性能非常差，当时在取出数据元素时，性能基本和数组是一样的。

LinkedList 因为LinkedSet是采用双向链表的，如果单纯的添加某个节点性能是很好的，当时如果需要指定索引处添加节点，LinkedList必须必须先找到索引处的节点，这个搜索过程系统开销也是不少的，删除也同理，如下图所示：

LinkedList.PNG

LinkedList2.PNG

不过弊端是对于ArrayList而言，由于它底层采用数组来保存集合元素，因此可以直接根据数组索引取出index位置的元素;但对于LinkedList就比较麻烦，LinkedList必须逐个元素地搜索，直到找到第index个元素为止。所以性能相对较低。

3.ArrayList和LinkedList的性能分析和适用场景

当程序需要以get(int index)获取List集合指定的索引出的元素，ArrayList性能大大的优于LinkedList。因为ArrayList底层以数组来保存集合元素，所以调用get(int index)方法获取指定索引处的元素时，底层实际调用elementData[index]来返回改元素，因此性能非常好，而LinkedList则必须逐个的搜索。

当程序调用add(int index,Object obj)向List添加数据是，ArrayList需要“整体搬家”才能实现添加，而LinkedList需要找到索引而不用整体搬家，当时找索引也需要消耗一些系统性能，因为他是逐个搜索。同理，删除也是这样子。

当添加的数据个数大于底层数组的长度时，那么ArrayList必须创建一个长度为原来长度1.5倍的数组，再由垃圾回收机制进行回收。这样系统开销也有点大了。而LinkedList就不存在这个问题。

不过从大多数应用场景来说ArrayList总体性能还是优于LinkedList。

Iterator迭代器

1.Iterator实现类与迭代器模式

Java的lteratar和Enumeration两个接口都是迭代器模式的代表之作，它们就是迭代器模式里的“迭代器接口”。所谓迭代器模式指的是，系统为遍历多种数据列表、集合，容器提供一个标准的“迭代器接口”，这些数据列表、集合、容器就可面向相同的“迭代器接口”编程，通过相同的迭代器接口访问不同数据列表‘集合、容器里的数据.不同的数据列表、集合、容器如何实现这个“迭代器接口”， 则交给各数据列表、集合、容器自己完成。

2.迭代是删除指定元素

对于TreeSet, HashSet等Set集合而言，当使用Iterator遍历它们时，如果正在遍历最后一个集合元素，那么使用Set集合的remove()方法删除集合的任意元素并不会引发ConcurrentModificatianException异常，当正在遍历其他元素时删除集合的任意元素都将引发该异常。