Java汇合类的详解

一.汇合的简述

汇合类是用来寄存某类对象的。汇合类有一个独特特点，就是它们只包容对象（实际上是对象名，即指向地址的指针）。这一点和数组不同，数组能够包容对象和简略数据。如果在汇合类中既想应用简略数据类型，又想利用汇合类的灵活性，就能够把简略数据类型数据变成该数据类型类的对象，而后放入汇合中解决，但这样执行效率会升高。

汇合类包容的对象都是Object类的实例，一旦把一个对象置入汇合类中，它的类信息将失落，也就是说，汇合类中包容的都是指向Object类对象的指针。这样的设计是为了使汇合类具备通用性，因为Object类是所有类的先人，所以能够在这些汇合中寄存任何类而不受限制。当然这也带来了不便，这令应用汇合成员之前必须对它从新造型。

汇合类是Java数据结构的实现。在编写程序时，常常须要和各种数据打交道，为了解决这些数据而选用数据结构对于程序的运行效率是十分重要的。

汇合类是Java数据结构的实现。Java的汇合类是java.util包中的重要内容，它容许以各种形式将元素分组，并定义了各种使这些元素更容易操作的办法。Java汇合类是Java将一些根本的和应用频率极高的根底类进行封装和加强后再以一个类的模式提供。汇合类是能够往里面保留多个对象的类，寄存的是对象，不同的汇合类有不同的性能和特点，适宜不同的场合，用以解决一些理论问题。

二.汇合的分类

Java中的汇合类能够分为两大类：

一类是实现Collection接口；另一类是实现Map接口。

Collection是一个根本的汇合接口，Collection中能够包容一组汇合元素（Element）。

Map没有继承Collection接口，与Collection是并列关系。Map提供键（key）到值（value）的映射。一个Map中不能蕴含雷同的键，每个键只能映射一个值。

Collection有两个重要的子接口List和Set。List表白一个有序的汇合，List中的每个元素都有索引，应用此接口可能精确的管制每个元素插入的地位。用户也可能应用索引来拜访List中的元素，List相似于Java的数组。Set接口的特点是不能蕴含反复的元素。对Set中任意的两个元素element1和element2都有elementl.equals（element2）= false。另外，Set最多有一个null元素。此接口模拟了数学上的汇合概念。

Collection接口、List接口、Set接口以及相干类的关系如图1所示。

1.List

List接口扩大自Collection，它能够定义一个容许反复的有序汇合，从List接口中的办法来看，List接口次要是减少了面向地位的操作，容许在指定地位上操作元素，同时减少了一个可能双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的局部实现，AbstractSequentialList扩大自AbstractList，次要是提供对链表的反对。上面介绍List接口的两个重要的具体实现类，也是咱们可能最罕用的类，ArrayList和LinkedList。

1.1ArrayList

通过浏览ArrayList的源码，咱们能够很分明地看到外面的逻辑，它是用数组存储元素的，这个数组能够动态创建，如果元素个数超过了数组的容量，那么就创立一个更大的新数组，并将以后数组中的所有元素都复制到新数组中。假如第一次是汇合没有任何元素，上面以插入一个元素为例看看源码的实现。

