一、概述

1、为什么有集合

在java中有数组的概念，数组可以用来存放一组数据。但是，数组是固定长度的，这样在使用的时候就会有很多的不方便，比如说资源的浪费。这个时候，我们就希望有一种可以动态改变大小的数组，那就是集合的作用了。Java 所有的集合类都位于 java.util 包下，提供了一个表示和操作对象集合的统一构架，包含大量集合接口，以及这些接口的实现类和操作它们的算法。java中的集合主要分为Collection和Map两种

2、集合和数组区别

• 数组声明了它容纳的元素的类型，而集合不声明。
• 数组是静态的，一个数组实例具有固定的大小，一旦创建了就无法改变容量了。而集合是可以动态扩展容量，可以根据需要动态改变大小，集合提供更多的成员方法，能满足更多的需求。
• 数组的存放的类型只能是一种（基本类型/引用类型）,集合存放的类型可以不是一种(不加泛型时添加的类型是Object)。

二、Collection和Map体系集合

1、体系图

  

2、collection常见方法

3、list集合

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
和下面要提到的Set不同，List允许有相同的元素。
除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。
实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

LinkedList类
LinkedList实现了List接口，允许null元素。LinkenList底层采用了双向链表来存储数据，每个节点都存储着上一个节点和下一个节点的地址以及本节点的数据。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
注意：LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList底层采用动态数组的存储方式，便利效率非常高，ArrayList是线程不安全的。
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

ArrayList和LindedList的区别：
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
Vector类
Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。
Stack 类
Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

4、set集合

Set集合与Collection的方法相同，由于Set集合不允许存储相同的元素，所以如果把两个相同元素添加到同一个Set集合，则添加操作失败，新元素不会被加入，add()方法返回false

HashSet类

HashSet是Set集合最常用实现类，是其经典实现。HashSet是按照hash算法来存储元素的，因此具有很好的存取和查找性能。

HashSet具有如下特点：

♦ 不能保证元素的顺序。

♦ HashSet不是线程同步的，如果多线程操作HashSet集合，则应通过代码来保证其同步。

♦ 集合元素值可以是null。

HashSet存储原理如下：

当向HashSet集合存储一个元素时，HashSet会调用该对象的hashCode()方法得到其hashCode值，然后根据hashCode值决定该对象的存储位置。HashSet集合判断两个元素相等的标准是(1)两个对象通过equals()方法比较返回true；(2)两个对象的hashCode()方法返回值相等。因此，如果(1)和(2)有一个不满足条件，则认为这两个对象不相等，可以添加成功。如果两个对象的hashCode()方法返回值相等，但是两个对象通过equals()方法比较返回false，HashSet会以链式结构将两个对象保存在同一位置，这将导致性能下降，因此在编码时应避免出现这种情况。

HashSet查找原理如下：

基于HashSet以上的存储原理，在查找元素时，HashSet先计算元素的HashCode值（也就是调用对象的hashCode方法的返回值），然后直接到hashCode值对应的位置去取出元素即可，这就是HashSet速度很快的原因。

重写hashCode()方法的基本原则如下：

♦ 在程序运行过程中，同一个对象的hashCode()方法返回值应相同。

♦ 当两个对象通过equals()方法比较返回true时，这两个对象的hashCode()方法返回值应该相等。

♦ 对象中用作equals()方法比较标准的实例变量，都应该用于计算hashCode值。

LinkedHashSet类

LinkedHashSet是HashSet的一个子类，具有HashSet的特性，也是根据元素的hashCode值来决定元素的存储位置。但它使用链表维护元素的次序，元素的顺序与添加顺序一致。由于LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet，但在迭代访问Set里的全部元素时由很好的性能。

TreeSet类

TreeSet时SortedSet接口的实现类，TreeSet可以保证元素处于排序状态，它采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方法：自然排序和定制排序，默认采用自然排序。

• 自然排序

TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素的大小关系，然后将元素按照升序排列，这就是自然排序。如果试图将一个对象添加到TreeSet集合中，则该对象必须实现Comparable接口，否则会抛出异常。当一个对象调用方法与另一个对象比较时，例如obj1.compareTo(obj2)，如果该方法返回0，则两个对象相等；如果返回一个正数，则obj1大于obj2；如果返回一个负数，则obj1小于obj2。

