Java容器（含示例代码）

Java容器是整个java体系中非常重要的一部分，可以说所有的java项目都离不开java容器，本思维导图详细总结了java包含的所有容器知识，包括实现原理，以及相关的使用代码示例。

Java集合

J ava常见集合的默认大小及扩容机制 在面试后台开发的过程中，集合是面试的热话题，不仅要知道各集合的区别用法，还要知道集合的扩容机制，今天我们就来谈下ArrayList 和 HashMap的默认大小以及扩容机制。 在 Java 7 中，查看源码可以知道：ArrayList 的默认大小是 10 个元素，HashMap 的默认大小是16个元素（必须是2的幂，为什么呢？？？下文有解释）。这就是 Java 7 中 ArrayList 和 HashMap 类 的代码片段： // from ArrayList.java JDK 1.7 private static final int DEFAULT_CAPACITY = 10; //from HashMap.java JDK 7 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 这里要讨论这些常用的默认初始容量和扩容的原因是： 当底层实现涉及到扩容时，容器或重新分配一段更大的连续内存（如果是离散分配则不需要重新分配，离散分配都是插入新元素时动态分配内存），要将容器原来的数据全部复制到新的内存上， 这无疑使效率大大降低。加载因子的系数小于等于1，意指即当元素个数超过容量长度*加载因子的系数时，进行扩容。另外，扩容也是有默认的倍数的，不同的容器扩容情况不同。 List 元素是有序的、可重复 ArrayList、Vector默认初始容量为10 Vector：线程安全，但速度慢 底层数据结构是数组结构 加载因子为1：即当 元素个数 超过 容量长度 时，进行扩容 扩容增量：原容量的 1倍 如 Vector的容量为10，一次扩容后是容量为20 ArrayList：线程不安全，查询速度快 底层数据结构是数组结构 扩容增量：原容量的 0.5倍+1 如 ArrayList的容量为10，一次扩容后是容量为16 Set(集) 元素无序的、不可重复。 HashSet：线程不安全，存取速度快 底层实现是一个HashMap（保存数据），实现Set接口 默认初始容量为16（为何是16，见下方对HashMap的描述） 加载因子为0.75：即当 元素个数 超过 容量长度的0.75倍 时，进行扩容 扩容增量：原容量的 1 倍 如 HashSet的容量为16，一次扩容后是容量为32 Map是一个双列集合 HashMap：默认初始容量为16 （为何是16：16是2^4，可以提高查询效率，另外，32=16<<1） 加载因子为0.75：即当 元素个数 超过 容量长度的0.75倍 时，进行扩容 扩容增量：原容量的 1 倍 如 HashSet的容量为16，一次扩容后是容量为32 接下来我们来谈谈hashMap的数组长度为什么保持2的次幂？ hashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。 这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了 之前已经散列良好的老数组的数据位置重新调换)，还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀。 1. static int indexFor( int h, int length) { 2. return h & (length-1); 3. } 首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。看上去很简单，其实比较有玄机。比如数组的长度是2的4次方，那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问， 为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高，我以2的4次方举例，来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。 看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同 一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的 值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组 长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！  所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。 说到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因， 在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。

Map

HashMap

HashMap的数据结构：  java8优化后的数据结构： 为了减少链表遍历的开销，Java 8对HashMap进行了优化，将数据结构修改为数组+链表或红黑树。 在链表中的元素超过8个以后，HashMap会将链表结构转换为红黑树结构以提高查询效率，因此其时间复杂度为O(log N)。 

LinkedHashMap

LinkedHashMap为HashMap的子类，其内部使用链表保存元素的插入顺序，在通过Iterator遍历LinkedHashMap时，会按照元素的插入顺序访问元素。

数组+链表存储数据，线程不安全

判断两个元素相等：hashcode相等且（引用相同或者调用equals方法返回true）

HashMap的key和value允许为null。

