第9章 集合

9.1 概念

• 用于存储数量不等的多个对象、具有映射关系的关联数组。

9.2 集合框架体系

1. 单列集合（Collection）：存放单个对象，有两个重要的子接口，其实现子类都是单列集合。

• List：

• ArrayList
• Vector
• LinkedList

• Set：

• HashSet

• LinkedHashSet

• TreeSet

• 

2. 双列集合（Map）：存放k-v形式的数据

• Hashtable

• Properties

• HashMap

• LinkedHashMap

• TreeMap
• 

9.3 Collection

9.3.1 Collection接口的特点

1. Collection接口没有直接的实现子类，是通过它的子接口Set和List实现的。
2. Collection实现子类可以存放多个元素，每个元素可以是Object
3. Collection的实现类，List是有序的，Set不是有序的
4. Collection的实现类，有的可以存放重复的元素，有的不可以

9.3.2 Collection接口实现类遍历元素方式

1. Tterator（迭代器）：

• 所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个迭代器
• Iterator仅用于集合遍历，本身并不存放对象。
• 使用流程：

• 创建迭代器：Iterator it = 集合对象.iterator()
• 遍历对象：while(it.hasNext()){it.next()}

• 使用it.next()之前必须使用hasNext()方法进行判断，否则在调用完最后一条时会抛出NoSuchElementException异常。
• while循环结束后，迭代器指向集合中最后一个元素，如果再调用next()方法，会抛出异常，如果希望再次遍历，则需要重置迭代器：it = 集合对象.iterator()

• IDEA快捷模板：itit，Ctrl+j显示所有的快捷模板

2. 增强for循环：

• 语法：for( 元素类型 元素名 : 集合名或数组名){ 访问元素 }
• 只能用于遍历集合和数组。
• 本质就是简化版的迭代器（底层代码）。

3. 不可用普通for循环，因为子接口Set不支持索引

9.4 List

9.4.1 特点

1. List集合类的元素有序（添加和取出顺序一致），且可重复。
2. List集合类每个元素都有器对应的顺序索引，可通过索引取出元素——使用get()
3. List接口实现类常用的有ArrayList、LinkedList、Vector

• 

9.4.2 常用方法

9.4.3 遍历方式

1. 使用Iterator迭代器：迭代器的next()取出的就是每个对象
2. 使用增强for循环
3. 使用普通for循环

9.4.4 ArrayList

1. 特点：

• 可以存放null，且可存放多个
• 基本等同于Vector，但ArrayList线程不安全。

2. 底层：

• ArrayList的数据由一个transient修饰的Object[] 存储。可变数组

• transient表示不可被序列化

• ArrayList()：初始容量为0，第一次添加元素容量变为10，后续扩容按照当前容量的1.5倍增大
• ArrayList(int initialCapacity)：初始容量为initialCapacity，后续扩容按照当前容量的1.5倍增大

3. IDEA补充知识：

• IDEA在debug时，会阉割数据
• 解决方式：（去掉下列两个红框的勾选）。

• 

9.4.5 Vector

1. 特点：

• 可以存放null，且可存放多个
• Vector类的操作方法带有synchronized，所以是线程安全的。

2. 底层：

• 底层使用Object[]存放数据
• Vector()：初始容量0，第一次添加后10，不足时按当前容量的2倍扩容。
• Vector(int initialCapacity)：初始容量为initialCapacity，不足时按当前容量的2倍扩容。

9.4.6 LinkedList

1. 特点：

• 可以存放null，且可存放多个
• 线程不安全，添加删除效率比数组高，查找效率较低

2. 底层：

• 底层维护了一个双向链表

• LinkedeList中有两个属性first、last，分别指向链表中第一个和最后一个节点
• 每个节点都含有3个属性：prev、next、item
• 只有无参构造器LinkedList()，默认容量0，添加一个数组，容量+1。

3. LinkedList和ArrayList的选择

• 改查较多，选择ArrayList
• 增删较多，选择LinkedList

• 业务中，一般查询较多、增删较少，建议使用ArrayList

9.5 Set

9.5.1 特点

1. 无序（添加和取出顺序不一定一致），元素不可重复，最多只可包含一个null。

• 元素不可重复按照equals是否相等理解。（基本数据类型会自动装箱，但包装类重写了equals方法，比较的还是具体值；字面量字符串在常量池；构造器创建的字符串比较的也是具体内容（equals））
• 但一旦数据确定，每次的取出顺序一致
• hashcode是根据对象的地址值确定的

2. 没有索引
3. 常用实现类有：HashSet、LinkedHashSet、TreeSet

• 

9.5.2 常用方法

9.5.3 遍历方式

1. 迭代器
2. 增强for循环
3. 不能使用普通for循环

