• 一、基本概念

  HashSet

• 定义：只存储值（元素）的集合
• 特点：不允许重复元素，无序
• 底层实现：基于 HashMap 实现

• HashMap

• 定义：存储键值对（key-value）的映射
• 特点：key 不允许重复，value 可以重复
• 底层实现：数组 + 链表/红黑树

二、常用操作

HashSet 常用方法

Set<String> set = new HashSet<>();
set.add("apple");           // 添加元素
set.contains("apple");      // 判断是否存在
set.remove("apple");        // 删除元素
set.size();                 // 获取大小
set.isEmpty();              // 判断是否为空
set.clear();                // 清空

HashMap 常用方法

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);        // 添加/更新
map.get("apple");           // 获取值
map.containsKey("apple");   // 判断key是否存在
map.remove("apple");        // 删除
map.size();                 // 获取大小
map.keySet();               // 获取所有key
map.values();               // 获取所有value
map.entrySet();             // 获取所有键值对

三、时间复杂度

HashSet

• 添加/查找/删除：O(1) 平均，O(n) 最坏

HashMap

• 添加/查找/删除：O(1) 平均，O(n) 最坏

---

四、使用场景

HashSet 适用场景

• 去重：去除重复元素

• 快速查找：判断元素是否存在

• 记录访问过的节点：如检测链表环

HashMap 适用场景

• 计数：统计元素出现次数

• 缓存：key-value 缓存

• 索引：快速根据 key 查找 value

• 两数之和：快速查找目标值

---

五、实际应用示例

HashSet 示例

//去重
Set<Integer>set=new HashSet<>();
for(int num:arr){
    set.add(num); //自动去重
}
//检测链表环
Set<ListNode>visited =new HashSet<>();
while(node!=null){
    if(visited.contains(node)){
        return true; 
}
    visited.add(node);
    node=node.next;
}

HashMap 示例

//计数
Map<String,Integer> count=new HashMap();
for(String word:words){
    count.put(word,getOrDefault(word,0)+1);
}

关键方法：

• count.getOrDefault(word, 0)：获取 word 对应的值，不存在返回 0

• count.put(word, newCount)：存入或更新 word 的计数

执行过程：

words = ["apple", "banana", "apple"]

第1次：apple
  getOrDefault("apple", 0) = 0（不存在）
  put("apple", 0 + 1) → count = {apple=1}

第2次：banana
  getOrDefault("banana", 0) = 0
  put("banana", 0 + 1) → count = {apple=1, banana=1}

第3次：apple
  getOrDefault("apple", 0) = 1（已存在）
  put("apple", 1 + 1) → count = {apple=2, banana=1}

public int[] towSum(int[]nums,int target){
    Map<Integer,Integer>map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
        int need=target-nums[i];
    }
    if(map.containKey(need)){
        int index1=map.get(need); //之前遇到的数的索引
        int index2=i;            //当前数的索引
        int [] result=new int[2];
        result[0]=index1;
        result[1]=index2;
        return result;
    }
    //没找到，把当前数和索引存入map
    map.put(nums[i],i);        

}

六、注意事项

1. equals 和 hashCode：自定义类作为 key 或元素时，必须重写

1. null 值：都允许一个 null 值

1. 线程安全：都不是线程安全的

1. 初始容量：默认 16，负载因子 0.75

1. 遍历顺序：不保证顺序

---

七、总结对比表

特性	HashSet	HashMap
存储内容	值（元素）	键值对
重复性	不允许重复	key 不允许重复
时间复杂度	O(1) 平均	O(1) 平均
主要用途	去重、查找	映射、计数
常用方法	add, contains, remove	put, get, containsKey