如果需要满足线程安全的条件，则可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

HashMap在查找数据时，根据HashMap的Hash值可以快速定位到数组的具体下标，但是在找到数组下标后需要对链表进行顺序遍历直到找到需要的数据，时间复杂度为O(n)。

为了减少链表遍历的开销，Java 8对HashMap进行了优化，将数据结构修改为数组+链表或红黑树。在链表中的元素超过8个以后，HashMap会将链表结构转换为红黑树结构以提高查询效率，因此其时间复杂度为O(log N)。

常用参数

capacity：当前数组的容量，默认为16，可以扩容，扩容后数组的大小为当前的两倍，因此该值始终为2^n。

loadFactor：负载因子，默认为0.75。

threshold：扩容的阈值，其值等于capacity×loadFactor。Map中存储的数据量超过这个阈值后，会触发扩容

容量：默认为16，每次增长原来的一倍

ConcurrentHashMap

数据结构：  java8引入红黑树： 

分段锁实现，线程安全

ConcurrentHashMap由多个Segment组成（Segment的数量也是锁的并发度），每个Segment均继承自ReentrantLock并单独加锁，所以每次进行加锁操作时锁住的都是一个Segment，这样只要保证每个Segment都是线程安全的，也就实现了全局的线程安全。

在ConcurrentHashMap中有个concurrencyLevel参数表示并行级别，默认是16，也就是说ConcurrentHashMap默认由16个Segments组成，在这种情况下最多同时支持16个线程并发执行写操作，只要它们的操作分布在不同的Segment上即可。并行级别concurrencyLevel可以在初始化时设置，一旦初始化就不可更改。ConcurrentHashMap的每个Segment内部的数据结构都和HashMap相同。

TreeMap

基于二叉树数据结构

默认按键值的升序排序，也可以自定义排序比较器。

在使用TreeMap时其key必须实现Comparable接口或采用自定义的比较器，否则会抛出java.lang.ClassCastException异常。

HashTable

线程安全

已废弃，并发性不如ConcurrentHashMap

继承自Dictionary类

WeakHashMap

其键是弱键WeakReference，弱键引用不会阻止垃圾收集器进行垃圾回收

当某弱键不再被其它对象引用，并被GC回收时。在GC回收该弱键时，这个弱键也同时会被添加到ReferenceQueue(queue)

当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们，就是删除table中被GC回收的键值对

IdentityHashMap

解决hashcode和equals方法不能确定键的唯一性的情况

Collection

List

ArrayList

基于数组实现，增删慢，查询快，线程不安全

默认容量是10，ArrayList中每次增长的长度为之前的(1/2)+1

LinkedList

基于双向链表实现，增删快，查询慢，线程不安全

Vector

Stack

基于数组实现，增删慢，查询快，线程安全

默认容量是10，每次增长原来的1倍

Set

HashSet

判断两个元素相等：hashcode相等且（引用相同或者调用equals方法返回true）

底层是hashmap

扩容与HashMap一致

LinkedHashSet

底层是LinkedHashMap

TreeSet

基础类型如String，Integer按照默认排序即可

自定义类型需要实现Comparable接口并实现CompareTo方法

Queue

ArrayBlockingQueue

基于数组数据结构实现的有界阻塞队列

LinkedBlockingQueue

基于链表数据结构实现的有界阻塞队列

PriorityBlockingQueue

支持优先级排序的无界阻塞队列。

DelayQueue

支持延迟操作的无界阻塞队列。

SynchronousQueue

用于线程同步的阻塞队列。

LinkedTransferQueue

基于链表数据结构实现的无界阻塞队列。

LinkedBlockingDeque

基于链表数据结构实现的双向阻塞队列。

Collections

java.utils.Collections是集合工具类, 用来对集合进行操作.

sort(List)

对list进行排序

binarySearch(List)

在List中进行查找，二分查找

reverse(List)

反转

shuffle(List)

