Map

TreeMap、HashMap、LinkedHashMap、Hashtable、WeakHashMap

概述：

• Map 存储键值对，键不可重复
• Map 下有 SortedMap 接口、AbsractMap 抽象类
• Map 接口提供的通用方法
  • get(Object key)：返回给定键的值
  • getOrDefault(Object key, V defaultValue)：返回给定键的值，若键不存在，则返回默认值
  • put(K key, V value)：将指定值与指定键关联，若键不存在，则添加键值对
  • putAll(Map<? extends K,? extends V> map)：将多个键值对关联
  • remove(Object key)：删除键值对
  • clear()：删除所有键值对
  • containsKey(Object key)：判断是否包括给定键
  • containsValue(Object value)：如果一个或多个键被映射到给定值，则返回 true
  • replace(K key, V oldValue, V newValue)：当给定键映射到给定值时，替换值
  • size()：返回键值对总数
  • isEmpty()：判断是否为空
  • equals(Object o)：判断是否与给定对象相等

TreeMap：

• TreeMap 存储有序的键值对

• 数组 + 红黑树，不是线程安全的

• 初始化并自定义排序规则

  TreeMap<K, V> map = new TreeMap<>(
      new Comparator<K>() {
          @Override
          public int compare(K a, K b) {  // 若 a 应排在 b 前则返回负数
              return b - a;  // 降序排序
              // return a - b;  // 升序排序
          }
      }
  );
  

  • 初始化 TreeMap 时调用构造方法 public TreeMap(Comparator<? super E> comparator)
  • 构造方法的输入参数是 Comparator 比较器，其中 Comparator 是接口
  • 通过匿名类实现接口并重写 compare 方法 (菜鸟教程：Java 匿名类)

• 遍历方法

  for (Map.Entry<K, V> entry : map.entrySet()) {
  	entry.getKey();
      entry.getValue();
      entry.setValue();
      ...
  }
  

• 常用方法

  • ceilingEntry(K key)、ceilingKey(K key)：返回大于等于给定键的键值对 / 键，若无则返回 null
  • floorEntry(K key)、floorKey(K key)：返回小于等于给定键的键值对 / 键，若无则返回 null
  • higherEntry(K key)、higherKey(K key)：返回严格大于给定键的键值对 / 键，若无则返回 null
  • lowerEntry(K key)、lowerKey(K key)：返回严格小于给定键的键值对 / 键，若无则返回 null
  • firstEntry()、firstKey()：返回第一个键值对 / 键
  • lastEntry()、lastKey()：返回最后一个键值对 / 键
  • pollFirstEntry()、pollLastEntry()：返回并删除第一个 / 最后一个键值对
  • headMap(K toKey, boolean inclusive)：返回小于给定键的键值对的集合
  • tailMap(K fromKey, boolean inclusive)：返回大于给定键的键值对的集合
  • subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)：返回给定区间的键值对的集合
  • descendingMap()：返回逆序的键值对映射

HashMap：

• HashMap 存储无序的键值对，遍历时不保证顺序
• 数组 + 链表 + 红黑树，不是线程安全的
• 初始化 HashMap<K, V> map = new HashMap<>();

LinkedHashMap：

• LinkedHashMap 存储无序的键值对，在 HashMap 的基础上添加双向链表，可按插入 / 访问顺序遍历

• 数组 + 双向链表 + 红黑树，不是线程安全的

• 初始化 LinkedHashMap<K, V> map = new LinkedHashMap<>(int initialCapacity, float loadFactor, boolean accessOrder);

  • initialCapacity 是初始数组长度，默认 16
  • loadFactor 是负载因子，当键值对数量与数组长度之比超过负载因子时需要扩容，默认 0.75f
  • accessOrder 是遍历顺序，false 基于插入顺序 (默认)，true 基于访问顺序

• 常用方法

  • removeEldestEntry(Map.Entry<K,V> eldest)：在插入键值对后，调用 removeEldestEntry 判断是否需要删除最旧键值对；removeEldestEntry 永远返回 false，即永远扩容数组而不删除键值对，可根据需求重写该方法

• 初始化并重写 removeEldestEntry

  LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<Integer, Integer>(capacity, 1f, true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
          return size() > capacity;
      }
  };
  

Hashtable：

• Hashtable 存储无序的键值对
• 数组 + 链表，是线程安全的 (与 HashMap 的不同点)
• 性能差，被淘汰