Java常用类中已经实现了Comparable接口的类有以下几个：

♦ BigDecimal、BigDecimal以及所有数值型对应的包装类：按照它们对应的数值大小进行比较。

♦ Charchter：按照字符的unicode值进行比较。

♦ Boolean：true对应的包装类实例大于false对应的包装类实例。

♦ String：按照字符串中的字符的unicode值进行比较。

♦ Date、Time：后面的时间、日期比前面的时间、日期大。

对于TreeSet集合而言，它判断两个对象是否相等的标准是：两个对象通过compareTo(Object obj)方法比较是否返回0，如果返回0则相等。

• 定制排序

想要实现定制排序，需要在创建TreeSet集合对象时，提供一个Comparator对象与该TreeSet集合关联，由Comparator对象负责集合元素的排序逻辑。

综上：自然排序实现的是Comparable接口，定制排序实现的是Comparator接口。（具体代码实现会在后续章节中讲解）

EnumSet类

EnumSet是一个专为枚举类设计的集合类，不允许添加null值。EnumSet的集合元素也是有序的，它以枚举值在Enum类内的定义顺序来决定集合元素的顺序。

各Set实现类的性能分析

HashSet的性能比TreeSet的性能好（特别是添加，查询元素时），因为TreeSet需要额外的红黑树算法维护元素的次序，如果需要一个保持排序的Set时才用TreeSet，否则应该使用HashSet。

LinkedHashSet是HashSet的子类，由于需要链表维护元素的顺序，所以插入和删除操作比HashSet要慢，但遍历比HashSet快。

EnumSet是所有Set实现类中性能最好的，但它只能 保存同一个枚举类的枚举值作为集合元素。

5、map集合

Map接口采用键值对Map的存储方式，保存具有映射关系的数据，因此，Map集合里保存两组值，一组值用于保存Map里的key，另外一组值用于保存Map里的value，key和value可以是任意引用类型的数据。key值不允许重复，可以为null。如果添加key-value对时Map中已经有重复的key，则新添加的value会覆盖该key原来对应的value。常用实现类有HashMap、LinkedHashMap、TreeMap等。

Map常见方法（来源于API）如下：

1）HashMap与Hashtable

HashMap与Hashtable是Map接口的两个典型实现，它们之间的关系完全类似于ArrayList与Vertor。HashTable是一个古老的Map实现类，它提供的方法比较繁琐，目前基本不用了，HashMap与Hashtable主要存在以下两个典型区别：

♦ HashMap是线程不安全，HashTable是线程安全的。

♦ HashMap可以使用null值最为key或value；Hashtable不允许使用null值作为key和value，如果把null放进HashTable中，将会发生空指针异常。

为了成功的在HashMap和Hashtable中存储和获取对象，用作key的对象必须实现hashCode()方法和equals()方法。

HashMap工作原理如下：

HashMap基于hashing原理，通过put()和get()方法存储和获取对象。当我们将键值对传递给put()方法时，它调用建对象的hashCode()方法来计算hashCode值，然后找到bucket位置来储存值对象。当获取对象时，通过建对象的equals()方法找到正确的键值对，然后返回对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会存储在链表的下一个节点中。

2）LinkedHashMap实现类

LinkedHashMap使用双向链表来维护key-value对的次序（其实只需要考虑key的次序即可），该链表负责维护Map的迭代顺序，与插入顺序一致，因此性能比HashMap低，但在迭代访问Map里的全部元素时有较好的性能。

3）Properties

Properties类时Hashtable类的子类，它相当于一个key、value都是String类型的Map，主要用于读取配置文件。

4）TreeMap实现类

TreeMap是SortedMap的实现类，是一个红黑树的数据结构，每个key-value对作为红黑树的一个节点。TreeMap存储key-value对时，需要根据key对节点进行排序。TreeMap也有两种排序方式：

♦ 自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则会抛出ClassCastException。

♦ 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。

5）各Map实现类的性能分析

♦ HashMap通常比Hashtable（古老的线程安全的集合）要快