打乱顺序

swap()

交换两个元素的位置，可用于List或者对象数组

fill(List)

用指定的元素替换List中的所有元素

copy

List复制

min

取最小元素，该元素的类需要实现Comparable接口

max

取最大元素

rotate

指定长度反转，可向前(参数为正)可向后(参数为负)

replaceAll(List)

替换所有指定的元素

indexOfSubList

lastIndexOfSubList

创建不可变集合对象

unmodifiableCollection

返回不可更改的集合对象

unmodifiableSet

返回不可更改的集合

unmodifiableSortedSet

返回不可更改的排序集合

unmodifiableList

unmodifiableNavigableSet

unmodifiableMap

unmodifiableSortedMap

unmodifiableNavigableMap

创建线程安全的集合对象

synchronizedCollection

synchronizedSet

synchronizedSortedSet

synchronizedNavigableSet

synchronizedList

synchronizedMap

synchronizedSortedMap

synchronizedNavigableMap

。。。

Arrays

package com.dreamriver.collection; import java.util.Arrays; import com.dreamriver.utils.ArrayUtil; public class ArraysTest { public static void main(String[] args) { int[]data = ArrayUtil.intArray(100, 0, 100); System.out.println(Arrays.toString(data)); Arrays.sort(data); System.out.println(Arrays.toString(data)); int[]data1 = Arrays.copyOf(data, data.length); System.out.println(Arrays.toString(data1)); System.out.println(Arrays.equals(data, data1)); System.out.println(Arrays.binarySearch(data, 50)); Arrays.stream(data).forEach(a->System.out.print(a)); Arrays.fill(data, 55); System.out.println(Arrays.toString(data)); } }

排序

二分查找

判断数组相等

数组填充

数组复制

数组转字符串

Stream操作

Comparable

Comparator

示例代码

package com.dreamriver.collection; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.TreeMap; public class MapTest { public static void main(String[] args) { Map<MyObject, String>map = new TreeMap<MyObject, String>(); map = Collections.synchronizedMap(map); map.put(new MyObject(7), "1"); map.put(new MyObject(1), "1"); map.put(new MyObject(2), "1"); map.put(new MyObject(3), "1"); map.put(new MyObject(4), "1"); map.put(new MyObject(5), "1"); System.out.println(map); List<MyObject1>list = new ArrayList<MyObject1>(); list.add(new MyObject1(7)); list.add(new MyObject1(1)); list.add(new MyObject1(2)); list.add(new MyObject1(3)); list.add(new MyObject1(4)); list.add(new MyObject1(5)); System.out.println(list); Collections.sort(list, new Comparator<MyObject1>() { @Override public int compare(MyObject1 var1, MyObject1 var2) { return var1.data>var2.data?1:(var1.data==var2.data?0:-1); } }); System.out.println(list); } public static class MyObject implements Comparable<MyObject>{ int data; public MyObject(int data) { this.data = data; } @Override public boolean equals(Object paramObject) { if (paramObject==null) { return false; } if (paramObject instanceof MyObject) { return ((MyObject)paramObject).data==data; }else { return false; } } @Override public int hashCode() { return 32; } @Override public String toString() { return "MyObject [data=" + data + "]"; } @Override public int compareTo(MyObject paramT) { if (paramT==null) { return 1; } if (data>paramT.data) { return 1; } if (data<paramT.data) { return -1; } return 0; } } public static class MyObject1 { int data; public MyObject1(int data) { this.data = data; } @Override public boolean equals(Object paramObject) { if (paramObject==null) { return false; } if (paramObject instanceof MyObject) { return ((MyObject)paramObject).data==data; }else { return false; } } @Override public int hashCode() { return 32; } @Override public String toString() { return "MyObject1 [data=" + data + "]"; } } }

红黑树

红黑树是一种自平衡的二叉查找树

黑色完美平衡

规则

1.节点分红色和黑色