WeakHashMap：

• 待补充

Collection

概述：

• Collection 存储元素本身
• Collection 下有 Set 接口、List 接口、Queue 接口
• Collection 接口提供的通用方法
  • add(E e)：添加元素
  • addAll(Collection<? extends E> c)：添加多个元素
  • remove(Object o)：删除元素
  • removeAll(Collection<?> c)：删除多个元素
  • clear()：删除所有元素
  • contains(Object o)：判断是否包括给定元素
  • containsAll(Collection<?> c)：判断是否包括给定的多个元素
  • size()：返回元素总数
  • isEmpty()：判断是否为空
  • equals(Object o)：判断是否与给定对象相等
  • toArray()：转换成数组

Set

概述：

• Set 存储不重复元素的集合
• Set 下有 SortedSet 接口、AbsractSet 抽象类

TreeSet：

• TreeSet 存储有序的不重复元素的集合

• 数组 + 红黑树，不是线程安全的

• 初始化并自定义排序规则

  TreeSet<E> set = new TreeSet<>(
      new Comparator<E>() {
          @Override
          public int compare(E a, E b) {  // 若 a 应排在 b 前则返回负数
              return b - a;  // 降序排序
              // return a - b;  // 升序排序
          }
      }
  );
  

• 常用方法

  • ceiling(E e)：返回大于等于给定元素的元素，若无则返回 null
  • floor(E e)：返回小于等于给定元素的元素，若无则返回 null
  • higher(E e)：返回严格大于给定元素的元素，若无则返回 null
  • lower(E e)：返回严格小于给定元素的元素，若无则返回 null
  • first()：返回第一个元素
  • last()：返回最后一个元素
  • pollFirst()：返回并删除第一个元素
  • pollLast()：返回并删除最后一个元素
  • headSet(E toElement, boolean inclusive)：返回小于给定元素的元素的集合
  • tailSet(E fromElement, boolean inclusive)：返回大于给定元素的元素的集合
  • subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)：返回给定区间的元素的集合
  • descendingSet()：返回逆序的元素的集合

HashSet：

• HashSet 存储无序的不重复元素的集合，遍历时不保证顺序
• 数组 + 链表 + 红黑树 (采用 HashMap 实现)，不是线程安全的
• 初始化 HashSet<E> set = new HashSet<>();

LinkedHashSet：

• LinkedHashSet 存储无序的不重复元素的集合，在 HashSet 的基础上添加双向链表，可按插入顺序遍历 (不能按访问顺序遍历)
• 数组 + 双向链表 + 红黑树 (采用 LinkedHashMap 实现)，不是线程安全的
• 初始化 LinkedHashSet<E> set = new LinkedHashSet<>();

List

概述：

• List 存储可重复元素的列表
• List 下有 AbstractList 接口
• List 接口提供的通用方法
  • add(int index, E element)：在给定位置插入元素 (插入后 get(index) 得到的即是该元素)
  • get(int index)：返回给定位置的元素
  • set(int index, E element)：修改给定位置的元素
  • indexOf(Object o)：返回第一次出现给定元素的索引
  • lastIndexOf(Object o)：返回最后一次出现给定元素的索引
  • subList(int fromIndex, int toIndex)：返回给定区间的元素的集合

ArrayList：

• ArrayList 存储可重复元素的列表，查找快、增删慢
• 数组，不是线程安全的
• 初始化 ArrayList<E> list = new ArrayList<>();

LinkedList：

• LinkedList 存储可重复元素的列表，查找慢、增删快
• 双向链表，不是线程安全的
• 初始化 LinkedList<E> list = new LinkedList<>();
• 常用方法
  • addFirst(E e)、offerFirst(E e)：在头部插入元素
  • addLast(E e)、offerLast(E e)、add(E e)、offer(E e)、push(E e)：在尾部插入元素
  • getFirst()、peekFirst()、element()、peek()：返回第一个元素
  • getLast()、peekLast()：返回最后一个元素
  • pollFirst()、removeFirst()、poll()：返回并删除第一个元素
  • pollLast()、removeLast()、pop()：返回并删除最后一个元素
  • removeFirstOccurrence(Object o)：删除第一次出现的给定元素
  • removeLastOccurrence(Object o)：删除最后一次出现的给定元素
  • 说明
    • 栈相关操作：push、pop
    • 队列相关操作：offer、peek、poll (LinkedList 实现了 Deque 接口)

