1、Map 体系

Map：存储记录（K-V 键值对），无序无下标，Key 具有唯一性。

• 体系图

  

• API

  	JDK	线程安全	存储结构	说明
  HashMap	1.2	线程不安全	数组+链表、红黑树	K 或 V 可以为 null
  Hashtable	1.0	线程安全	数组+链表	K 或 V 不允许为 null，很少使用
  Properties	1.0	线程安全	数组+链表	继承 Hashtable。 K 和 V 都是 String，通常用于读取配置文件
  TreeMap	1.2	线程不安全	红黑树	自动对 K 排序。 前提：K 实现 Comparable 接口

2、Map 接口

Map 体系的父接口

强调几个方法

• put()：添加元素，key 重复则覆盖原值。

• keySet()：返回一个包含所有 key 值的 Set 集合。

• entrySet()：返回一个包含所有记录的 Set 集合。

  

3、HashMap（❗）

3.1、使用

定义一个 User 类：name、age

• 增、删

  User u1 = new User("Jaywee", 17);
  User u2 = new User("Baby", 10);
  
  HashMap<User, String> hashMap = new HashMap<>();
  
  // 添加
  hashMap.put(u1, "北京");
  hashMap.put(u2, "上海");
  // key相同，覆盖原有元素，相当于replace()
  hashMap.put(u2, "广州");
  
  // 删除
  hashMap.remove(u1);
  

• 遍历

  System.out.println("========= KeySet =========");
  Set<User> keySet = hashMap.keySet();
  for (User user : keySet) {
      System.out.println(user);
  }
  
  System.out.println("======== EntrySet ========");
  Set<Map.Entry<User, String>> entrySet = hashMap.entrySet();
  for (Map.Entry<User, String> entry : entrySet) {
      System.out.println(entry.getKey() + ": " + entry.getValue());
  }
  

• 判断

  hashMap.containsKey(u1);
  hashMap.containsKey(new User("Jaywee", 17));
  

3.2、存储机制（❗）

（与 HashSet 相同，可以回顾 Collection 体系 一文的 HashSet）

注意：HashMap 中的每个数组元素，称为位桶

• 存储结构：数组+链表，红黑树
• 树化条件：桶的容量达到树化阈值，数组容量达到最小树化容量。
• 相等条件：hashCode 相等且 equals() 为 true，则相等。
  • 通过 hashCode() 计算位置（要放在哪个位桶）
  • 通过 equals() 判断相等（位桶的链表是否有重复元素）

因此，使用 HashMap 时，需要重写 hashCode() 和 equals() 方法。

3.3、源码分析

HashMap 源码分析

3.4、回顾 HashSet

看看 HashSet 的源码结构。

• map：HashSet 的存储结构，就是 HashMap

  • Key：向 HashSet 添加的元素，作为 HashMap 的 Key。
  • Value：用一个无意义的 PRESENT，作为 HashMap 的 value。

• PRESENT：无意义的变量

  public class HashSet<E>
      extends AbstractSet<E>
      implements Set<E>, Cloneable, java.io.Serializable {
      private transient HashMap<E,Object> map;
      private static final Object PRESENT = new Object();
  
      public HashSet() {
          map = new HashMap<>();
      }
  
      public boolean add(E e) {
          return map.put(e, PRESENT)==null;
      }
  }
  

4、Hashtable

已很少使用，了解即可。

• 默认初始容量 11，默认加载因子 0.75f
• Properties 子类：要求 Key 和 Value 都是 String，常用于读取配置文件。

5、TreeMap

5.1、使用

定义一个 Employee 类

演示 TreeMap 的增删、遍历、判断，以及元素排序。

Employee 必须实现 Comparable 接口，否则报错。

（或者在创建 TreeMap 时，以匿名内部类形式创建 Comparator）

public class Employee implements Comparable<Employee> {
    private String name;
    private int salary;

    // 构造方法、toString()
    
    @Override
    public int compareTo(Employee o) {
        return salary - o.salary;
    }
}

5.2、存储机制

• 存储结构：红黑树
• 相等条件：compareTo() 返回 0
  • 与 equals() 和 hashCode() 无关
  • 元素对象需实现 Comparable 接口，或声明 TreeMap 时定义匿名内部类 Comparator。

5.3、回顾 TreeSet

了解完 TreeMap，来看看 TreeSet 的源码结构。

（类似 HashSet 与 HashMap 的关系）

m：TreeSet 的存储结构，NavigableMap 是 HashMap 的接口之一

• Key：向 TreeSet 中添加的元素，作为 TreeMap 的 Key

• Value：无意义的 PRESENT，作为 TreeMap 的 value

  public class TreeSet<E> extends AbstractSet<E>
      implements NavigableSet<E>, Cloneable,java.io.Serializable {
      private transient NavigableMap<E,Object> m;
      private static final Object PRESENT = new Object();
  
      public TreeSet() {
          this(new TreeMap<E,Object>());
      }
      
      public boolean add(E e) {
          return m.put(e, PRESENT)==null;
      }
  }
  

6、Collections工具类

数组有一个 Arrays 工具类，集合也有一个 Collections 工具类。

• 二分查找
• 反转：reverse()
• 随机：shuffle()
• 交换元素位置：swap()
• 排序：升序
• 同步化：将线程不安全的集合包装为线程安全（synchronizedCollection、synchronizedSet 等）
• ...