1、找到add()实现办法。 public boolean add(E e) { ensureCapacityInternal(size + 1);  // Increments modCount!! elementData[size++] = e; return true; }2、此办法次要是确定将要创立的数组大小。 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); }3、最初是创立数组，能够显著的看到先是确定了增加元素后的大小之后将元素复制到新数组中。 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

1.2LinkedList

同样，咱们关上LinkedList的源文件，不难看到LinkedList是在一个链表中存储元素。

在学习数据结构的时候，咱们晓得链表和数组的最大区别在于它们对元素的存储形式的不同导致它们在对数据进行不同操作时的效率不同，同样，ArrayList与LinkedList也是如此，理论应用中咱们须要依据特定的需要选用适合的类，如果除了在开端外不能在其余地位插入或者删除元素，那么ArrayList效率更高，如果须要常常插入或者删除元素，就抉择LinkedList。

1.3CopyOnWriteArrayList

CopyOnWriteArrayList，是一个线程平安的List接口的实现，它应用了ReentrantLock锁来保障在并发状况下提供高性能的并发读取。

2.Set

Set接口扩大自Collection，它与List的不同之处在于，规定Set的实例不蕴含反复的元素。在一个规定集内，肯定不存在两个相等的元素。AbstractSet是一个实现Set接口的抽象类，Set接口有三个具体实现类，别离是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。

2.1HashSet

散列集HashSet是一个用于实现Set接口的具体类，能够应用它的无参构造方法来创立空的散列集，也能够由一个现有的汇合创立散列集。在散列集中，有两个名词须要关注，初始容量和客座率。客座率是确定在减少规定集之前，该规定集的丰满水平，当元素个数超过了容量与客座率的乘积时，容量就会主动翻倍。

从输入后果咱们能够看到，规定集里最初有4个元素，而且在输入时元素还是无序的。

2.2LinkedHashSet

LinkedHashSet是用一个链表实现来扩大HashSet类，它反对对规定集内的元素排序。HashSet中的元素是没有被排序的，而LinkedHashSet中的元素能够依照它们插入规定集的程序提取。

2.3TreeSet

TreeSet扩大自AbstractSet，并实现了NavigableSet，AbstractSet扩大自AbstractCollection，树形集是一个有序的Set，其底层是一颗树，这样就能从Set外面提取一个有序序列了。在实例化TreeSet时，咱们能够给TreeSet指定一个比拟器Comparator来指定树形集中的元素程序。树形集中提供了很多便捷的办法。

3.Queue

队列是一种先进先出的数据结构，元素在队列开端增加，在队列头部删除。Queue接口扩大自Collection，并提供插入、提取、测验等操作。

上图中，办法offer示意向队列增加一个元素，poll()与remove()办法都是移除队列头部的元素，两者的区别在于如果队列为空，那么poll()返回的是null，而remove()会抛出一个异样。办法element()与peek()次要是获取头部元素，不删除。

接口Deque，是一个扩大自Queue的双端队列，它反对在两端插入和删除元素，因为LinkedList类实现了Deque接口，所以通常咱们能够应用LinkedList来创立一个队列。PriorityQueue类实现了一个优先队列，优先队列中元素被赋予优先级，领有高优先级的先被删除。

如后面提到的，Map接口与Collection接口不同，Map提供键到值的映射。Map接口提供三种Collection视图，容许以键集、值集或键一值映射关系集的模式查看某个映射的内容。Map接口及其相干类的关系如图2所示。

1.HashMap

HashMap是基于哈希表的Map接口的非同步实现，继承自AbstractMap，AbstractMap是局部实现Map接口的抽象类。在平时的开发中，HashMap的应用还是比拟多的。咱们晓得ArrayList次要是用数组来存储元素的，LinkedList是用链表来存储的，那么HashMap的实现原理是什么呢？先看上面这张图：

在之前的版本中，HashMap采纳数组+链表实现，即应用链表解决抵触，同一hash值的链表都存储在一个链表里。然而当链表中的元素较多，即hash值相等的元素较多时，通过key值顺次查找的效率较低。而JDK1.8中，HashMap采纳数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

上面次要通过源码介绍一下它的实现原理。

HashMap存储元素的数组
transient Node<K,V>[] table;</pre>

数组的元素类型是Node<K,V>，Node<K,V>继承自Map.Entry<K,V>，示意键值对映射。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; //构造函数 ( Hash值键值下一个节点 ) Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey()        { return key; } public final V getValue()      { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
接下来咱们看下HashMap的put操作。
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;  //如果没有初始化则初始化table if ((p = tab[i = (n - 1) & hash]) == null) //这里 (n-1)&hash 是依据hash值得到这个元素在数组中的地位（即下标） tab[i] = newNode(hash, key, value, null); //如果数组该地位上没有元素，就间接将该元素放到此数组中的该地位上 else { Node<K,V> e; K k; //第一节节点hash值同，且key值与插入key雷同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //属于红黑树解决抵触 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { /链表解决抵触 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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)))) break; p = e; } } //更新hash值和key值均雷同的节点Value值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
接下来咱们看下HashMap的get操作。
 final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //如果第一个节点是TreeNode,阐明采纳的是数组+红黑树结构解决抵触 //遍历红黑树，失去节点值 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null &&  key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

到这里HashMap的大抵实现原理应该很分明了，有几个须要关注的重点是：HashMap存储元素的形式以及依据Hash值确定映射在数组中的地位还有JDK 1.8之后退出的红黑树的。

在HashMap中要找到某个元素，须要依据key的hash值来求得对应数组中的地位。对于任意给定的对象，只有它的hashCode()返回值雷同，那么程序调用hash(int h)办法所计算失去的hash码值总是雷同的。咱们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的散布相对来说是比拟平均的。然而，“模”运算的耗费还是比拟大的，在HashMap中，(n - 1) & hash用于计算对象应该保留在table数组的哪个索引处。HashMap底层数组的长度总是2的n次方，当数组长度为2的n次幂的时候，(n - 1) & hash 算得的index雷同的几率较小，数据在数组上散布就比拟平均，也就是说碰撞的几率小，绝对的，查问的时候就不必遍历某个地位上的链表，这样查问效率也就较高了。

2.LinkedHashMap

LinkedHashMap继承自HashMap，它次要是用链表实现来扩大HashMap类，HashMap中条目是没有程序的，然而在LinkedHashMap中元素既能够依照它们插入图的程序排序，也能够按它们最初一次被拜访的程序排序。

3.TreeMap

TreeMap基于红黑树数据结构的实现，键值能够应用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，应用它能够确保图中的条目是排好序的。

在理论应用中，如果更新图时不须要放弃图中元素的程序，就应用HashMap，如果须要放弃图中元素的插入程序或者拜访程序，就应用LinkedHashMap，如果须要使图依照键值排序，就应用TreeMap。

4.ConcurrentHashMap

Concurrent，并发，从名字就可以看进去ConcurrentHashMap是HashMap的线程平安版。同HashMap相比，ConcurrentHashMap不仅保障了拜访的线程安全性，而且在效率上与HashTable相比，也有较大的进步。

三.汇合的特点

汇合类的特点有三个：

第一点，汇合类这种框架是高性能的。对根本类集（动静数组，链接表，树和散列表）的实现是高效率的。个别人很少去改变这些曾经很成熟并且高效的APl；

第二点，汇合类容许不同类型的汇合以雷同的形式和高度互操作形式工作；

第三点，汇合类容易扩大和批改，程序员能够很容易地稍加革新就能满足本人的数据结构需要。