中级03 - Collection体系简介

没有 Collection，Java 只能算是玩具。

List
Set
hashCode约定
Map

一、Collection 体系

参考1

参考2

Collection 的体系

Collection的体系结构
List/Set约定

Collection 体系提供的常⽤⽅法：

new: new ArrayList(Collection), new ArrayList()
Read: size()/isEmpty()/contains()/for()/stream()
Cread/Update: add()/addAll()/retainAll()
Delete: clear()/remove()/removeAll()

retainAll()求交集
removeAll()求差集

1. List

有序可重复，最常用的是 ArrayList，本质上就是一个数组

Collection<Integer> c = new LinkedHashSet<>();
        
// IntegerList
List<Integer> list = new ArrayList<>(c);
        
// 等价于
List<Integer> list2 = new ArrayList<>();
list2.addAll(c);
        
// 等价于
List<Integer> list3 = new ArrayList<>();
for (Integer i : c) {
    list3.add(i);
}

add() 方法内部实现了数组的动态扩容：创建一个更大的空间，然后把原先的所有元素拷贝进去。

2. Set

无序且不可重复的元素集合。

只是简单通过object.contains()判断添加新元素时是否重复，从而实现去重的 Set 是很低效的，这就引出了对象的 hashcode。

Java世界⾥第⼆重要的约定：hashCode

同⼀个对象必须始终返回相同的 hashCode
两个对象的 equals 返回 true，必须返回相同的 hashCode
两个对象不等，也可能返回相同的 hashCode

3. 哈希算法

哈希就是⼀个单向、一对多的映射，具有相同 hashCode 的东西存放在同一个 hash 桶中，
例⼦：从姓名到姓到哈希运算
从任意对象到⼀个整数（int）的 hashCode

4. HashSet

HashSet 是无序的，是最常用的 Set 实现。
可以利用 set 为 list 过滤去重：

List<Integer> list = new ArrayList<>();

list.add(2);
list.add(3);
list.add(3);
list.add(3);
        
Set<Integer> set = new HashSet<>(list);

LinkedHashSet 是有序的，其维护了一个双向（doubly-linked）链表，顺序就是插入元素时的顺序。

5. Collections ⼯具⽅法集合

emptySet()：返回一个方便的空集合
synchronizedCollection：将⼀个集合变成线程安全的
unmodifiableCollection：将⼀个集合变成不可变的（也可以
使⽤ Guava 的 Immutable）
unmodifiableSet()：可以获取不可变的 set，System.getenv() 内部就使用了这个方法将环境变量转换为不可变的 set。

6. Collection的其他实现

Queue/Deque
Vector/Stack（已废弃，现用 ArrayList/Deque）
LinkedList
ConcurrentHashMap
PriorityQueue

二、Map 体系

map 是一个将 keys 映射到 values 的对象，键不能重复，每个键只能映射一个值，值可以重复。

Create/Update: put()/putAll()

Read:

get()/size()
containsKey()/containsValue()
keySet()/values()/entrySet()

Delete: remove()/clear()

image.png

keySet()返回键的集合，因为键不可重复，所以可以返回一个 set；
values()返回值的集合，因为值可以重复，所以返回的是 collection。
注意：keySet() 和 map 背后的 keys 是同一组数据，所以二者的修改会相互影响。

entrySet()返回键值对的集合（Set<Map.Entry<K, V>>），遍历时很有用：

Map<String, String> map = new HashMap<>();

for (Map.Entry<String, String> entry: map.entrySet()) {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

1. HashMap

HashMap 是最常用、最高效的 Map 实现。

HashMap 的扩容，思路同样是创建更大的空间，然后把之前的数据 copy 进来。

HashMap 是多线程不安全的，可使用 ConcurrentHashMap。

HashMap在Java 7+后的改变（链表 --> 红⿊树）：
因为 hashCode 是可能重复的（即发生碰撞），极端情况下如果一组数据的 hashCode 全部相同，那么会全放在同一个 hash 桶中成为了一个 List 链表，此时就丧失了 hash 桶的好处，性能会急剧恶化，所以 Java 7 开始会采用红黑树来代替链表。

HashMap 和 HashSet 本质上是同一个东西：
HashMap 的 key 集合（set）就是 HashSet，而 HashSet 内部其实就是个 HashMap，毕竟 HashSet 拥有的功能 HashMap 都有。

2. 有序集合TreeSet/TreeMap

TreeSet 可以排序（默认是自然顺序）。
HashSet、LinkedHashSet 与 TreeSet 对比：

import java.util.*;

public class Main {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1000, -13, 0, -41656, 1250, 555);

        Set set1 = new HashSet<>(list);
        Set set2= new LinkedHashSet(list);
        Set set3 = new TreeSet(list);

        System.out.println(set1);
        System.out.println(set2);
        System.out.println(set3);
    }
}

[0, 1250, -41656, 1000, 555, -13]
[1000, -13, 0, -41656, 1250, 555]
[-41656, -13, 0, 555, 1000, 1250]

TreeMap 同理。
它们使⽤ Comparable 约定，认为排序相等的元素相等。

三、Guava

Google 开源的 Guava 提供了 JDK 没有的额外方法，不要重复发明轮⼦，尽量使⽤经过实战检验的类库。

Lists/Sets/Maps
ImmutableMap/ImmutableSet
Multiset/Multimap
BiMap