[TOC]

集合结构图（来源于JavaGuide哥）Java 中集合又叫做容器，主要分为两大阵营：Collection、Map；前者用来存放单一元素，后者用来存放键值对；

Collection 主要包含两个集合类(1. List，List 集合的特点是，元素是有序的，可重复的) (2. Set 元素是无序的，不可重复的集合)
Map（映射）双列数据，保存映射关系的集合也就是传说中的 key-value 键值对儿

Collection 的主要实现接口有 List、Set、Queue；

List、Set、Map、Queue四者的区别

List 存储元素是有序的，可重复的！可以存放多个空值！
Set 存储的元素是无序的，不可重复的。可以存放一个 null 值，TreeSet 涉及到排序所以不可以存放 null；
Queue 按照特定的排队规则进行排序，存储的元素是有序的、可重复的；
Map 是用来存储键值对的，只能存放一个 null 值（因为其他的会被覆盖掉）；HashTable、TreeMap 依然不可以存放空值；

Collection 与数组的区别

数组的特点

数组一旦初始化就无法进行扩充，无法改变其数组长度和数据类型；
数组提供给我们的处理方法也是很少的，对于插入删除等操作还是非常的麻烦的；
数组中存储数据的特点是：有序性、可重复；

Collection 集合接口中常用的方法

@Testpublic void test1() {// 1. add(Object obj); 添加一个元素  注意 在Collection接口的实现类对象中// 添加obj时,要求obj所在的类必须重写equals()方法java.util.Collection coll = new ArrayList();coll.add(132);System.out.println(coll);  // [132]// 2. addAll(Collection coll); 添加一个Collection的集合的全部元素到现有的集合中java.util.Collection coll1 = new ArrayList();coll1.add(555);coll1.addAll(coll);System.out.println(coll1); // [555, 132]// 3. int size(); 返回集合中元素的个数System.out.println(coll.size());  // 1System.out.println(coll1.size()); // 2// 4. void clear(); 清空集合coll1.clear();System.out.println(coll1.size()); // 0// 5. boolean isEmpty(); 判断是否为空集合System.out.println(coll.isEmpty());  //falseSystem.out.println(coll1.isEmpty()); //true// 6. boolean contains(Object obj); 底层是通过元素调用equals()方法,// 判断是否为同一个对象// 注意,在用contains()方法查看集合中是否有该对象时,// 会直接调用该对象所在类的equals()方法// 此处用String时因为String类中对equals()类进行了重写coll.add(new String("hello"));boolean hello = coll.contains(new String("hello"));System.out.println(hello);  //true// 7. boolean containsAll(Collection coll);// 底层是通过调用equals()方法,对集合里的元素挨个比较// 判断形参coll中的所有元素是否都在当前集合中coll1.add(555);coll.add(555);coll1.add(new String("hello"));boolean b = coll.containsAll(coll1);System.out.println(coll);  // [132, hello, 555]System.out.println(coll1);  // [555, hello]System.out.println(b);  // true// 7. boolean remove(Object obj); 通过元素的equals()方法判断// 是否是要删除的那个元素,只会删除找到的第一个元素coll.remove(555);System.out.println(coll); // [132, hello]// 8. boolean removeAll(Collection coll);取当前集合与形参里集合的差集coll.removeAll(coll1);System.out.println(coll); // [132]// 9. retainAll(Collection coll);获取当前集合对象和形参里集合的交集,// 并返回给调用者java.util.Collection coll2 = Arrays.asList(132, 563);coll.retainAll(coll2);System.out.println(coll); // [132]// 10. equals(Object obj); 比较两个集合里的元素是否一样// 这里要注意区分 集合是否有序// 11. hashcode(); 返回当前对象的哈希值// 12. toArray(); 集合-->数组Object[] objects = coll2.toArray();System.out.println(Arrays.toString(objects));// 13. 数组-->集合 Arrays.asList();List list = Arrays.asList(45, 66, 48, "hello world");System.out.println(list); //[45, 66, 48, hello world]System.out.println("长度为:" + list.size());//长度为:4List<String> list1 = Arrays.asList(new String[]{"hello java","你好"});System.out.println(list1); //[hello java, 你好]System.out.println("长度为:" + list1.size()); //长度为:2List list3 = Arrays.asList(new int[]{1, 3, 5});System.out.println("长度为:" + list3.size()); //长度为:1List list4 = Arrays.asList(new Integer[]{154, 15, 33, 46});System.out.println(list4);  //[154, 15, 33, 46]System.out.println("长度为:" + list4.size()); //长度为:4}

遍历集合

Iterator 遍历集合，用于遍历 Collection 集合注意：集合对象每次调用 iterator() 都会得到一个全新的迭代器；

方式一

通过for循环遍历不推荐使用

for (int i = 0; i < list4.size(); i++) {System.out.println("第"+ (i+1) +"个元素"+ iterator.next());}

方式二

通过配合迭代器的 hasNext() 方法使用 while 循环进行遍历

hasNext() 判断下一个位置是否有元素

while (iterator.hasNext()) {// next(),将指针下移,并输返回下移后位置上的元素System.out.println(iterator.next());}

Collection 的子接口 List

List 正如我们上面提到的，元素是有序的，可重复的，底层是数组。但是也是需要重写 equals( ) 方法的，因为判断元素是否存在的时候是需要的；

List接口主要有三个实现类

概述

ArrayList 作为一个 List 接口的主要实现类而存在，也是我们平时用的比较多的一个集合类；
LinkedList 双向链表(1.6包括之前为循环链表)，具体的 LinkedList 我们下面会做具体分析；
Vector 是作为 List 接口的一个古老的实现类而存在的；

差异

相同点：都实现了 List 接口，切都遵循 List 的特点，元素有序，且可重复；

不同点：

ArrayList 作为 List 接口的主要实现类，是线程不安全的，但是效率极高（底层使用Object elementData 存储数据）；
LinkedList 对于频繁的插入删除操作来说，比 ArrayList 的效率高得多，因为其底层实现是双向链表；
Vector 作为一个古老的实现类而存在，线程安全，但效率底下，底层视同 Object elementData 存储数据；

对于 ArrayList 的源码简略分析

基于 jdk1.7

ArrayList list = new ArrayList();

底层创建了长度为 10 的 Object [ ] 数组 ElementData，然后直接对创建好的数组进行赋值,如果不够则进行扩容（默认情况下扩容为原来的 1.5 倍），同时将原来的数组复制到新的数组当中；

基于 jdk1.8

ArrayList list = new ArrayList();

底层数组进行了初始化，Object [ ] elementData 初始化为，并没有创建长度，当第一次调用 add()；添加元素时，底层才进行了创建长度为 10 的数组,并将数据添加到数组当中.后面的操作则与 jdk1.7 无异jdk1.7 中的 ArrayList 的对象的创建类似于单例的饿汉式，而 jdk1.8 中的 ArrayList 的对象的创建类似于单例模式的懒汉式,延迟了数组的创建,节省内存；结论：建议使用带有参数的构造器：

ArrayList list = new ArrayList(int capacity);

直接初始化容量；

对 LinkedList 的源码分析

LinkedList list = new LinkedList();

内部声明了 Node 类型的 first 和 last 属性,默认值为 null，

list.add();

将对象封装到 Node 中,创建了 Node 对象Node 的定义体现了 LinkedList 的双向链表的说法

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;}}