♦ TreeMap通常比HashMap、Hashtable要慢，因为TreeMap底层采用红黑树来管理key-value。

♦ LinkedHashMap比HashMap慢一点，因为它需要维护链表来爆出key-value的插入顺序。

 

6、、使用总结

• 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
• 如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。
• 要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
• 尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

三、Arrays

Java API对Arrays类的说明是：此类包含用来操作数组（比如排序和搜索）的各种方法。

常用方法

数组转字符串

int[] array = new int[]{1, 2, 3};
out.println(Arrays.toString(array)); //[1, 2, 3]

如果是一维数组，toString方法可以很好的适用。但遇到多维数组时，需要使用deepToString把数组完全转成字符串。

int[][] deepArray = new int[][]{{1, 3},{2, 4}};
out.println(Arrays.toString(deepArray)); //[[I@1540e19d, [I@677327b6]
out.println(Arrays.deepToString(deepArray)); //[[1, 3], [2, 4]]

填充数组

array = new int[5];
Arrays.fill(array, 2);
out.println(Arrays.toString(array)); //[2, 2, 2, 2, 2]

array = new int[5];
Arrays.fill(array, 1, 4, 2); //部分填充
out.println(Arrays.toString(array));//[0, 2, 2, 2, 0]

数组元素排序

array = new int[]{3, 10, 4, 0, 2};
Arrays.sort(array);
out.println(Arrays.toString(array)); //[0, 2, 3, 4, 10]

array = new int[]{3, 10, 4, 0, 2};
Arrays.parallelSort(array); //和sort相比是这个是并行的
out.println(Arrays.toString(array)); //[0, 2, 3, 4, 10]

array = new int[]{3, 10, 4, 0, 2};
Arrays.sort(array, 0, 4); //部分排序
out.println(Arrays.toString(array)); //[0, 3, 4, 10, 2]

自定义排序规则

假如想根据字符串的长度而不是根据字典顺序对字符串排序，但是String类我们是无法修改的。上面的代码对String数组进行排序，只能按照字典顺序对String数组进行排序。

Arrays.sort方法和Collections.sort方法都提供了一个可以接收Comparator实例作为第二个参数的版本。

要按照长度比较字符串，定义一个实现Comparator的类。

public class LengthComparator implements Comparator {
    @Override
    public int compare(String o1, String o2) {
        return o1.length() - o2.length();
    }
    public static void main(String[] args){
        String[] names = {"tom", "alice", "fred"};
        Arrays.sort(names, new LengthComparator());
        out.println(Arrays.toString(names));
    }
}

像Comparator、Runable等这=一些接口有一个特点就是只有一个抽象方法（其他的都是static或者default的方法），比如继承Comparator接口只需要重写compare方法，继承Runnable接口只需要重写run方法，这种类型的接口被称为函数式接口，可以被lambda表达式所代替。

比如上面根据字符串的长度进行排序的代码，Arrays.sort的第二个参数是需要实现了Comparator接口的实例，用lambda表达是就可以写成这样：

String[] names = {"tom", "alice", "fred"};
Comparator comp = (first, second) -> first.length() - second.length();
Arrays.sort(names, comp);

简单点

String[] names = {"tom", "alice", "fred"};
Arrays.sort(names, (first, second) -> first.length() - second.length());

Arrays.sort方法的第二个参数变量接受一个实现了Comparator接口的类的实例，调用该对象的compare方法会执行lambda表达式中的代码，所以这也就是为什么接口只有一个抽象方法的时候可以用lambda表达式代替。

数组的比较

array = new int[]{1, 2, 3};
int[] array2 = new int[]{1, 2, 3};
out.println(Arrays.equals(array, array2)); //true

和toString方法一样，equals方法遇到多维数组时也会出现问题。

int[][] deepArray1 = new int[][]{{1, 3},{2, 4}};
int[][] deepArray2 = new int[][]{{1, 3},{2, 4}};
out.println(Arrays.equals(deepArray1, deepArray2)); //false
out.println(Arrays.deepEquals(deepArray1, deepArray2)); //true

deepEquals用于判定两个指定数组彼此是否深层相等，此方法适用于任意深度的嵌套数组。