9.5.4 HashSet

1. 特点：

• 可以存放null，但只能存放一个。
• 相同数据只能存放一个

• 注意字符串的特殊性（面试题）：
• 其他对象可以添加成功：

• 数据存入与取出顺序不一定一致

2. 底层（数据结构）：

• 底层实际上是HashMap，而HashMap的底层是数组+链表+红黑树

• 调用HashSet构造器后，会先执行HashMap()构造器，并创建table表（数组），初始容量为0，再取得加载因子0.75
• 添加元素时，先计算得到该元素的hash值，并转换得到索引值
• 第一次添加时，将table扩容到16，并把第一次添加的元素放到表中的指定位置
• 后续添加时，比较索引值，如果表中该索引已有值，则在该值后的数据链中比较，添加到最后

• 注意：这里比较元素内容是否相同，取决于加入元素的equals()方法，通过重写equals()和hasCode()可以控制元素能否加入

• JAVA8中，如果数据链的数据已有8个，先对表按2倍进行扩容，如果表已经扩容过，并且表到了64，则将该表转换为红黑树
• 平时链表数据没到8个，但表到达12个（16*0.75），就会对表按照2倍进行扩容，并以此类推

• 数组类型为HashMap$Node，数据类型为HashMap$Node。

9.5.5 LinkedHashSet

1. 特点：

• HashSet的子类、并实现了Set接口
• 可以存放null、但只能存放一个
• 相同数据只能添加一个
• 元素取出顺序固定，且与加入顺序一致。

2. 底层：

• 底层使用了一个hashtable（数组） 和双向链表存储数据，

• 数组是HashMap$Node类型

• 数组有head和tail

• 数据类型为LinkedHashMap$Entry类型，LinkedHashMap是HashMap的子类。

• 每个元素有before和after

• 初始容量为0，第一次添加时，直接将数组table 扩容到16，再添加一个元素时，先求hash值，再求索引，确定在表中的位置，然后再将元素添加到链表中【机制同HashSet】

9.5.6 TreeSet

1. 特点：

• 使用无参构造器时，仍然是无序的（输出顺序与输入顺序不一致）。
• 使用带比较器的构造器TreeSet(Comparator<? super E> comparator)：可以设定指定的添加规则及顺序。

• 添加规则：取决于比较器中比较的属性，比较器返回0时则不能加入
• 顺序：根据比较器指定的顺序或者逆序确定。
• 匿名内部类的比较器规则会被创建时底层的compare()调用

2. 底层：

• 底层就是TreeMap，TreeMap底层就是Entry
• 存放的数据类型是TreeMap$Entry
• 初始化大小是0，添加一个容量+1

9.6 Map

9.6.1 Map接口的特点

1. Map与Collection并列存在，用于保存具有映射关系的数据。key-value（双列元素）。
2. Map中的key和value可以时任意数类型，会封装到HashMap$Node对象中，数据类型为HashMap$Node。
3. Map中的key不允许重复，原因同HashSet（key相同则hashcode和索引值相同，在table表（数组）的位置相同），相同的key等价于替换元素。
4. Map中的value可以重复
5. Map中的key可以为null，value也可以为null，key为null时只能添加一个（等价于替换），value可以多个为null
6. Map中常用String作为key，实际上key只要是Object就都可以（包含基本数据类型）
7. Map中的key和value存在一一对应关系，使用get(key)，就可以得到唯一的一个value
8. Map中的数据存储：一对k-v是存放在HashMap$Node中的，由于Node实现了Entry接口，所以在一定理解上，可以说一对k-v就是一个Entry

• 源码韩顺平分析：

• k-v 最后是 HashMap$Node node = newNode(hash, key, value, null)
• k-v 为了方便程序员的遍历，还会创建 EntrySet 集合 ，该集合存放的元素的类型 Entry, 而一个Entry对象就有k,v EntrySet<Entry<K,V>> 即： transient Set<Map.Entry<K,V>> entrySet;
• entrySet 中， 定义的类型是 Map.Entry ，但是实际上存放的还是 HashMap$Node这是因为 static class Node<K,V> implements Map.Entry<K,V>
• 当把 HashMap$Node 对象 存放到 entrySet 就方便我们的遍历, 因为 Map.Entry 提供了重要方法K getKey(); V getValue();
• 

• 源码个人理解：

• k-v在创建时执行的是HashMap$Node node = newNode(hash, key, value, null)，所以k-v的数据类型就是HashMap$Node，数组类型也是HashMap$Node。
• Map.Entry有重要的getKey()、getValue()可以获取元素的k-v值，有了这两个方法，就大大方便了使用（遍历）。

