一. 结构图

171415468703867

  • Produces表示

二. Collection详解

1. 集合基本接口

  • Collection
    通过上图可观察出Collection为所有集合的根接口,实际该接口仍然继承了一个接口Iterable,Iterable定义了创建迭代器(Iterator)的方法,因此所有集合(map接口并没有继承Collection接口)均可创建迭代器对象(详见迭代器设计模式)。该接口定义了一系列集合的基本公用方法如size(),add(),remove()等。

  • Iterator
    迭代器接口,包含了hasNext(),next(),remove()三个方法,对数据存储对象(即集合)进行遍历,移除,使用迭代器可以在不关心数据存储细节的情况下,对存储数据进行遍历,比如抽象类AbstractList中并未定义数据如何存储,但是却通过迭代器的方式实现了remove等方法

  • ListIterator(上图中的LinkIterator是错误的)
    继承了Iterator接口,Iterator的定位是所有的java数据对象的迭代器对象,ListIterator继承了Iterator对象,通过名字就可以知道ListIterator为集合的迭代器对象,在Iterator的基础上又新增了一些针对List类集合的方法如previous(),nextIndex(),previousIndex()等,针对List类集合添加这些方法的原因是list是有序的,而set是无序的,但是需要注意的是ListIterator并不是通过iterator方法返回的,换句话说就是List并没有重写Iterable的itreator方法返回ListIterator,而是新增了一个listIterator()方法返回ListIterator对象(原因不明)。

  • List Set Queue
    List相比Set,最大的区别是set中不允许保存重复对象,而List可以保存重复对象,另外List比Set中多了一些通过index操作数据的方法,因为List是有序的,而Set是无序的(不按存储顺序排序)。而Queue是队列,包含了方法poll()【移除并返问队列头部的元素】,peek()【返回队列头部的元素】等方法。如果仔细的话会发现Collection中已经声明了add方法,但是List Set Queue继承了Collection,但是又声明了一遍完全一样的add方法,感觉这完全是无必要的,查询很多资料后总结为:其实只是定义的接口行为不一样。表示子类如果实现List接口,那就需要遵循List Javadoc的行为。如果实现Collection那就必须要遵循Collection Javadoc的行为。不单单只是重写一个方法而已,重写这个方法的时候应该按照Javadoc所描述的一样。这样才正确。

  • AbstractCollection,AbstractList,AbstractSet
    Collection,List,Set接口均存在一个与之对应的抽象类AbstractCollection,AbstractList,AbstractSet。由于List,Set继承了接口Collection,而AbstractList是List的实现,所以AbstractList在继承AbstractCollection的同时实现了接口List

2. set具体实现类

HashSet TreeSet LinkedHashSet

  • TreeSet: 目前jdk中唯一的SortedSet接口实现类,有序的set集合,正常感觉set都是无序不可重复的,TreeSet为有序的,是不是与set的定义冲突了呢,其实set也是有序的,包括hashset对象,只不过set的有序与list不同,list是按存储的顺序保存而set并不是按存储的顺序保存(所以总是被误解为无序),如hashset是通过对象的hashcode排序存储,而treeset默认是按照元素的自然顺序排序,也可以通过指定比较器(Comparator)的方式,使数据按照特定的顺序排序。实际存储使用的是TreeMap
  • HashSet: 平时用的最多,通过对象的hash码顺序保存数据。实际存储使用的是HashMap
  • LinkedHashSet: LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍微逊色于HashSet。实际存储使用的是LinkedHashMap

所以了解HashSet TreeSet LinkedHashSet前需要先了解Treemap Hashmap LinkedHashMap

3. list具体实现类

ArrayList与LinkedList

jvm-collection-img1

上图完美的说明了arraylist与linkedlist的存储结构

  • ArrayList 是一个可改变大小的数组.当更多的元素加入到ArrayList中时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组.
  • arraylist 存储地址是连续的,linkedlist的存储地址不是连续的;而是通过上一个的指向找到下一个数据,所以LinkedList间接实现了queue接口,因为LinkedList比较适合做队列
  • arraylist如果要插入数据,需要将所有欲插入之后 的数据移动 ;而 LinkedList 是一个双链表只需要修改指向,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList.
  • 当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义
linkedList的get(int index)方法:

Entry<E> e = header;
if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }

ArrayList与Vector

jvm-collection-img2

jvm-collection-img3

  • Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized).因此,开销就比ArrayList要大.正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。
  • Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间,而ArrayList每次对size增长50%.

注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。

三. Map详解

