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；
第二点，汇合类容许不同类型的汇合以雷同的形式和高度互操作形式工作；
第三点，汇合类容易扩大和批改，程序员能够很容易地稍加革新就能满足本人的数据结构需要。