Collection、Map
容器
容器主要用来保存对象，Java 中有两个顶层接口 Collection、Map。
Collection 接口
- List 有序、重复、自动扩容、非线程安全：常见 List 的实现类有 ArrayList、Vector、LinkedList 等……
- Set 无序、不可重复、非线程安全：常见 Set 接口的实现类有 HashSet、LinedHashSet、TreeSet 等……
Map 接口
- key value 存储：常见的 Map 接口实现类有 HashMap、TreeMap。
接口抽象与数据结构
通过接口的抽象，很好的屏蔽了底层数据结构的差异，并且为开发者提供了统一的 API 来使用底层不同的实现类。
List 接口
List 数据结构
List 接口是 ⼀个有序的 Collection，线性列表接 ⼝，能够精确的控制每个元素插 ⼊的位置，能 够通过索引(类似于数组的下标)来访问 List 中的元素，第 ⼀个元素的索引为 0，⽽且允许有相同 的元素，接 ⼝存储 ⼀组不唯 ⼀，有序（插 ⼊顺序）的对象。
List 接口的实现类
- ArrayList：基于数组实现，是 ⼀个动态的数组队列，但它和 Java 中的数组 ⼜不 ⼀样，它的容量可以 ⾃动增 ⻓。可以存储任意多的对象，但是只能存储对象，不能存储原 ⽣数据类型例如 int。访问元素的速度快 O(1)，插入和删除元素开销较大 O(n)。
- LinkedList：基于的数据结构是链表，⼀个双向链表，链表数据结构的特点是每个元素分配的空间不 必连续。插 ⼊和删除元素时速度 ⾮常快 O(1)，但访问元素的速度较慢 O(n)。
常用 API
1//初始化容器
2 ArrayList<String> arrayList = new ArrayList<>(5);
3 LinkedList<String> linkedList = new LinkedList<>();
4
5 //添加对象
6 arrayList.add("Howard");
7 arrayList.add("tom");
8 arrayList.add("alice");
9
10 //输出
11 System.out.println(arrayList);//[Howard, tom, alice]
12
13 //通过指定index获取元素
14 arrayList.get(0);
15
16 //更新元素
17 arrayList.set(1, "tomcat");
18
19 //返回集合容器中已存储对象的数量
20 arrayList.size();
21
22 //根据指定索引删除元素 返回删除的对象
23 arrayList.remove(1);
24
25 //根据对象删除元素 删除成功返回true
26 arrayList.remove("alice");
27
28 //清空容器
29 arrayList.clear();
30
31 //是否为空
32 arrayList.isEmpty();
33 }
Set 接口
Set 数据结构
- Set 相对于 List 是简单的 ⼀种集合，具有和 Collection 完全 ⼀样的接 ⼝，只是实现上不同，Set 不保存重复的元素，存储 ⼀组唯 ⼀，⽆序的对象。
- Set 中的元素是不能重复的， 实现细节可以参考 Map，因为这些 Set 的实现都是对应的 Map 的 ⼀ 种封装。⽐如 HashSet 是对 HashMap 的封装，TreeSet 对应 TreeMap
- Set 底层是 ⼀个 HashMap，由于 HashMap 的 put()⽅法是 ⼀个键值对，当新放 ⼊ HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 相同（hashCode()返回值相等，通过 equals ⽐较也返回 true），新添加的 Entry 的 value 会将覆盖原来 Entry 的 value，但 key 不会有任何改变。
- 允许包含值为 null 的元素，但最多只能有 ⼀个 null 元素
Set 接口的实现类
- HashSet：HashSet 类按照哈希算法来存取集合中的对象，存取速度比较快。
- TreeSet：TreeSet 类实现了 SortedSet 接口，能够对集合中的对象进行排序。
1public void setTesting(){
2 //初始化容器
3 HashSet<String> hashSet = new HashSet<>();
4
5 //添加对象
6 hashSet.add("jack");
7
8 //返回容器大小
9 hashSet.size();
10
11 //根据对象删除元素
12 hashSet.remove("jack");
13
14 //是否为空
15 hashSet.isEmpty();
16
17 //清空元素
18 hashSet.clear();
19 }
HashSet 与 TreeSet 区别
- HashSet 不能保证元素的排列顺序，TreeSet 是 SortedSet 接 ⼝的唯 ⼀实现类，可以确保集合 元素处于排序状态。
- HashSet 底层 ⽤的是哈希表，TreeSet 采 ⽤的数据结构是红 ⿊树（红 ⿊树是 ⼀种特定类型的 ⼆ 叉树）。
- HashSet 中元素可以是 null，但只能有 ⼀个，TreeSet 不允许放 ⼊ null。
- ⼀般使 ⽤ HashSet，如果需要排序的功能时，才使 ⽤ TreeSet（性能原因）。
Map 接口
Map 数据结构
- 底层就是 ⼀个 table（数组结构），数组中的每 ⼀项 ⼜是 ⼀个链表，即数组和链表的结合体。
- Table 是数组，数组的元素是 Entry。
- Entry 元素是 ⼀个 key-value 键值对，它持有 ⼀个指向下 ⼀个 Entry 元素的引 ⽤，table 数组的 每个 Entry 元素同时也作为当前 Entry 链表的 ⾸节点，也指向了该链表的下 ⼀个 Entry 元素。
Map 接口的实现类
HashMap
- ⼀个散列桶（数组和链表），它存储的内容是键值对(key-value)映射。
- 是基于 hashing 的原理，使 ⽤ put(key, value)存储对象到 HashMap 中，使 ⽤ get(key)从 HashMap 中获取对象。当 put()⽅法传递键和值时，会先对键调 ⽤ hashCode()⽅法，计算并返回的 hashCode 是 ⽤于找到 Map 数组的 bucket 位置来储存 Entry 对象的，是非线程安全的，所以 HashMap 操作速度很快。
- HashMap 可实现快速存储和检索，但缺点是包含的元素是 ⽆序的，适 ⽤于在 Map 中插 ⼊、删除和定位元素。
TreeMap
- 在数据的存储过程中，能够 ⾃动对数据进 ⾏排序，实现了 SotredMap 接 ⼝，它是有序的集合。
- TreeMap 使 ⽤的存储结构是平衡 ⼆叉树，也称为红 ⿊树。
- 默认排序规则：按照 key 的字典顺序来排序（升序），也可以 ⾃定义排序规则，要实现 Comparator 接 ⼝。
- TreeMap 能便捷的实现对其内部元素的各种排序，但其 ⼀般性能 ⽐ HashMap 差，适 ⽤于 按 ⾃然顺序或 ⾃定义顺序遍历键(key)
常用 API
1public void mapTesting(){
2 //初始化容器
3 HashMap<String, String> hashMap = new HashMap<>();
4 TreeMap<String, String> treeMap = new TreeMap<>();
5
6 //容器添加对象
7 hashMap.put("小张", "男");
8 hashMap.put("小王", "男");
9
10 //判断是否包含某个key
11 hashMap.containsKey("小张");
12
13 //根据key获取value
14 hashMap.get("小张");
15
16 //返回map的元素数量
17 hashMap.size();
18
19 //清空容器
20 hashMap.clear();
21
22 //获取所有value的集合
23 Collection<String> collection = hashMap.values();
24
25 //返回所有的key的集合
26 Set<String> set = hashMap.keySet();
27
28 //返回⼀个Set集合，集合的类型为Map.Entry , 是Map声明的⼀个内部接⼝，接⼝为泛型，定义为Entry<K,V>，
29 //它表示Map中的⼀个实体(⼀个key-value对),主要有getKey(),getValue⽅法
30 Set<Map.Entry<String, String>> entrySet = hashMap.entrySet();
31 for (Map.Entry<String, String> entry : entrySet) {
32 System.out.println(entry.getKey()); //小王
33 System.out.println(entry.getValue()); //男
34 }
35 //判断map是否为空
36 hashMap.isEmpty();
37 }
jdk1.7 和 jdk1.8 中 HashMap 的主要区别
底层实现由之前的 “数组 + 链表” 改为 “数组 + 链表 + 红 ⿊树”。
什么时候开始转变
当链表节点较少时仍然是以链表存在，当链表节点较多时，默认是 ⼤于 8 时会转为红黑树。
1static final int TREEIFY_THRESHOLD = 8;
练习一
统计每个字符出现的次数。
1/**
2 * 练习一：统计每个字符出现的次数。
3 */
4 @Test
5 public void practiceOne(){
6 //1.字符串
7 String str = "sdasvvvvwerkyuktyukyrwhergqerwgdcqwdcqwecxcasc";
8 //2.把字符串转换为数组
9 char[] charArray = str.toCharArray();
10 //3.创建一个Map
11 HashMap<Character, Integer> hashMap = new HashMap<>();
12 //4.遍历charArray
13 for (char c : charArray) {
14 if(!hashMap.containsKey(c)){
15 hashMap.put(c, 1);
16 } else {
17 hashMap.put(c, (hashMap.get(c) + 1));
18 }
19 }
20 //5.遍历hashMap
21 Set<Map.Entry<Character, Integer>> entrySet = hashMap.entrySet();
22 Iterator<Map.Entry<Character, Integer>> iterator = entrySet.iterator();
23 while (iterator.hasNext()) {
24 Map.Entry<Character, Integer> next = iterator.next();
25 Character key = next.getKey();
26 Integer value = next.getValue();
27 System.out.println(key + "=" + value);
28 }
29 }
练习二
A、B ⽤户订单列表 ⾥ ⾯的 交集(2 种 ⽅式)，差集(2 种 ⽅式)，并集，去重并集。
订单类
1package com.javase.demo;
2
3import lombok.AllArgsConstructor;
4import lombok.Data;
5
6import java.util.Objects;
7
8
9@AllArgsConstructor
10public class VideoOrder {
11 private String title;
12 private int price;
13
14 public String getTitle() {
15 return title;
16 }
17
18 public void setTitle(String title) {
19 this.title = title;
20 }
21
22 public int getPrice() {
23 return price;
24 }
25
26 public void setPrice(int price) {
27 this.price = price;
28 }
29
30 @Override
31 public boolean equals(Object o) {
32 if (this == o) return true;
33 if (o == null || getClass() != o.getClass()) return false;
34 VideoOrder that = (VideoOrder) o;
35 return price == that.price &&
36 title.equals(that.title);
37 }
38
39 @Override
40 public int hashCode() {
41 return Objects.hash(title, price);
42 }
43
44 @Override
45 public String toString() {
46 return "VideoOrder{" +
47 "title='" + title + '\'' +
48 ", price=" + price +
49 '}';
50 }
51}
测试类
1/**
2 * 练习二：A、B⽤户订单列表⾥⾯的 交集(2种⽅式)，差集(2种⽅式)，并集，去重并集
3 */
4 @Test
5 public void practiceTwo(){
6 ArrayList<VideoOrder> videoOrders1 = new ArrayList<>();
7 videoOrders1.add(new VideoOrder("葵花宝典", 20));
8 videoOrders1.add(new VideoOrder("九阳神功", 21));
9 videoOrders1.add(new VideoOrder("七伤拳", 22));
10
11 ArrayList<VideoOrder> videoOrders2 = new ArrayList<>();
12 videoOrders2.add(new VideoOrder("葵花宝典", 20));
13 videoOrders2.add(new VideoOrder("一阳指", 21));
14 videoOrders2.add(new VideoOrder("凌波微步", 22));
15
16 //交集：方式一
17 videoOrders1.retainAll(videoOrders2);
18 System.out.println(videoOrders1);//[VideoOrder{title='葵花宝典', price=20}]
19 //交集：方式二
20 ArrayList<VideoOrder> list = new ArrayList<>();
21 for (VideoOrder videoOrder : videoOrders1) {
22 if (videoOrders2.contains(videoOrder)) {
23 list.add(videoOrder);
24 }
25 }
26 System.out.println(list);//[VideoOrder{title='葵花宝典', price=20}]
27
28
29 //差集：方式一
30 //videoOrders1.removeAll(videoOrders2);
31 System.out.println(videoOrders1);//[VideoOrder{title='九阳神功', price=21}, VideoOrder{title='七伤拳', price=22}]
32 //差集：方式二
33 ArrayList<VideoOrder> difflist = new ArrayList<>();
34 for (VideoOrder videoOrder : videoOrders1) {
35 if (!videoOrders2.contains(videoOrder)) {
36 difflist.add(videoOrder);
37 }
38 }
39 System.out.println(difflist);//[VideoOrder{title='九阳神功', price=21}, VideoOrder{title='七伤拳', price=22}]
40
41 //并集
42 videoOrders1.addAll(videoOrders2);
43 System.out.println(videoOrders1);//[VideoOrder{title='葵花宝典', price=20}, VideoOrder{title='九阳神功', price=21}, VideoOrder{title='七伤拳', price=22}, VideoOrder{title='葵花宝典', price=20}, VideoOrder{title='一阳指', price=21}, VideoOrder{title='凌波微步', price=22}]
44
45 //去重并集
46 videoOrders1.addAll(videoOrders2);
47 Set<VideoOrder> set = new HashSet<>(videoOrders1);
48 System.out.println(set);//[VideoOrder{title='一阳指', price=21}, VideoOrder{title='葵花宝典', price=20}, VideoOrder{title='凌波微步', price=22}, VideoOrder{title='七伤拳', price=22}, VideoOrder{title='九阳神功', price=21}]
49
50 }