1. Map基础接口及抽象类

  • Map
    将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值。该接口定义了一系列对键值对的操作方法,如get(Object),put(K,V)等。
    Set<Map.Entry<K, V>> entrySet() 该方法返回一个实体set集合对象,该set对象由各个Map实体中创建一个继承于AbstractSet的Set对象,之所以没有在各实体类中使用hashSet等现有set的原因是,现有每个set的实体类都有该类自己的迭代器实现,但是不同map中的entryset实现均不同,比如 size直接返回map的size,而不需要重新计算;另外包括 contains及remove在不同的map实现类中方法实现均不同,并且与map.entry深度耦合
  • AbstractMap
    通过迭代器的方式实现了Map中的部分方法,如get方法,先取到实体的Set信息,然后循环判断key是否相等,相等则返回
  • SortedMap
    有序的map接口,它的接口应该支持默认的自然排序及通过指定的比较器排序

2. Map实现类详解

TreeMap

(引用自http://blog.csdn.net/jzhf2012/article/details/8540705)

  • 实现了接口SortedMap,所以TreeMap是一个key有序的数据存储对象
  • TreeMap基于红黑树实现,所有每个Entry存在一个父Entry
  • 通过TreeMap的Entry类可以看到,实体中存在left和right实体对象,指定他的左右节点
    jvm-collection-img4
  • put时,先判断是否存在root,若不存在则直接建为root节点,若存在则将当前节点与root比较,若小于当前节点,则再与root的左节点比较,若大于当前节点,则与root的右节点比较,直到某节点不存在左或右节点,将该节点放在该位置
  • 在put(K key,V value)方法的末尾调用了fixAfterInsertion(Entry<K,V> x)方法,这个方法负责在插入节点后调整树结构和着色,以满足红黑树的要求。(红黑树不详细说,了解以树形结构存储即可)
    • 每一个节点或者着成红色,或者着成黑色。
    • 根是黑色的。
    • 如果一个节点是红色的,那么它的子节点必须是黑色的。
    • 一个节点到一个null引用的每一条路径必须包含相同数量的黑色节点。

HashMap

  • HashMap使用数组和链表两种数据存储形式存储数据
  • 当get数据时,先根据key计算出该数据的数组坐标,若数据位置上存在对象,则使用==及.equal的方式判等,若相等则返回,不等则取到下一个对象判等,若数据该坐标的链状结构不存在相与入参相等的key,则返回null.
  • 当put数据时,先根据key计算出该数据的数组坐标,若当前位置为不存在数据,则直接插入,若当前位置存在数据,则使用链表结构将欲插入的数据插入数组的当前坐标位置上,并将之前的数据保存到新的entry的next上
  • HashMap中存在HashIterator,KeyIterator,ValueIterator,EntryIterator等四个Iterator对象,其中HashIterator为抽象类,其它三个对象均继承HashIterator抽象类,并实现next方法,在三个实现类中均调用nextNode()方法,不同的是EntryIterator的next为nextNode(),KeyIterator为nextNode().key,ValueIterator为nextNode().value,因此hashmap的迭代重点在HashIterator的nextNode方法上
  • 通过下述代码可看出nextNode是先取该对象的next对象,若查询到为null,则查询数据t的下一个index是否为空,直至不为空则返回该对象
Node<K,V> e = next;
if ((next = (current = e).next) == null && (t = table) != null) { 
      do {
      } while (index < t.length && (next = t[index++]) == null);
}
  • HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因子,随着map的size越来越大,Entry[]会以一定的规则加长长度。
  • HashMap不同jdk实现代码有较大区别,重要的是理解逻辑!!!下面的示例为jdk1.6!!!
public V put(K key, V value) {
        // HashMap允许存放null键和null值。     
        // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。 
        if (key == null)
            return putForNullKey(value);
        // 根据key的keyCode重新计算hash值。  
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);

        //循环遍历map,判断当前key在map中是否已存在
       //如果已存在,则替换old值 ,并返回old值
       // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
       //HashMap的结构被修改的次数
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
/*http://www.th7.cn/Program/java/201511/689291.shtml
先复习一下逻辑与,0 & 0 = 0;0 & 1 = 0;1 & 0 = 0;1 & 1 = 1。
第二个参数length始终为2的n次方,所以,换成二进制数就是 100,1000,10000,...(length -1)就是 11, 111,1111,...
这样的话,第一个参数h比第二个参数小的情况下,那结果就是h。第一个参数h比第二个参数大的情况下,如下:
例:h=18 -> 10010 length-1=15 -> 01111   10010&01111-------00010 (即2)
也就是h-length,假设 h=5,length=16, 那么 h & length - 1 将得到 5;
如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……
如果 h=15,length=16, 那么 h & length - 1 将得到 15;
但是当 h=16 时 , length=16 时,那么 h & length - 1 将得到 0 了;
当 h=17 时 , length=16 时,那么 h & length - 1 将得到 1 了这样就能保证取得合理的索引值。
*/
//获取坐标  HashMap存取时,都需要计算当前key应该对应Entry[]数组哪个元素,即计算数组下标
static int indexFor(int h, int length) {
        return h & (length-1);
}
//添加实体,将当前实体插入到table[index]位置上,若之前该位置已存在entry,则将之前的entry,
//以最新的entry对象的next对象属性形式(链表形式)保存
void addEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //如果当前的map size大于了下次的数组长度,则对map重新设置大小为现在的2倍,并对新的数组重新赋值
        if (size++ >= threshold)
            resize(2 * table.length);
    }

