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
//初始化容器
ArrayList<String> arrayList = new ArrayList<>(5);
LinkedList<String> linkedList = new LinkedList<>();
//添加对象
arrayList.add("Howard");
arrayList.add("tom");
arrayList.add("alice");
//输出
System.out.println(arrayList);//[Howard, tom, alice]
//通过指定index获取元素
arrayList.get(0);
//更新元素
arrayList.set(1, "tomcat");
//返回集合容器中已存储对象的数量
arrayList.size();
//根据指定索引删除元素 返回删除的对象
arrayList.remove(1);
//根据对象删除元素 删除成功返回true
arrayList.remove("alice");
//清空容器
arrayList.clear();
//是否为空
arrayList.isEmpty();
}
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 接口，能够对集合中的对象进行排序。
public void setTesting(){
//初始化容器
HashSet<String> hashSet = new HashSet<>();
//添加对象
hashSet.add("jack");
//返回容器大小
hashSet.size();
//根据对象删除元素
hashSet.remove("jack");
//是否为空
hashSet.isEmpty();
//清空元素
hashSet.clear();
}
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
public void mapTesting(){
//初始化容器
HashMap<String, String> hashMap = new HashMap<>();
TreeMap<String, String> treeMap = new TreeMap<>();
//容器添加对象
hashMap.put("小张", "男");
hashMap.put("小王", "男");
//判断是否包含某个key
hashMap.containsKey("小张");
//根据key获取value
hashMap.get("小张");
//返回map的元素数量
hashMap.size();
//清空容器
hashMap.clear();
//获取所有value的集合
Collection<String> collection = hashMap.values();
//返回所有的key的集合
Set<String> set = hashMap.keySet();
//返回⼀个Set集合，集合的类型为Map.Entry , 是Map声明的⼀个内部接⼝，接⼝为泛型，定义为Entry<K,V>，
//它表示Map中的⼀个实体(⼀个key-value对),主要有getKey(),getValue⽅法
Set<Map.Entry<String, String>> entrySet = hashMap.entrySet();
for (Map.Entry<String, String> entry : entrySet) {
System.out.println(entry.getKey()); //小王
System.out.println(entry.getValue()); //男
}
//判断map是否为空
hashMap.isEmpty();
}
jdk1.7 和 jdk1.8 中 HashMap 的主要区别
底层实现由之前的 “数组 + 链表” 改为 “数组 + 链表 + 红 ⿊树”。
什么时候开始转变
当链表节点较少时仍然是以链表存在，当链表节点较多时，默认是 ⼤于 8 时会转为红黑树。
static final int TREEIFY_THRESHOLD = 8;
练习一
统计每个字符出现的次数。
/**
* 练习一：统计每个字符出现的次数。
*/
@Test
public void practiceOne(){
//1.字符串
String str = "sdasvvvvwerkyuktyukyrwhergqerwgdcqwdcqwecxcasc";
//2.把字符串转换为数组
char[] charArray = str.toCharArray();
//3.创建一个Map
HashMap<Character, Integer> hashMap = new HashMap<>();
//4.遍历charArray
for (char c : charArray) {
if(!hashMap.containsKey(c)){
hashMap.put(c, 1);
} else {
hashMap.put(c, (hashMap.get(c) + 1));
}
}
//5.遍历hashMap
Set<Map.Entry<Character, Integer>> entrySet = hashMap.entrySet();
Iterator<Map.Entry<Character, Integer>> iterator = entrySet.iterator();
while (iterator.hasNext()) {
Map.Entry<Character, Integer> next = iterator.next();
Character key = next.getKey();
Integer value = next.getValue();
System.out.println(key + "=" + value);
}
}
练习二
A、B⽤户订单列表 ⾥ ⾯的 交集(2 种 ⽅式)，差集(2 种 ⽅式)，并集，去重并集。
订单类
package com.javase.demo;
import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.Objects;
@AllArgsConstructor
public class VideoOrder {
private String title;
private int price;
public String getTitle() {
return title;
}
public void setTitle(String title) {
this.title = title;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
VideoOrder that = (VideoOrder) o;
return price == that.price &&
title.equals(that.title);
}
@Override
public int hashCode() {
return Objects.hash(title, price);
}
@Override
public String toString() {
return "VideoOrder{" +
"title='" + title + '\'' +
", price=" + price +
'}';
}
}
测试类
/**
* 练习二：A、B⽤户订单列表⾥⾯的 交集(2种⽅式)，差集(2种⽅式)，并集，去重并集
*/
@Test
public void practiceTwo(){
ArrayList<VideoOrder> videoOrders1 = new ArrayList<>();
videoOrders1.add(new VideoOrder("葵花宝典", 20));
videoOrders1.add(new VideoOrder("九阳神功", 21));
videoOrders1.add(new VideoOrder("七伤拳", 22));
ArrayList<VideoOrder> videoOrders2 = new ArrayList<>();
videoOrders2.add(new VideoOrder("葵花宝典", 20));
videoOrders2.add(new VideoOrder("一阳指", 21));
videoOrders2.add(new VideoOrder("凌波微步", 22));
//交集：方式一
videoOrders1.retainAll(videoOrders2);
System.out.println(videoOrders1);//[VideoOrder{title='葵花宝典', price=20}]
//交集：方式二
ArrayList<VideoOrder> list = new ArrayList<>();
for (VideoOrder videoOrder : videoOrders1) {
if (videoOrders2.contains(videoOrder)) {
list.add(videoOrder);
}
}
System.out.println(list);//[VideoOrder{title='葵花宝典', price=20}]
//差集：方式一
//videoOrders1.removeAll(videoOrders2);
System.out.println(videoOrders1);//[VideoOrder{title='九阳神功', price=21}, VideoOrder{title='七伤拳', price=22}]
//差集：方式二
ArrayList<VideoOrder> difflist = new ArrayList<>();
for (VideoOrder videoOrder : videoOrders1) {
if (!videoOrders2.contains(videoOrder)) {
difflist.add(videoOrder);
}
}
System.out.println(difflist);//[VideoOrder{title='九阳神功', price=21}, VideoOrder{title='七伤拳', price=22}]
//并集
videoOrders1.addAll(videoOrders2);
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}]
//去重并集
videoOrders1.addAll(videoOrders2);
Set<VideoOrder> set = new HashSet<>(videoOrders1);
System.out.println(set);//[VideoOrder{title='一阳指', price=21}, VideoOrder{title='葵花宝典', price=20}, VideoOrder{title='凌波微步', price=22}, VideoOrder{title='七伤拳', price=22}, VideoOrder{title='九阳神功', price=21}]
}