Java 哈希数据结构与经典用法

哈希的本质是用空间换时间，把查找从 O(n) 降到 O(1) 平均。

HashSet

存不存在 / 去重，用于判断某元素是否出现过、数组去重、集合交集

Set<Integer> set = new HashSet<>();
set.add(3); // 添加元素
set.add(3); // 重复元素不会加入
set.contains(3); // 判断是否存在
set.remove(3); // 删除元素

典型题：两数之和、数组去重、判断重复元素、两数组交集

HashMap

计数 / 映射，用于字符统计、频率统计、值到索引映射

Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
    // 如果 n 不存在，默认返回 0，然后 +1
    map.put(n, map.getOrDefault(n, 0) + 1);
}

两个 Integer 代表泛型，指 key 和 value 都是整数。map.put(n, map.getOrDefault(n, 0) + 1) 是哈希计数的经典写法，意思是给 n 做出现次数统计。map.getOrDefault(n, 0) 去 map 里取 n 的值，如果 n 不存在，就返回默认值 0。因为我们要统计出现次数，每遇到一次就加 1。map.put(n, ...) 代表把更新后的次数放回 map 里，如果 n 原来不存在，会自动创建。

典型题：字母异位词、出现次数最多的元素、前缀和 + 哈希、两数之和

TreeMap / TreeSet

有序哈希，用于需要自动排序、范围查询

Set<Integer> set = new TreeSet<>();
Map<Integer, Integer> map = new TreeMap<>();

基本用法：

TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(3);
set.add(8);
set.add(3); // 重复元素不会加入
System.out.println(set); // [3, 5, 8] 自动升序

TreeMap<Integer, String> map = new <>();
map.put(, );
map.put(, );
map.put(, );
map.put(, ); 
System.out.println(map);