equals用于判定两个数组是否相等，如果两个数组以相同顺序包含相同元素，则返回true。

如果两个数组使用equals返回true，则使用deepEquals必定也返回true，也就是说在比较的两个数组均为一维数组的前提下，equals和deepEquals的比较结果没有差别。

数组复制

array = new int[]{3, 10, 4, 0, 2};
int[] arrayCopy = Arrays.copyOf(array, 3);
out.println(Arrays.toString(arrayCopy)); //[3, 10, 4]

arrayCopy = Arrays.copyOf(array, 7);
out.println(Arrays.toString(arrayCopy)); //[3, 10, 4, 0, 2, 0, 0], 多出的长度补0

arrayCopy = Arrays.copyOfRange(array, 1, 4);
out.println(Arrays.toString(arrayCopy)); //[10, 4, 0]

二分查找返回下标

array = new int[]{0, 3, 4, 10, 20};
out.println(Arrays.binarySearch(array, 10)); //3, array必须是排序的，否则得到的是错误的结果
out.println(Arrays.binarySearch(array, 6)); //-4, 找不到的值，从-1开始，6如果存在下标是3， 所以返回-4
out.println(Arrays.binarySearch(array, 2, 5, 10)); //3, 返回的还是全局的下标值。

数组转List

int array = new int[]{3, 10, 4, 0, 2};
out.println(Arrays.asList(array).contains(3)); //false

Integer arr[] = new Integer[]{3, 10, 4, 0, 2};
out.println(Arrays.asList(arr).contains(3)); //true

四、Collections

java.util.Collection 是一个 集合框架的父接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。

排序操作

reverse(List list)：反转指定List集合中元素的顺序

shuffle(List list)：对List中的元素进行随机排序（洗牌）

sort(List list)：对List里的元素根据自然升序排序

sort(List list, Comparator c)：自定义比较器进行排序

swap(List list, int i, int j)：将指定List集合中i处元素和j出元素进行交换

rotate(List list, int distance)：将所有元素向右移位指定长度，如果distance等于size那么结果不变

查找和替换（主要针对Collection接口相关）

binarySearch(List list, Object key)：使用二分搜索法，以获得指定对象在List中的索引，前提是集合已经排序

max(Collection coll)：返回最大元素

max(Collection coll, Comparator comp)：根据自定义比较器，返回最大元素

min(Collection coll)：返回最小元素

min(Collection coll, Comparator comp)：根据自定义比较器，返回最小元素

fill(List list, Object obj)：使用指定对象填充

frequency(Collection Object o)：返回指定集合中指定对象出现的次数

replaceAll(List list, Object old, Object new)：替换

同步控制

Collections工具类中提供了多个synchronizedXxx方法，该方法返回指定集合对象对应的同步对象，从而解决多线程并发访问集合时线程的安全问题。HashSet、ArrayList、HashMap都是线程不安全的，如果需要考虑同步，则使用这些方法。这些方法主要有：synchronizedSet、synchronizedSortedSet、synchronizedList、synchronizedMap、synchronizedSortedMap。

特别需要指出的是，在使用迭代方法遍历集合时需要手工同步返回的集合。

设置不可变集合

Collections有三类方法可返回一个不可变集合：
emptyXxx()：返回一个空的不可变的集合对象
singletonXxx()：返回一个只包含指定对象的，不可变的集合对象。
unmodifiableXxx()：返回指定集合对象的不可变视图

其它

disjoint(Collection c1, Collection c2) - 如果两个指定 collection 中没有相同的元素，则返回 true。

addAll(Collection c, T… a) - 一种方便的方式，将所有指定元素添加到指定 collection 中。示范：

Collections.addAll(flavors, “Peaches 'n Plutonium”, “Rocky Racoon”);

Comparator reverseOrder(Comparator cmp) - 返回一个比较器，它强行反转指定比较器的顺序。如果指定比较器为 null，则此方法等同于 reverseOrder()（换句话说，它返回一个比较器，该比较器将强行反转实现 Comparable 接口那些对象 collection 上的自然顺序）。

五、Comparator和Comparable

Java中Comparable和Comparator区别小结 - 温布利往事 - 博客园