Hashtable

与HashMap实现方式一样,但Hashtable属于同步(synchronized)的.
jvm-collection-img5

jvm-collection-img6

LinkedHashMap

(引用自http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html此链接是对jdk6的解释,以下是对jdk8的解释,理解思想最重要)

  • LinkedHashMap继承于类HashMap
  • LinedHashMap可以通过插入顺序或访问顺序遍历对象
  • LinkedHashMap 实现与 HashMap 的不同之处在于,LinkedHashMap 维护着一个运行于所有条目的双重链接列表(通过一个对象可查询该对象的before及after对象)。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。
  • 根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。new LinkedHashMap<String, String>(16,0.75f,true); true表示按访问顺序,false表示按存储顺序
  • LinkedHashMap get方法与HashMap的get方法一致,调用的是HashMap的getNode(hash(key), key),不同的是LinkedHashMap存在两种排序方式,若使用按访问顺序排序的话,在get方法中调用afterNodeAccess(e);将该对象移至尾部
  • jdk8中对map做了一些优化,当节点个数>= TREEIFY_THRESHOLD - 1时,会将链表结构转化为红黑树结构存储。为什么这么做呢?正如我们前面提到的,当发生Hash冲突时,HashMap首先是采用链表将重复的值串起来,并将最后放入的值置于链首,java8对HashMap进行了优化。当节点个数多了之后使用红黑树存储。这样做的好处是,最坏的情况下即所有的key都Hash冲突,采用链表的话查找时间为O(n),而采用红黑树为O(logn),这也是Java8中HashMap性能提升的奥秘。
  • 发现了一个有趣的事情,HashMap中存在一个static final class TreeNode,该类继承于LinkedHashMap.Entry,而LinkedHashMap.Entry继承于HashMap.Node,父类内部类继承子类内部类,为什么不在HashMap中创建LinkedHashMap.entry,LinedHashMap.Entry中直接使用该类,而要用父类的内部类实现子类的内部类,思想上没问题吗?
  • LinkedHashMap 并未重写父类 HashMap 的 put 方法,而是重写了HashMap中调用的子方法,在HashMap中详细讲述了HashMap jdk1.6的put,在这里说一下HashMap jdk 1.8的put方法。(jdk1.6中重写了put方法中调用的子方法void recordAccess(HashMap m) ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现,但是在jdk1.8并不存在这几个方法)
  • 在jdk8的put中直接调用putVal方法,在该方法中如果不存在该实体,则调用HashMap或LinkedHashMap各自的nextNode()方法创建实体对象,如果存在则修改,这里面主要有两个方法,第一就是nextNode()创建实体,不同的HashMap及其子类,创建的实体对象肯定不同,第二就是afterNodeAccess(),该方法是如果现在的数据有替换,则替换后调用该方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//如果该坐标位置不存在对象,则直接创建
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))//判断当前坐标获取的对象key与入参key是否一致
            e = p;
        else if (p instanceof TreeNode)//如果p实例是TreeNode的实例,则调用putTreeValue方法,原因待研究
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //循环当前坐标的下一个实体,如果为null,则直接插入,如果不为null,则一直循环,直到为null或实体的key与入参key一致
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);//创建实体,并将最新的实体赋值给上一实体的next对象
                    //如果条件成立,将链表修改为红黑树结构,jdk8新的优化,所以在get和put时,都有校验 p instanceof TreeNode,这样查找效率从o(n)变成了o(log n) 
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st     
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))//判断实体的key与入参key是否相等
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key   map中已存在该实体
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);//HashMap的该方法是空方法,而LinkedHashMap的该方法,增加了在排序是访问顺序的情况下,对链表重新排序的操作
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    //HashMap的该方法为空方法,LinkedHashMap的该方法虽然不是空方法,但是实际并没有任务的意义,因为removeEldestEntry方法固定返回false
    //这样做的目的是方便开发者可以把Map当cache来用,并且可以限制大小,只需继承LinkedHashMap并重写removeEldestEntry()  
    afterNodeInsertion(evict);
    return null;
}
  • LinkedHashMap 中同样存在四个迭代器LinkedHashIterator,LinkedKeyIterator,LinkedValueIterator,LinkedEntryIterator。其中LinkedHashIterator为抽象类,其它三个继承该类,与HashMap一致,不详述。
  • 四个迭代器的精华为nextNode()方法,nextNode与Entry结合实现了顺序访问形式,以下为jdk8的代码,可见实现代码非常简单,一直获取after对象。但是通过代码可以发现如果直接调用nextNode(),而已经不存在下一个对象,则会抛出异常,所以在调用next()前一定先调用hasNext()方法
final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after;
    return e;
}