• 而在Map中，通过keySet()获取Set类型的所有key，values()获取Collection类型的所有vaule，将这二者存放在了一个Set表中。
• 这个Set表就是EntrySet集合，集合中每一个元素是Entry类型，拥有key和value：transient Set<Map.Entry<K,V>> entrySet;

• EntrySet和Node都是HashMap的内部类

• 为了使HashMap$Node类型的数据能够用上面两个方法，HashMap$Node类实现了Map.Entry：static class Node<K,V> implements Map.Entry<K,V>

9. 常用实现类：HashMap（使用率最高）、Hashtable、Properties

• 

9.6.2 Map接口常用方法

9.6.3 Map接口遍历方法

1. 方式一：使用Map的keySet()方法取出所有的key，而取出的key类型为Set，因此可以使用两种方式：

• 增强for循环：
• 使用迭代器：

• 迭代器的next()取出的是key

2. 方式二：使用Map的values()方法取出所有的value，而取出的value类型为Collection，因此可以使用两种方式：

• 增强for循环：
• 使用迭代器：

• 迭代器的next()取出的是value

3. 方式三：使用Map的entrySet()方法取出所有的entry，而取出的entry类型为HashMap$Node，HashMap$Node实现了Map.Entry，而Map.Entry有getKey()和getValue()

• 使用EntrySet的增强for循环：

• 前提条件：使用向上转型，转为Map.Entry。

• 使用迭代器：

• 迭代器的next()取出的是entry，entry类型为HashMap$Node，HashMap$Node实现了Map.Entry。
• 

9.6.4 HashMap

1. 特点：

• 使用率最高
• key不能重复，但value可以重复，允许使用null的key和null的value
• 如果添加相同的key，则会覆盖原来的key-val，等同于修改（替换）
• 线程不安全

2. 底层：

• 底层以key-val的方式来存储数据（数组及数据均为HashMap$Node类型）
• 与HashSet一样，不保证映射顺序，因为底层是以hash表的方式来存储（数组+链表+红黑树）
• 
• 扩容机制：同HashSet，唯一区别在于HashSet计算哈希值是元素，HashMap计算时是key
• 初始化数据容量为0

9.6.5 LinkedHashMap

1. 特点：

• 继承了HashMap，实现了Map。
• 线程不安全
• 如果有相同key，后者替换前者；value可以重复，允许使用null的key和null的value

2. 底层

• 底层使用数组+双向链表 转 红黑树
• 初始容量为0

9.6.6 Hashtable

1. 特点：

• 键和值都不能为null，会抛出NullPointerException
• 线程安全的

2. 底层：

• 底层是一个数组，类型为Hashtable$Entry，实现了Map.Entry。元素类型也为Hashtable$Entry
• 初始化大小为11，临界值为8（11*0.75）
• 当添加数据数量到达8时，对数组进行扩容，扩容为当前容量 * 2 + 1，新的临界值变为当前容量 * 0.75

9.6.7 Properties

1. 特点：

• 继承了Hashtable：不能添加null的key或value，会发生NullPointerException
• 线程安全
• 如果有相同key，后者替换前者
• 可以用与xxx.properties文件中，加载数据到Properties类中进行读取和修改

2. 底层

• 初始容量为0，底层使用数组，元素类型、扩容机制同Hashtab

9.6.8 TreeMap

1. 特点：

• 使用无参构造器时，仍然是无序的（输出顺序与输入顺序不一致）。
• 使用带比较器的构造器TreeMap(Comparator<? super E> comparator)：可以设定指定的添加规则及顺序。

• 添加规则：取决于比较器中比较的属性，比较器返回0时则不能加入
• 顺序：根据比较器指定的顺序或者逆序确定。
• 匿名内部类的比较器规则会被创建时内部的compare()调用

2. 底层：

• 底层就是Entry
• 存放的数据类型是TreeMap$Entry
• 初始化大小是0，添加一个容量+1

比较（个人总结）：

注意：容量和size()不同。size()指的是有多少实际的数据。

9.7 Collections工具类

9.7.1 介绍

1. 操作Set、List、Map等集合的工具类。
2. 能够对集合进行排序、查找、修改等工作。

https://www.runoob.com/manual/jdk1.6/java.base/java/util/Collections.html

9.7.2 排序操作：

1. reverse(List)：反转List中的元素顺序
2. shuffle(List)：对List集合进行随机排序，每次调用都进行一次随机
3. sort(List)：对List结合的元素进行自然排序（从小到大）
4. sort(List, Comparator)：根据比较器的规则对List集合的元素进行排序
5. swap(List, int i, int j)：交换List和i和j位置的元素

• i或j超范围时抛出索引越界异常

9.7.3 查找、替换

• 使用copy()方法前必须确认目标集合与源集合有同样的size（注意size不是容量），否则会发生数组越界异常。