List 接口特有的常用方法

总结:常用方法// 增add(Object obj);// 删remove(int index);remove(Object obj));// 改set(int index,Object ele);// 查get(int index)// 插add(int index,Object ele)// 长度size()// 遍历Iterator // 迭代器

增加元素

@Testpublic void test() {ArrayList list = new ArrayList();list.add(123);list.add(556);list.add("hello");list.add(new person("小红", 23, "女"));System.out.println(list);//[123, 556, hello, person{name=\'小红\', age=23, sex=\'女\'}]}

在指定索引位置插入 ele 元素 add(int index,ele)；

@Testpublic void test1() {ArrayList list = new ArrayList();list.add(123);list.add(556);list.add("hello");list.add(new person("小红", 23, "女"));System.out.println(list);// [123, 556, hello, person{name=\'小红\', age=23, sex=\'女\'}]list.add(2, new person("小黄", 22, "男"));System.out.println(list);// [123, 556, person{name=\'小黄\', age=22, sex=\'男\'}, hello, person{name=\'小红\', age=23, sex=\'女\'}]}

从指定索引位置开始将 eles 中的所有元素都添加进来

@Testpublic void test2() {ArrayList list = new ArrayList();ArrayList list1 = new ArrayList();list.add(123);list.add(556);list.add("hello");list.add(new person("小红", 23, "女"));list1.add(45);list1.add(36);list1.add(86);System.out.println(list1); // [45, 36, 86]list1.addAll(2, list);System.out.println(list1);// [45, 36, 123, 556, hello, person{name=\'小红\', age=23, sex=\'女\'}, 86]}

取指定索引位置的元素 get(int index)

@Testpublic void test3() {ArrayList list = new ArrayList();list.add(123);list.add(556);list.add("hello");list.add(new person("小红", 23, "女"));System.out.println(list);// [123, 556, hello, person{name=\'小红\', age=23, sex=\'女\'}]System.out.println(list.get(3)); // person{name=\'小红\', age=23, sex=\'女\'}}

返回 obj 在集合中首次出现的位置 int indexOf(Object obj); 返回 obj 在当前集合首次出现的位置

@Testpublic void test4() {ArrayList list = new ArrayList();list.add(123);list.add(556);list.add("hello");System.out.println(list.indexOf(556)); // 1}

返回 obj 在集合中最后一次出现的位置

@Testpublic void test5() {ArrayList list = new ArrayList();list.add(123);list.add(123);list.add(556);list.add(556);list.add(123);list.add("hello");System.out.println(list.lastIndexOf(123)); // 4}

移除指定索引位置的元素,并返回该元素 Object remove(int index);

@Testpublic void test6() {ArrayList list = new ArrayList();list.add(123);list.add(123);list.add(556);System.out.println("移除前:" + list); // 移除前:[123, 123, 556]Object remove = list.remove(2);System.out.println("移除的值为:" + remove); // 移除的值为:556System.out.println("移除后:" + list); // 移除后:[123, 123]}

指定索引位置的元素设置为 ele

@Testpublic void test7() {ArrayList list = new ArrayList();list.add(123);list.add(123);list.add(556);System.out.println("设置前:" + list); // 设置前:[123, 123, 556]list.set(0, new person("小明", 23, "男"));System.out.println("设置后:" + list); // 设置后:[person{name=\'小明\', age=23, sex=\'男\'}, 123, 556]}

返回指定区间的集合的子集合 List subList(int fromIndex,int toIndex);

@Testpublic void test8() {ArrayList list = new ArrayList();list.add(123);list.add(556);list.add("hello");list.add(new person("小红", 23, "女"));List list1 = list.subList(1, 3);System.out.println(list); //[123, 556, hello, person{name=\'小红\', age=23, sex=\'女\'}]System.out.println(list1); //[556, hello]}

Set接口

Set 接口是 Collection 的子接口，Set 接口没有提供额外的方法，Set 存储无序的、不可重复的数据

Set 接口中不允许包含相同的元素(无序且唯一)，若强行添加会使得添加操作失败
Set 判断两个对象是否相同只能调用equals();

所以，Set是严格的

要求：

在 Set 中添加的数据一定要重写 equals()、hashCode();
重写的 equals( )、hashCode( )，保证相同的对象的哈希值是相同的，即 equals( ) 与 hashCode( ) 返回值都是true

无序性以及不可重复性的理解：

底层数据的存储依然是以数组的形式进行存储，但是无序不等于随机，当我们添加数组的时候，并不是按照数组的索引进行添加，而是根据哈希值进行添加。

存数据的过程

如果计算的哈希值不同，则表明数据不一样，直接添加成功，
如果计算的哈希值相同，那么就会调用其equals();进行比较，如果经过equals();比较后返回的值不是true那么证明不一样，添加成功。
如果哈希值相同，equals返回为false，那么就会在对应的哈希值的位置以链表的方式添加数据。以链表的方式添加数据的

针对上述的第三种情况又有：

规则,新的 hash 值相同的元素放在同一个位置的数组里，其顺序在jdk7.0/8.0中有些许不同

基于JDK7.0：新的元素放到数组中，并指向原来的旧元素
基于JDK8.0：原来的元素在数组中，指向新的元素

总结：七上八下(指的是新元素的存放位置，七、新的元素放在原来的数组的位置(上边)，旧的元素向下移动，在链表中，新的元素指向旧的元素；八、新的元素放在链表中，在链表中，旧的指向新的)

Set接口有三个实现类:

HashSet 基于 HashMap（底层是数组 + 链表）实现的，底层使用 HashMap 来保存元素，作为 Set 接口的主要实现类，线程不安全；
LinkedHashSet 作为 HashSet 的子类，遍历其中的元素，可以按照添加顺序来遍历，对于频繁的遍历操作，效率高于 HashSet，是因为在 HashSet 的基础上在数组给每个元素都加上了指针，使数据变成双向链表。
TreeSet 可以按照对象的指定属性进行排序，要求添加的数据是相同类的对象

Set的实现类 HashSet 的实现以及练习

@Testpublic void test1() {Set set = new HashSet();set.add("hello");set.add(123);set.add("abc");set.add(123);set.add(new person("小红", 29, "男"));set.add(new person("小红", 29, "男"));Iterator iterator = set.iterator();while (iterator.hasNext()) {System.out.println(iterator.next());}}

输出结果

abcperson{name=\'小红\', age=29, sex=\'男\'}hello123

LinkedHashSet 是 HashSet 的子类，根据添加元素的顺序来遍历集合

@Testpublic void test2() {Set set = new LinkedHashSet();set.add("hello");set.add(123);set.add("abc");set.add(123);set.add(new person("小红", 29, "男"));set.add(new person("小红", 29, "男"));Iterator iterator = set.iterator();while (iterator.hasNext()) {System.out.println(iterator.next());}}

输出结果

hello123abcperson{name=\'小红\', age=29, sex=\'男\'}

TreeSet，向 TreeSet 中添加数据，要求是相同类的对象，两种排序方式：自然排序、定制排序

自然排序中，比较两个对象是否相同的标准为：compareTo() 返回 0 ，而不再是 equals() 方法定制排序中，比较两个对象是否相同的标准是 compare() 但是规则是一样的

@Testpublic void test3() {//编写比较规则Comparator comparator = new Comparator() {@Overridepublic int compare(Object o1, Object o2) {if (o1 instanceof person && o2 instanceof person) {person p1 = (person) o1;person p2 = (person) o2;return p1.getName().compareTo(p2.getName());} else {throw new RuntimeException("数据异常！");}}};//应用比价规则TreeSet treeSet = new TreeSet(comparator);  //在有参数的情况下，会根据参数对象中所定义的排序方式进行排序，// 若没有，将会按照添加的对象中实现的comparable接口后重写的compareTo();的规则进行排序treeSet.add(new person("孔乙己", 33, "女"));treeSet.add(new person("祥林嫂", 22, "男"));treeSet.add(new person("鲁迅", 18, "女"));Iterator iterator = treeSet.iterator();//通过age进行自然排序while (iterator.hasNext()) {System.out.println(iterator.next());}}

输出结果：

person{name=\'孔乙己\', age=33, sex=\'女\'}person{name=\'祥林嫂\', age=22, sex=\'男\'}person{name=\'鲁迅\', age=18, sex=\'女\'}

Map

Map，并列于 Collection 接口，用于存储双列数据（键值对 key – value）

HashMap 作为 Map 的主要实现类存在，与 ArrayList 的存在地位相似，线程不安全、但是效率高，可以存储一个 null 的 key – value，key 所在的类要重写equals( ) 和 hashCode( )；
LinkedHashMap，HashMap 的子类、Map 的实现类，在 HashMap 的底层基础上，添加了指针，构成链表，对于频繁的遍历操作，执行效率高于 HashMap
TreeMap 按照添加的 key-value 对进行排序，实现排序遍历，底层的实现是红黑树；
Hashtable 作为古老的实现类，线程安全、效率低下，不能够存储空的 key-value；
Properties，常用来处理配置文件，key-value 都是 String 类型；

HashMap 的底层:

数组+链表（jdk7及以前）数组+链表+红黑树（jdk8+）

对于 Map 结构的理解：

Map 中的 key：无序的、不可重复的、使用 Set 存储所有的 key ；
Map 中的 value：无序的、可重复的，使用 Collection 存储所有的 value，value 所在的类要重写 equals( )；
一个键值对：key-value 构成一个 Entry 对象；
Map 中的 entry：无序的、不可重复的，使用 Set 存储所有的 entry；

对 Map 底层原理的理解

JDK7为例说明：

HashMap map = new HashMap(); 在实例化之后，底层创建了一个长度为 16 的一维数组 Entry [ ] table。

当我们往 HashMap 中添加数据的时候

map.put(ket1,value1);

首先调用 key1 所在类的 hashCode() 计算哈希值，若哈希值所对应的 Entry 数组的位置上的数据为空，那么此时的(key1,value)添加成功；

以上哈希值相同的情况均以链表的方式进行存储（遵循七上八下）
在不断地添加过程中会涉及扩容问题，当 size 超出临界值且要存放的位置非空，扩容为原来的两倍，并将原来的数据复制过来；

JDK8 在底层与JDK7的不同之处：

```
new HashMap();
```
底层没有创建一个长度为16的数组
JDK8 底层的数组是 Node ，而非 Entry；
首次使用 put()，的时候，底层创建长度为 16 的数组
jdk7 底层结构只有：数组+链表。而 JDK8 底层结构为 数组+链表+红黑树。
当数组的某一个索引位置上的元素以链表的形式存在的数据个数 > 8，且当前数组的长度>64时，此时此索引位置上的所有数据改为红黑树存储

底层主要关键字

DEFAULT_INITIAL_CAPACITY (初始默认容量)：HashMap的默认容量：16
DEFAULT_LOAD_FACTOR(HashMap的默认加载因子)：0.75
threshold(扩容的临界值):容量*扩容因子：16 X 0.75 = 12
TREEIFY_THRESHOLD_THRESHOLD:Bucket中链表长度大于该默认值，就转化为红黑树：8
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量：64

Java 集合框架