Java Collection 体系

概述

java.util.Collection => public interface Collection<E> extends Iterable<E>

Collection Framework Hierarchy in Java

java.util.Collection

• java.util.Set => public interface Set<E> extends Collection<E>
• java.util.List => public interface List<E> extends Collection<E>
• java.util.ArrayList => public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  ArrayList
• java.util.LinkedList => public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  LinkedList
• java.util.AbstractCollection => public abstract class AbstractCollection<E> implements Collection<E>
• java.util.SortedSet => public interface SortedSet<E> extends Set<E>
  SortedSet
• java.util.HashSet => public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable
  HashSet
• java.util.TreeSet => public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
  TreeSet

构造

• new ArrayList<>() | new ArrayList<>(Collection)

常用方法

• size() | isEmpty() | contains()
• add() | allAll() | retainAll()
• clear() | remove() | removeAll()

java.util.List

本质就是一个数组 => 有序

java.util.ArrayList

ArrayList Diagrams

ArrayList 动态扩容

动态扩容的实现 => 创建一个更大的空间，然后把原先的所有元素拷贝过去 => ArrayList add 方法中的 ensureCapacityInternal

java.util.Set

无序 & 不允许有重复元素
判断重复 => equals 方法

Set

java.util.HashSet

最常用、最高效的 Set 实现 & 无序

HashSet Diagrams

java.util.LinkedHashSet

顺序和插入的时候相同

LinkedHashSet Diagrams

java.util.TreeSet

有序 => 使用 Comparable 约定，认为排序相等的元素相等 => 可用于排序
内部结构 => 红黑树 => 一种二叉树

TreeSet Diagrams

java.util.Collections

约定：接口 | 类 的工具方法在相应的 s 类中**

• Interface Collection -> class Collections
• Interface Set -> class Sets

方法 TODO

• emptySet() | emptyMap() | emptyList() 等 => 返回一个方便的空集合
• synchronizedCollection() => 将一个集合变成线程安全的
• unmodifiableCollection() => 将一个集合变成不可变的

Collection 其他实现

• Queue | Deque => 队列：LILO => Last In Last Out
• LinkedList => 链表
• ConcurrentHashMap
• PriorityQueue

java.util.Map

An object that maps keys to values. A map connot contain duplicate keys; each key can map to at most one value

• java.util.HashMap => public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable
  HashMap
• java.util.TreeMap => public class TreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V>, Cloneable, java.io.Serializable
  TreeMap
• java.util.SortedMap => public interface SortedMap<K, V> extends Map<K, V>
  SortedMap

常用方法

• put() | putAll()
• get() | size()
• remove() | clear()
• containsKey() | containsValue()
• Set<K> keySet() | Collection<V> values() | Set<Map.Entry<K, V>> entrySet() => 三个方法的返回值与 Map 中的 key | value 是同一组数据，更改其一，另外一个会立刻更改

java.util.HashMap

最常用、最高效的 Map 实现

HashMap Diagrams

HashMap 的扩容

同 ArrayList 扩容 => 创建一个更大的空间，然后把原先的所有元素拷贝过去 => HashMap 中的 put() -> putVal() -> resize()

HashMap 线程不安全性

Note that this implementation is not synchronized.
HashMap 在扩容时，如果有多线程同时访问，resize 有可能变成一个死循环的链表 => 在多线程的时候使用 ConcurrentHashMap

HashMap 在 Java 7+ 后的改变：链表 -> 红黑树

HashMap 在处理同一个 Hash 桶里面的碰撞的情况时，把链表变成红黑树，以提高性能

java.util.TreeMap

TreeMap Diagrams

java.util.HashSet vs java.util.HashMap

HashSet 源码

HashSet 就是一个 HashMap，HashSet 的构造函数都是 new HashMap，HashSet 的所有 value 都是第10行的 PRESENT。HashMap 是从 key 到 value 的映射，其中 key 是不能重复的，那么 HashMap 中的 key 的集合就是一个 HashSet，HashSet 重用了 HashMap 的逻辑。当 HashSet 中丢入一个元素，实际上是将元素作为 key，第10行的 PRESENT 作为 value 丢入到 HashMap 中

Guava

不要重复造轮子！尽量使用经过实战检验的类库！

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>30.1.1-jre</version>
</dependency>

常用工具类

• Lists | Sets | Maps
• ImmutableMap | ImmutableSet => 不可变
• MultiSet | MultiMap => MultiSet 存放唯一的元素 + 这个唯一的元素出现的次数
• BiMap => 双向 Map

知识点

1. 清除 list 中的重复元素 => Set<Integer> set = new HashSet<>(list);
2. 哈希就是单向的映射
3. hashCode 约定 // TODO
   • 同一个对象必须始终返回相同的 hashCode
   • 两个对象的 equals 返回 true，必须返回相同的 hashCode
   • 两个对象不等，也可能返回相同的 hashCode