- title: java集合框架学习总结
- tags:集合框架
- categories:总结
- date: 2017-03-23 19:24:21
好久都想找出个时间来分析分析，总结总结java中的集合容器问题了。趁今天有时间也有兴趣就来看看。不过，网上也有很多码友们各抒己见地对java集合的分析，实践。这都是他们根据自己的理解分析总结过来的，不过也很是值得我借鉴。不过最终还是要根据自己的思考与动手操作来跟深入的了解java的集合框架吧。毕竟在日常开发中像List,Map等非常常见且核心的框架类我们都会经常使用，有时候我们若是更深入的了解这些集合，根据实际情况分析，什么时候使用什么类型的集合，对程序运行，效率，可拓展性等等会有更清楚的认识。在一些不注意的基础细节，其实也是相当重要的。
微信截图_20171119102744.png
Java中的集合框架和分类
在java中,集合就想让与一组类型相同或者异同的对象或者基础数据的集合。那总是要有容器来容纳这些数据吧。就像用一个篮子将散落在地上的鸡蛋盛放起来，或者是用一个格子布局的盒子将石头什么的存放起来，又或者想我们的书架将不同类别的书放置好是一个道理。
将数据保存或者是放入某种容器，那必定是有一套规则的，至于怎么放，是一个一个放，放在那里，还是一次多个存放在指定位置。这些规则都可以通过在设计容器的时候进行设置，就像java中的List,Map等一样，都是用来保存数据的。至于如何将集合中的数据取出，那么就要看list,Map等容器的方法函数设置了。
当将"容器"这个概念简单阐述后，下面就来看看java中的容器有哪些，每种容器在存放哪些数据类型？如何存放一个或者多个数据，如何取出一个或者多个数据？容器的不同的适用场景有哪些？有哪些利弊等方面都可以根据自己认识去分析分析，探讨探讨，当然了，最后还可以从JDKSE源代码中去looklook......
集合类图和分类
[1] Java的容器类图
刚开始自己可以通过对jdk集合类图的层级结构，结合OOP的概念将java中的容器集合大致梳理出来，包括Collection线性集合和KEY-VALUE键值对的MAP图，分别如下:
java_collection.png
A. 从上述的Collection线性集合可以看到，Collection是所有集合层级结构的根，也就是最顶层的接口。一个集合代表了一组可以被称为"元素"的对象。接口Collection中声明的接口是所有集合子类所拥有的通用共有操作，其实就是定义了作为一个集合，应当有什么功能.
Collection中声明的通用操作包括以下几个:
int size(); /*获取集合中元素个数*/
boolean isEmpty(); /*判断集合容器是否为空*/
boolean contains(Object o); /*判断集合中是否有对象o存在*/
Iterator<E> iterator(); /*实现了Iterator接口返回迭代器对象*/
Object[] toArray(); /*将集合元素转换为数组对象*/
<T> T[] toArray(T[] a); /*根据类型T转换成数组元素*/
boolean add(E e); /*一次添加一个对象到集合容器中*/
boolean remove(Object o);/*一次移除集合中的某一个元素*/
boolean containsAll(Collection<?> c);/*判断集合元素中是否包含参数c集合中的所有元素*/
boolean addAll(Collection<? extends E> c);/*一次添加多个元素*/
boolean removeAll(Collection<?> c);/*一次移除多个元素*/
boolean retainAll(Collection<?> c);/*筛选元素*/
void clear();/*清除集合中所有元素*/
boolean equals(Object o);/*定义判断对象是否相等的逻辑*/
int hashCode();/*自定义hash值*/
从上面方法就可以看出，集合基础方法就包括这些：获取集合容器数量，集合转换为数组，单个元素添加，多个元素添加，单个元素移除，多个元素移除等等。另一方面，因为这是根最顶层接口，我们若是自定义集合类，要自己实现全部基础方法的话，也有些太麻烦了。所以，根据上面的图，我们可以看到一个抽象类AbstractCollection。
AbstractCollection是一个抽象类，该类实现了Collection接口，除了将size(),iterator两个方法抽象化，其他的接口方法都有了基础的实现。这就不仅仅给我们提供了便利，其他内部的集合类都有继承了该抽象类，也就具有集合的基础功能。另一方面，若是我们想定义自己的集合类，当然最佳方法就是通过extends来继承该抽象类了。根据OOP的继承理念，我们的集合类也就继承了所有集合特性的基础操作功能。同理，像集合框架中的抽象类，AbstractList,AbstractSet一般都是提供了其实现的接口中方法的基本实现。
然后再可以根据集合内部对象元素是否可以重复，或者说相同。又将集合分支为另外两个方向，不同方向的集合功能通常都是通过Interface接口将功能或者集合特性区分开，以适用于不同的场景：
-
<interface>java.util.List:
List容器内部包含有序的元素集合，可以通过内部元素的索引快速访问和查找每一个元素。容器内部可以包含相同的元素。 -
<interface>java.util.Set:
Set集合容器内部包含了可重复相同的元素。
至于更详细的两者差别和适用放到下一节做总结。
java_map.png
B. java集合的KEY-VALUE键值对模式的Map集合类图如上图。可以看到Map<K,V>类中的类泛型K,V，就是分别代表Map集合中每个Entry中的key和value对应的类型。Map<K,V>是所有键值对集合的根类，可以从该接口的方法中看看，该类型的集合对内部的键值对有什么通用的操作，与Collection集合接口一样，抽象的AbstractMap类则提供了KEY-VALUE键值对集合基本功能方法。
int size();
boolean isEmpty();
boolean containsKey(Object obj); /*元素中是否包含某个key*/
boolean containsValue(Object obj);/*元素中是否包含某个value值*/
V get(Object key); /*根据键值取到对应的值*/
V put(K key, V value);/*放置新的键值对到集合中*/
void putAll(Map<? extends K, ? extends V> m);
Set<K> keySet(); /*拿到map集合元素所有的key值-不可重复*/
Collection<V> values();/*拿到集合中所有的value值集合*/
Set<Map.Entry<K, V>> entrySet(); /*拿到集合中所有的键值对（key-value）集合*/
//还有一个内部接口Entry<K,V>代表容器中一个键值对对象
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
键值对类型的集合与线性单个元素集合就有很大不同了，就是属于两种不同的结构。Map顾名思义就是根据某个KEY，去拿到对应的VALUE,键值对集合其实在开发中也是非常常用的。其中，Map<K,V>中的Entry<K,V>也是非常有用，也是map中不同分支区分的重要依据，因为可以从上图看到，其实每个map子类中都会有自己自定义的Entry类，比如HashMap.Entry,TreeMap.Entry。根据自定义的map元素key-value实体，就能根据该类的职责对内部的节点元素进行操作。就拿LinkedHashMap来说，它内部的Entry类是继承HashMap的，自身Entry类中定义了before,after属性，就可以用来维持内部键值对的位置关系，就能达到LinkedHashMap实现的:出去元素顺序与放置键值对顺序是相同的。
Map集合的分类，也就是根据内部Entry子元素是否需要排序分成HashMap和SortedMap两大分支。至于更细的部分放到后面再说。
[2]容器集合其他相关类:
下面罗列的几个类，都是与集合容器密切相关的接口或者类。代表着不同的功能或者特性。
- 集合迭代：
<Interface>java.lang.Iterable<T>: 实现该接口的对象，可以使用foreach增强循环迭代获取对象内部元素。由上面Collection类图可知，Collection继承了该接口，所以，所有Collection下子类都能使用增强for循环遍历集合元素。该类中包含一个返回java.util.Iterator<E>对象的方法:
Iterator<T> iterator();
<Interface>java.util.Iterator<E>: 该接口用于替代之前集合框架中使用枚举Enumeration来遍历容器元素。该接口与枚举类不同的地方包括两点:
1.跟原先Enumeration接口的方法名比起来，Iterator接口的方法名语义更规范和明确。
2.Iterators对象允许集合容器在遍历元素过程中，将某个元素从元素移除。
@Test
public void tt(){
List<String> tt = new ArrayList<String>(Arrays.asList("aa","bb"));
System.out.println(tt.size());
Iterator<String> iterator = tt.iterator();
while(iterator.hasNext()){
String next = iterator.next();
if("aa".equals(next)){
iterator.remove();
}
}
System.out.println(tt.size());
}
//output 2 1
迭代器对象中方法包括以下方法:
boolean hasNext(); /*判断容器中是否还有元素*/
E next(); /*在循环中用于获取当次的元素*/
void remove(); /*用于移除当次循环中的元素*/
- 对象克隆:
<Interface>java.lang.Cloneable: 该接口内部没有定义方法，只是用来标识：所有实现该接口的类实例化的对象都可以被克隆。若是调用Object中的clone()方法的对象类没有实现该接口，则会抛出CloneNotSupportedException异常。当然了，对象克隆包括了浅克隆和深度克隆。 - 对象序列化:
<Interface>java.io.Serializable: 该接口没有属性和方法。该接口用于标识：实现该接口的类对象可以被序列化和反序列化。 - 集合随机访问:
<Interface>java.util.RandomAccess: 通常是用于标记List接口子类的接口，实现该接口表明了该集合在获取元素时候，可以随机访问容器中任一个位置元素。与顺序访问概念相对。 - 线性队列:
<Interface>java.util.Deque<E>: 该接口是代表一种获取线性集合元素方式的功能集合。该接口继承了Queue队列集合接口。可以在线性集合的两端获取和添加元素，同时具备了队列先进先出和栈后进先出的数据结构模式。
泛型相关内容
因为在集合中元素的多种多样，不可能每种数据类型都定义一种专门盛放该类型元素的集合，所以，就可以使用泛型这个类参数概念来解决，通过泛型类参数来标识，那么容器内的类型就会推迟到运行期间去进行类型判断。泛型的本质就是参数化类型，就是将容器内的元素对应的java.lang.Class也可以在运行期间作为一个变量传递到容器中，这个Class可以是java的所有类型。
泛型的使用，在java中，可以声明在类或者接口，还有方法上。如下:
public class MathOp<E,K>{
public static <E extends Number,K extends Comparable<? super K >> E find(E[] src,E obj){
E target = null;
K ret = null;
for(int i=0;i<src.length;i++){
if(src[i] == obj || src[i].equals(obj)){
target = src[i];
break;
}
}
return target;
}
}
//interface eg: public interface tt<K,V>{}
在简单说说通常会遇见的泛型范围界定和泛型通配符?
结合上面代码可以看到有使用<E extends Number> 和<? super K>。<E extends Number>: 这意味着当在实际编码过程中，传入容器的类型E必须是Number的子类，这里实际上就是规定了类型参数E的上界。即编译器会根据你传入的参数类型判断该类型是不是Number的子类，包括byte, double, float, int, long, and short等类型都行。另一方面，当定义了参数类型上界为Number,那么方法里的对象就可以调用Number类的方法。
<? super K >: 对extends相对，这里使用通配符，可以动态代表类型参数，这里使用了super来定义参数类型的下界：在实际调用传入类型参数时候，类型参数必须是类型K，或者K类型的父类。
在使用泛型界定的时候，extends和super会对容器取出或者放置元素有影响。
想看更多关于java泛型例子，可以看这篇文章: <u>Java 泛型 <? super T> 中 super 怎么 理解</u>
Collection系列
在了解了Collection集合的结构和主要分类后，那么就可以根据这些分类来进行延伸，看看这些重要的经常使用的子类如何创建，使用？在什么需求下应该选择哪一种集合容器。集合与集合之间，还能进行并集，交集等操作处理元素。下面就通过List和Set分支分别进行了解。
List
java.util.List系列的集合容器，意味着容器内部能存放相同的元素（eg:List内部两个元素e1,e2。e1.equals(e2)）。List接口中除了继承自Collection接口的方法外，还为了自身结构而设计的几种方法:
/*List位置操作方法*/
E get(int index); /*根据索引位置返回位置内保存的元素*/
E set(int index, E element);/*将指定位置的元素替换成指定的元素*/
void add(int index, E element);/*在指定位置内添加新的元素，后面的元素要向后移动*/
E remove(int index);/*将指定位置元素移除，并返回移除的元素*/
/*List查找元素方法*/
int indexOf(Object o);/*返回集合内部第一次出现指定元素索引位置*/
int lastIndexOf(Object o);/*返回集合内部最后一次出现指定元素索引位置*/
/*集合子集集合*/
List<E> subList(int fromIndex, int toIndex);
可以看到List接口根据自身特定，对自己集合容器的元素的获取和设置动作进行定义。包括根据集合元素的位置索引，可以快速定义元素，对元素进行增删改查操作。至于为什么可以通过位置索引快速定位元素这样随机访问集合容器，那它内部的如何实现的？后面通过具体的ArrayList实现来说明。
List还有一个特别的迭代器，是List类自定义的一个迭代器ListIterator<E>。这个迭代器是专门用于List服务的，有什么特点呢？可以在遍历迭代List集合过程中，可以双向移动光标位置，或向前调用previous(),或向后next()。根据光标向前或者向后移动来获取集合内元素并进行修改删除元素等操作，看看该接口内定义的方法:
boolean hasNext();/*根据光标向后移动,next()方法是否返回元素，就表面后面还有元素*/
E next();/*获取后一位元素，并且光标向后移动*/
boolean hasPrevious();/*反向移动光标获取元素，判断前一位是否还有元素*/
E previous();/*向前移动光标，返回前一位元素*/
int nextIndex();/*返回调用next方法后光标索引位置*/
int previousIndex();
void remove();/*移除在调用next,previous方法后返回的元素*/
void set(E e);/*替换在调用next,previous方法后返回的元素*/
void add(E e);/*添加新元素，注意调用时序*/
那么就用个例子来调用上面方法熟悉熟悉这个接口的使用过程：
@Test
public void ListIteratorTest(){
List<String> tt = new ArrayList<String>(Arrays.asList("one","two","three","four"));
ListIterator<String> listIterator = tt.listIterator();
System.out.println("原始集合元素:"+tt);
//向后遍历
while(listIterator.hasNext()){
String t = listIterator.next();
System.out.println("下一个元素："+t);
int index = listIterator.nextIndex();
if(index == 2 && listIterator.hasPrevious()){
System.out.println("index 为"+index+"的前一个元素:"+listIterator.previous());
System.out.println("修改index为"+index+"前一个元素为 update_two");
listIterator.set("update_two");
break;
}
}
System.out.println("修改后的集合元素:"+tt);
}
//输出
原始集合元素:[one, two, three, four]
下一个元素：one
下一个元素：two
index 为2的前一个元素:two
修改index为2前一个元素为 update_two
修改后的集合元素:[one, update_two, three, four]
每个List子类包括:AbstractList,ArrayList,LinkedList内部都有个私有类来实现ListIterator<E>这个接口，以满足不同集合特征的元素遍历方式。
其实从源代码部分List接口中声明的Iterator<E> iterator()方法在AbstractList和List多数子类中的实现，内部是通过私有类Itr来实现的。
List接口中声明的ListIterator<E> listIterator()方法则是
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {..}
##############
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
private class ListItr extends Itr implements ListIterator<E> {...}
所以，List子类中的迭代器都可以有两种方式来获取即:iterator()和listIterator()。两者大的区别也就是listIterator可以双向移动获取和操作元素了。
根据类图，可以看到List主要的三种实现：ArrayList,Vector,LinkedList。下面分别说说：
-
ArrayList
ArrayList是一个可动态调整大小的实现List的集合。该集合可以容纳任何类型的对象，包括null。ArrayList的方法根据时间复杂度的不同可以大致分为以下几种:
constant time：即不管你集合内部有多少数据量，调用这几个方法花费的时间都是基本相等的：size(),isEmpty(),get(),set(),iterator(),listIterator()。
amortized constant time: 就是add()方法，添加n个元素需要时间是O(n)。
linear time : 其他操作基本上算是线性时间阶。
ArrayList内部是由一个Object[]类型的elementData字段来存储数据。也就是说该集合底层的操作都是由数组维持的，无论是增删改都是与数组的结构特性相关，即可以随机存取，但是在n位置插入一个新元素，n+1后面的所有元素都要后移一位等。
elementData数组的长度默认是DEFAULT_CAPACITY = 10;。当我们在创建ArrayList，调用的无参构造函数，内部就是初始化elementData数组的长度为10。ArrayList的所有新增，删除，初始化等操作都是与elementData，size变量有关。而elementData数组中的capacity又是很重要的概念，表示数组最多能容纳的元素数量，size变量则是表示当前elementData数组中存放元素的个数。
通过下面的方法来看看内部的ArrayList操作:
//java.util.ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
...
}
//end ArrayList
//当我们创建一个ArrayList对象若是传入了初始化数组的个数的话，就直接this.elementData = new Object[initialCapacity];
//elementData数组就初始化完成。
//若是我们常用的调用无参数的构造器，那么内部数组是如何初始化的呢？
//List<String> tt = new ArrayList<String>();
//1. 首先将一个空的数组赋值给elementData
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
//2.当调用add("sptok")时候，add方法就会对elementData进行容量拓展
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//3. ensureCapacityInternal方法,从代码可以看到，根据上面1的无参构造的调用，
//第一个if判断为真，然后将默认的DEFAULT_CAPACITY=10容量值，与当前数组个数size
//进行比较，因为是第一次添加，size必定小于DEFAULT_CAPACITY,所以，
//传入ensureExplicitCapacity的参数就是10.
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//4. ensureExplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//5. grow(10) ，可以看到最后是调用Arrays的copyOf方法对elementData进行初始化
//Arrays.copyOf(elementData,10); 最后ArrayList的elementData数组容量大小就为10.
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);
}
特别的，在ArrayList中，elementData的capacity是一个特别重要的地方，因为ArrayList内部所有数据元素存储都是在elementData中，而elementData最多能存放多少元素个数就是与capacity有关，所以在每次使用add一次添加一个元素，或者addAll一次添加多个元素，这些对存储新元素有关的操作，该ArrayList内部都会使用ensureCapacity,ensureCapacityInternal,ensureExplicitCapacity,hugeCapacity等方法对capacity重新处理，若是数组容量不够大，就要扩容。
在elementData容量修改成功之后，所有元素的添加add,修改set,删除remove,查询get等方法都是与常规操作数组一样了。ArrayList是线程不安全的，意味着在处理容器元素时候，在多线程环境下是要进行人为同步的，无论是通过共享内存，添加synchronized关键字等。相对的，与ArrayList结构完全差不多的线程安全的集合就是Vector了。
-
B. LinkedList
与ArrayList内部是由数组存储元素，可随机读取元素不同，LinkedList是链式的数据结构即为链式存储，ArrayList则是顺序存储的线性表。所以存储结构不同，当然就会有不同的操作特性与具体实现。链式的LinkedList类中有first和last连个节点属性变量来维持链式存储信息和操作内部的链式存储元素。因为LinkedList也实现了Deque接口，那么这个链式集合的存取都可以从任意一段进行操作。
看看LinkedList内部用于维护链式存储信息的结构:内部有个节点Node私有类。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
....
//元素节点，分别存储当前节点前面和后面的节点信息。因为是双向的。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
...
}
因为LinkedList是链式存储，那么对内部元素的操作都是使用Node来操作，就那添加节点来举个例子:
// List<String> tt = new LinkedList<String>();
public boolean add(E e) {
linkLast(e); //调用链式方法，在链尾添加一个信息的Node.
return true;
}
//linkLast()
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
//参数表示前面节点，当前节点元素，后面节点
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode; //在链尾添加新节点
size++;
modCount++;
}
所以，LinkedList中继承自List中的公共方法底层实现，都是经过链式操作包装的。这样就能达到LinkedList类使用的目的，遍历读取集合内部元素的顺序与添加元素的顺序是相同的。这都是因为内部Node的next,prev保存者每个节点前后节点的信息来支持的。所以呢，对于线性链式存储的优势弊端同样也会在LinkedList中体现出来，那就是在相同的环境下，链式结构在指定位置添加新的元素速度会比顺序结构块（不是最后一个），因为没有顺序表要将插入点后的所有元素移位的花销，当然了，这也是通常的境况下。
-
C.Vector
与ArrayList差不多等价，只是Vector是线程同步的。内部的方法等都有synchronized修饰而已。
Set
Set是Collection集合的另一分支，与List相对，Set内部不能存放相同的元素。其他的功能方法与AbstractCollection中相差不大，主要就看看如何处理这个"相同元素"的问题以及元素排序TreeSet的内容。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
...
}
HashSet集合内部实际上是HashMap来实现的，这个KEY-VALUE的map所有value值都是同一个PRESENT对象。所以，HashSet实际上也就是一个key值不同，value值全部都是一个相同Object的Map集合，HashSet仅仅是关注不可重复的key值集合而已。
那重点当然看看这个不可添加重复的远的的Set内部的add方法是如何实现的?
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
map的put方法就是根据key的hash值进行比较，发现若是有相同的key的话，就替换对应的value值，返回被替换的value值。返回时候，不为null,所以返回false。也就是说明HashSet没有添加成功，有相同的元素。若是没有相同的元素，map的put方法会返回null,则HashSet的add方法返回true，表示添加新元素成功。
再来看看需要将元素排序的TreeSet的一些实现和用法。从源代码可以看到，与HashSet内部由HashMap实现相似，TreeSet内部底层也由Map系列的具有排序功能的NavigableMap接口的实现类实现。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
//通常我们使用的无参数构造器内部其实传递了一个TreeMap实现。
public TreeSet() {
this(new TreeMap<E,Object>());
}
//若是要自定义排序规则
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
...
}
看看如何使用TreeSet,定义一个实现Comparator接口的类，用于定义在集合容器中排序规则，这个是最主要的:
//Bottle pojo
public class Bottle {
private int height = 0;
public Bottle(){}
public Bottle(int height){
this.height = height;
}
@Override
public String toString() {
return "Bottle [height=" + height + "]";
}
//getter setter
}
//排序规则
public class BottleComparator implements Comparator<Bottle>{
//定义排序规则，按照瓶子高度升序
@Override
public int compare(Bottle o1, Bottle o2) {
return o1.getHeight() - o2.getHeight();
}
}
//treeSet使用
@Test
public void CompaTest(){
//根据Bottle瓶子的高度排序
TreeSet<Bottle> tr = new TreeSet<Bottle>(new BottleComparator());
Bottle b1 = new Bottle(15);
Bottle b2 = new Bottle(20);
Bottle b3 = new Bottle(10);
tr.add(b1);
tr.add(b2);
tr.add(b3);
System.out.println(tr);
}
//输出,可以看到已经按照瓶子高度从低到高排序
[Bottle [height=10], Bottle [height=15], Bottle [height=20]]
Set的底层实现大多都是依赖Map实现的，具体的细节还是要到Map中的查看。
Map系列
Map<K,V>是键值对的集合抽象，内部接口定义的方法都是围绕KEY-VALUE来进行操作的。如何获取和设置KEY，VALUE,若是KEY值重复如何处理？如何判断KEY的重复，在内部Map是如何实现每个KEY-VALUE存储的？每个KEY-VALUE是如何具体表示的？等等都可以进行思考与实践。下面就按照HashMap和TreeMap两大分支分别细说。
HashMap
因为HashMap的存储等核心都会与Hash有关，那先看看hash是什么，有什么作用，与java有什么关系？
Hash定义：就是把任意长度的输入(预映射)，通过散列算法（eg:md5,sha1..），变换成固定的长度的输出。更多请看百度-hash
在java中呢，所有的对象的顶层对象Object有一个hashCode()方法，就是根据一定的自定义规则，将与对象相关的信息(比如对象的内存地址，对象字段，属性等)映射成一个固定长度的数值，这个数值称为散列值。这样我们就可以根据自己定义的散列算法规则，得到想要的散列值，得到这个散列值，可以用来标识对象唯一性，或者对比两个对象是否相等。在java中对比两个对象是否相等，通常不都是重写hashCode和equals两个方法么。
关于java中hashCode更多内容，可以看看这篇文章，说得很好:浅谈Java中的hashcode方法
//Object,注释上说这个方法主要是可以用来标识对象唯一性且可以为Hash Table提供支持。
//两个对象通过e1.equals(e2)==true后，还不能判定两个对象相等，还要分别调用
//hashCode方法进行对比，若是两个对象的hashCode值相等，则两个对象相等。
* <li>If two objects are equal according to the {@code equals(Object)}
* method, then calling the {@code hashCode} method on each of
* the two objects must produce the same integer result.
public native int hashCode();
特别的，在HashMap底层的hash表更是hash散列函数的主要应用,Hash Table的操作都是需要依赖散列函数来操作的,HashMap自定义hash映射规则，然后根据规则添加节点元素。HashMap和HashTable大体上是相同的，不同点在于：HashMap是线程不安全的，并且可以放置的KEY-VALUE值分别均可为null;HashTable反之。好了，下面具体看看HashMap的内容。
从java.util.HashMap的注释中可以知道：影响HashMap性能的两大参数是capacity和load factor：
capacity:表示hash表内部的buckets（桶）的数量。也就是hash表的数组容量长度。
initial capacity： 表示hash表在创建的时候表中的capacity的初始值大小。
load factor:加载因子，就是用来检测当hash表中存放buckets占总的capacity的比例，达到某个指定的阈值，就将hash表的capacity扩容。
HashMap内部底层是由Entry<K,V>数组table这个hash表来实现对元素的添加，修改，删除，查询操作的。下面就根据自己对HashMap的理解，将内部的hash表在put操作的过程画出来，并对这个put过程进行简单说明:
//HashMap.java
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
...
public V put(K key, V value) {
//1.如果key为null，那么将此value放置到table[0],即第一个桶中
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//2.根据key值得到hash值
int hash = hash(key);
//3. 根据hash值得到对象所要被放置的table表索引槽
int i = indexFor(hash, table.length);
//4. 遍历索引槽上的链式节点
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//4-1. 查看是否有相同的key对象，注意这里对比相等的条件
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//5. 不存在，则根据键值对<Key,Value> 创建一个新的Entry<Key,Value>对象，
//然后添加到这个桶的Entry<Key,Value>链表的头部。
addEntry(hash, key, value, i);
return null;
}
...}
hashmap.png
就拿上述代码中的put方法进行解说，这个放置新的对象到hashmap对象中的大致过程也就像下图所示:（最左边的Object对象即为要放进hashMap对象元素，每个对象对应的key-value值都有在图中描述出来了）
1.先根据对象的key值，调用hash函数hash(key)得到hash值。
2.在根据这个hash值调用indexFor方法得到table数组的索引值，就决定将元素放在那个槽。
3.然后遍历索引所在槽对应的链表，看看是否有相同的key值对象，若是存在相同key值，则替换原来key值对应value值，返回被替换的value值。
4.若是没有相同的key值，则调用addEntry方法添加新的节点。具体如何添加的，在后面再细说。
从图看出，java对hashMap的hash映射规则有两步：第一步通过hash方法得到一个根据key值拿到的hash值；第二步再根据第一步得到的hash值映射到内部hash表table中具体的数组索引槽。这样就能大致定位元素所要存放的位置。之后，在槽的内部在进行链式结构的节点存储和对比查询。
这里的节点Entry<K,V>节点概念也是非常重要的，它是每个hash表table字段指定索引对应的槽中链式节点的基础。只有通过这个节点结构，才能形成链式节点元素的存储，看看该节点类是如何存储的:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next; //指向下一个节点指针
int hash; //hash值 : hash(key)
...
}
结合上图中，Object1,Object2,Object3分别对应的e1,e2,e3节点对象。每个节点中都保存着节点的key值，value值，和hash值，还有指向下一个节点的节点指针。这样其实就能形成链式节点了。再来看看每个存入对象Entry节点的hash值是如何计算的:
/*
* 这个hash函数就是自定义的hash映射函数，将对象根据自定义规则得到定长一个hash值返回。
* A. 如果输入是String类型，那么可以直接使用sun公司提供的stringHash32函数，得到32位的hash值。
* B. 如果不是String类型，会首先调用输入对象的hashCode方法得到一个hash值，但是为了避免hash值冲突，
* 为什么要避免hash值冲突，就是应为，若是假设冲突概率大，10000个元素有9999个元素都在一个table
* 索引槽中(最坏打算),那么当通过get(key)查找元素时候，就会遍历索引槽的链式节点，顺序查询，
* 非常影响性能。
* 所以，javase设计人员通过设计的一系列位运算，就是为了平衡hash值冲突情况，旨在尽量不影响hash表的性能。
*/
final int hash(Object k) {
//随机的hashSeed，来降低冲突发生的几率
int h = hashSeed;
//如果是字符串，用了sun.misc.Hashing.stringHash32((String) k);来获取hash值。
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
* 该函数是用来根据对象的hash值定位到hash表的索引槽位置
* 这里刚开始默认的capacity=16,即length=16
* 这里无论h为多少, h & (16 -1) = h & 0xffff < 16
* 得到的都是后四位二进制，最大值也就是15，就对应table的索引值0~15.
* 这样就能找到索引槽。
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
上面重要的hash函数说明也解释了，然后再来看看当调用indexFor找到索引槽后，是如何比较两个元素相等的:
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){}
可以看到，因为每个元素节点都有hash值属性，这个hash值都是根据HashMap.hash(key)方法算出来。首先比较两个Entry对象的hash值是否相等，相等的条件是两个对象的hash值相等，并且在未进行hash计算的两个对象的key值也相等（==相等或者equals相等）。若是相等的话，就直接将旧的value值替换成新的value值，并返回被替换的value值。若是不相同，则创建新的节点，链接到索引槽的链表上。
再看看hash表是如何添加新的节点Entry的：
从put方法中可以看到，若是在循环Entry链表中，找不到相同的key值，那么就调用addEntry方法，将hash值，key,value,index值都传递下去，从源代码看看，是如何创建新的节点的:
/*
* 先判断table这个hash表中元素(buckets)数量是否大于等于阈值（阈值=capacity * (load factor)）,并且
* bucketIndex的索引值出的元素不为null，就调用resize方法进行2倍扩容，这时候的table.length是原来的两倍。
*
* 然后在根据hash(key)得到的值和新的table.length得到新节点所在的索引槽，定位到索引槽之后，就可以添加新的Entry节点了。
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //扩容2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length); //定位扩容后的元素所在索引槽
}
//定位到新元素所在的索引槽，后添加节点
createEntry(hash, key, value, bucketIndex);
}
/*
* 可以看到，首先将索引槽处的节点赋值给e,然后再将新的节点放置在索引槽table[index]处，
* 最后将索引槽处节点指向e: 达到的效果就是，每次添加新的Entry节点都是放在链表的头部
* 也就是索引槽的位置。
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
其实，在了解了hashMap内部的hash表结构和hash()，indexFor()两个函数，就大概知道内部是如何操作节点的了。hash表内部就是数组和链表的组合操作。至于每个数组索引槽的链表节点数量的控制，就是hash()函数来直接影响的。最大差异化hash值，尽量少碰到hash碰撞的节点情况，这样链表的索引的数量就会少。其实，table数组的长度和每个索引槽的链表的长度两者的关系直接影响到HashMap的性能了，至于如何协调，还要多看看了。
TreeMap
TreeMap内部主要的难点就是底层红黑二叉树的理解和实现。其实自己对这个算法也不是太了解，再次就不对这个进行过多的描述了。就简单看看treeMap对象的put方法，大致是如何放置元素的，以及内部的二叉树结构是如何形成的。
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;
/**
* The number of entries in the tree
*/
private transient int size = 0;
...
}
可以看到，内部有两个个重要的属性就是comparator比较器和root根节点元素。从注释也可以看到，若是在构造器中传入比较器实例，那么就会按照每个对象的key值进行自然排序。也就是使用java自己实现的每个对象的比较规则对treeMap内的元素进行排序。那么TreeMap这个树形结构是如何形成的呢？主要还是因为TreeMap中每个节点Entry的定义:
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
}
这样每个节点有左右子节点，还有父节点，这样一个树形层级的二叉树就出来了。然后再来看看当将一个元素放置入map中，内部的树是如何进行处理的?
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
/*若是第一次添加元素，root根节点为null
* 然后在判断是否传入自定义的比较器comparator.若是没有传入
* 则调用java内构的数据类型的比较器，然后创建根节点
*/
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp; //用于判断最后是添加左叶子还是右叶子节点
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//若是传入了自定义元素比较器，则内部二叉树节点添加将会根据这个比较器进行
if (cpr != null) {
/*
* 不断的从根节点到左右子节点进行递归比较每个节点的key值。
* 若是当前树节点的key值小于新节点key值，那么就往右字数迭代，
* 反之，则往左字数迭代比较，直到遍历到叶子节点后 t= null,
* 跳出递归循环，添加新的叶子节点。
*/
do {
parent = t;//保存父节点信息
//根据自定义比较器，判断parent节点的key值与添加的Entry节点key值。
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//若是找到相同的key，则拿新值，替换旧的值，并返回旧值。
return t.setValue(value);
} while (t != null);
}
else { //自然排序，过程与上面的流程一样
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//遍历二叉树后，找到合适位置，添加新的树节点
Entry<K,V> e = new Entry<>(key, value, parent);
//根据cmp变量保存的最后key比较信息，来决定是添加右叶子节点还是左叶子节点。
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
从上面代码的注解中我们就可以直到TreeMap内部二叉树是如何添加新节点的了，都是根据comparator比较器来迭代循环二叉树节点，将每个树节点的key值与新添加的节点的key值进行比较，最后决定是在右叶添加还是左叶添加新节点而已。主要决定节点是左还是右边就是依赖comparator比较器。
集合容器工具类
在将JAVA SE中大多数经常使用的集合框架说明完后，最后，再看看集合容器的工具类，还有数组工具类。因为集合和数组都是形影不离的，两种类型的容器密不可分。就从上面的集合源代码也可以直到，某些内部集合存储元素都是使用数组来实现的。两者还能相互转换。
Collections:
所有集合框架的工具类，内部集成了为集合框架服务的工具类：包括集合内部元素排序，查找，拷贝，最大值，最小值，随机乱序，替换，同步等等方法。
-
Arrays:
数组工具方法，集成了为数组服务的工具类:包括数组排序，查找，hash值，拷贝等等方法。
在这里就重点看看两类容器的拷贝方法和相互转换：
集合拷贝，Collections集合工具类定义的方法：
其实内部就是通过遍历src集合，然后将每个元素设置到dest之中，也没什么技术含量。若是想实现自己的集合拷贝方法，也是非常不错的。
public static <T> void copy(List<? super T> dest, List<? extends T> src){..}
数组拷贝，可以通过Arrays工具类的copyOf方法，也可以通过System.arraycopy方法：
//Arrays.copyOf
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
//System.arraycopy
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
其实从实现可以看到，实质上Arrays.copyOf底层还是通过反射和system.arraycopy实现的。因为arraycopy方法是native的，本地代码库，更贴近机器底层，所以效率那肯定比copyOf方法高了。在数组拷贝需求中，优先考虑arraycopy方法了。
两者的相互转换：
集合转换数组:
toArray() 或者 toArray(T[] a)(优先)
数组转换成集合:
Arrays.asList(..)
参考:
Java HashMap 源码解析
Java集合框架源码剖析：HashSet 和 HashMap
HashMap的设计原理和实现分析
网友评论