简要总结 HashSet 和 HashMap（Java）

• 一、基本概念

  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. 遍历顺序：不保证顺序

七、总结对比表