2.根节点是黑色

3.每个叶子节点都是黑色的空节点（null）

4.每个红色节点的两个子节点都是黑色（从叶子节点到根节点的路径上不能有两个连续的红色节点）

5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

变换

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。



右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。



变色：结点的颜色由红变黑或由黑变红。

插入

1.红黑树为空，直接插入到根节点，黑色

2.插入的节点key已经存在，直接更新值

3.插入节点的父节点为黑色节点，直接插入节点，设置为红色

4.插入节点的父节点为红色节点

4.1叔叔节点为红色

处理： 将叔叔节点和父节点设置为黑色 将祖父节点设置为红色 将祖父节点设置为当前插入节点，继续处理

4.2叔叔节点不存在或者为黑色， 且父节点是祖父节点的左子节点

4.2.1插入节点是左子节点

处理： 将父节点设置为黑色 将祖父节点设置为红色 对祖父节点进行右旋

4.2.2插入节点是右子节点

处理： 对父节点进行左旋 将父节点设置为当前插入节点，得到4.2.1 进行4.2.1的处理

4.3叔叔节点不存在或者为黑色， 且父节点是祖父节点的右子节点

4.3.1插入节点是右子节点

处理： 将父节点设置为黑色 将祖父节点设置为红色 对祖父节点进行左旋

4.3.1插入节点是左子节点

处理： 对父节点进行右旋 将父节点设置为当前插入节点，得到4.3.1 进行4.3.1的处理

删除

总体思路（二叉搜索树的删除）

1.如果删除的节点没有子节点，则直接删除

2.若删除的节点只有一个子节点，则用子节点代替

3.若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点，然后再删除替换节点

不断寻找替换节点，直到替换节点为叶子节点

具体操作

1.替换节点是红色节点，将替换节点的颜色变为被删除的节点的颜色，并删除替换节点

2.替换节点是黑节点

2.1替换节点是其父节点的左子节点

2.1.1替换节点的兄弟节点是红色

处理： 将兄弟节点设置为黑色 将父节点设置为红色 对父节点进行左旋，得到2.1.2.3 进行2.1.2.3的处理

2.1.2替换节点的兄弟节点是黑色

2.1.2.1替换节点的兄弟节点的右子节点是红色

处理： 将兄弟节点的颜色设置为父节点的颜色 将父节点设置为黑色 将兄弟节点的右子节点设置为黑色 对父节点进行左旋

2.1.2.2替换节点的兄弟节点的右子节点是黑色、 左子节点是红色

处理： 将兄弟节点的颜色设置为红色 将兄弟节点的左子节点设置为黑色 对兄弟节点进行右旋，得到2.1.2.1 进行2.1.2.1的处理

2.1.2.3替换节点的兄弟节点的左右子节点都是 黑色

处理： 将兄弟节点设置为红色 将父节点设置为新的替换节点 重新进行节点删除操作

2.2替换节点是其父节点的右子节点

2.2.1替换节点的兄弟节点是红色

处理： 将兄弟节点设置为黑色 将父节点设置为红色 对父节点进行右旋，得到2.2.2.3 进行2.2.2.3的处理

2.2.2替换节点的兄弟节点是黑色

2.2.2.1替换节点的兄弟节点的左子节点是红色

处理： 将兄弟节点的颜色设置为父节点的颜色 将父节点设置为黑色 将兄弟节点的左子节点设置为黑色 对父节点进行右旋

2.2.2.2替换节点的兄弟节点的左子节点是黑色、 右子节点是红色

处理： 将兄弟节点的颜色设置为红色 将兄弟节点的右子节点设置为黑色 对兄弟节点进行左旋，得到2.2.2.1 进行2.2.2.1的处理

2.2.2.3替换节点的兄弟节点的左右子节点都是 黑色

处理： 将兄弟节点设置为红色 将父节点设置为新的替换节点 重新进行节点删除操作

Stream