Vector：

• 数组，是线程安全的
• 性能差，被淘汰

Stack：

• 数组，是线程安全的
• 性能差，被淘汰

Queue

概述：

• Queue 存储可重复元素的队列，只能在队头队尾操作

• Queue 下有 Deque 接口 (双端队列)、AbstractQueue 抽象类 (单向队列)

• Queue 接口提供的两套增删查方法

  • add、remove、get：方法失败时抛出异常
  • offer、poll、peek：方法失败时返回默认值 false 或 null

• Deque 接口在 Queue 接口的两套增删方法上添加了 First 和 Last 的后缀

  • addFirst、addLast ...
  • offerFirst、offerLast ...
  • 此外 Deque 接口中有模仿栈的 push 和 pop 方法

ArrayDeque：

• ArrayDeque 存储可重复元素的队列，只能在队头队尾操作，是双端队列
• 数组 (与 LinkedList 的不同点)，不是线程安全的
• 初始化 ArrayDeque<E> queue = new ArrayDeque<>();

PriorityQueue：

• PriorityQueue 存储可重复元素的队列，只能在队头队尾操作，保证元素按指定顺序排列

• 堆 (数组)，不是线程安全的

• 初始化初始化并自定义排序规则

  PriorityQueue<E> queue = new PriorityQueue<>(
      new Comparator<E>() {
          @Override
          public int compare(E a, E b) {  // 若 a 应排在 b 前则返回负数
              return b - a;  // 降序排序
              // return a - b;  // 升序排序
          }
      }
  );
  

工具

排序：

Arrays.sort()、Collections.sort()

• Arrays.sort(T[] a, Comparator<? super T> c) 针对基本数据类型和引用对象类型的数组排序

• Collections.sort(List<T> list, Comparator<? super T> c) 针对集合框架排序

• 当使用 Comparator 时，T 不能是 int，而应是 Integer，若要将 int 转换成 Integer 需要 \(O(n)\) 的遍历

• 自定义排序规则

  // 匿名类写法
  Integer [] nums = new Integer[] {1, 4, 5, 3, 2};
  Arrays.sort(nums, new Comparator<Integer>() {  // 若 a 应排在 b 前则返回负数
      @Override
      public int compare(Integer a, Integer b) {
          return a - b;  // 升序排序
          // return b - a;  // 降序排序
      }
  });
  
  // lambda 写法
  Integer [] nums = new Integer[] {1, 4, 5, 3, 2};
  Arrays.sort(nums, (a, b) -> a - b);
  // 或 Arrays.sort(nums, (Integer a, Integer b) -> { return a - b; });
  

遍历：

Iterator、Iterable、ListIterator

• Iterator 是供集合操作内部对象的迭代器，可以遍历、移除对象，只能单向移动

  • hasNext()：判断集合中是否存在下一个对象
  • next()：返回集合中的下一个对象，并将访问指针移动一位
  • remove()：删除集合中下次调用 next() 方法返回的对象

  List<Integer> list = new ArrayList<>();
  Iterator iter = list.iterator();
  while (iter.hasNext()) {
      Integer num = iter.next();
      System.out.println(num);
  }
  

• Iterable 是对 Iterator 的封装，在 JDK 1.8 时，实现了 Iterable 接口的集合可以使用增强 for 循环遍历集合对象

  List<Integer> list = new ArrayList<>();
  for (Integer num : list) {
      System.out.println(num);
  }
  

• ListIterator 继承 Iterator 接口，在遍历集合时可以从任意索引下标开始遍历，且支持双向遍历

  • hasNext()、next()、remove()
  • hasPrevious()、previous()
  • nextIndex()、previousIndex()
  • set(E e)：替换最近一次 next() 方法或 previous() 方法返回的对象
  • add(E e)：在最近一次 next() 方法或 previous() 方法返回的对象后添加元素

  List<Integer> list = new ArrayList<>();
  ListIterator<Integer> listIter1 = list.listIterator(); 
  ListIterator<Integer> listIter2 = list.listIterator(5); 
  

参考

• 菜鸟教程：Java 集合框架
• 菜鸟教程：Java 文档
• 廖雪峰：集合
• GitHub：超全 Java 集合框架讲解