我要评论哈希的本质是用空间换时间，把查找从 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不存在，就返回默认值0map是指数组）。因为我们要统计出现次数，每遇到一次就加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 treemap<>();
map.put(3, "c");
map.put(1, "a");
map.put(2, "b");
map.put(2, "bb"); // key=2 更新 value
system.out.println(map); // {1=a, 2=bb, 3=c} 自动按 key 排序linkedhashmap / linkedhashset
保序哈希，用于保持插入顺序 + 哈希效率
map<integer, integer> map = new linkedhashmap<>(); set<integer> set = new linkedhashset<>();
基本用法：
set<integer> set = new linkedhashset<>();
set.add(3);
set.add(1);
set.add(5);
set.add(1); // 重复元素不会加入
system.out.println(set); // [3, 1, 5] 插入顺序保持
map<integer, string> map = new linkedhashmap<>();
map.put(3, "c");
map.put(1, "a");
map.put(2, "b");
map.put(2, "bb"); // key=2 更新 value
system.out.println(map); // {3=c, 1=a, 2=bb} 插入顺序保持哈希在算法中的 10 大经典用法
判断元素是否存在
set<integer> set = new hashset<>();
if (set.contains(x)) {}去重
set<integer> set = new hashset<>();
for (int n : nums) {
set.add(n); // hashset 自动去重
}统计频率
map<integer, integer> map = new hashmap<>(); for (int n : nums) map.put(n, map.getordefault(n, 0) + 1);
字符串计数（异位词）
int[] cnt = new int[26]; for (char c : s.tochararray()) cnt[c - 'a']++;
两数之和（值 → 下标）
map<integer, integer> map = new hashmap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (map.containskey(need)) return new int[]{map.get(need), i};
map.put(nums[i], i);
}前缀和 + 哈希（子数组和为 k）
map<integer, integer> map = new hashmap<>();
map.put(0, 1);
int sum = 0, res = 0;
for (int n : nums) {
sum += n;
res += map.getordefault(sum - k, 0);
map.put(sum, map.getordefault(sum, 0) + 1);
}两数组交集
set<integer> set = new hashset<>(); for (int n : nums1) set.add(n); set<integer> res = new hashset<>(); for (int n : nums2) if (set.contains(n)) res.add(n);
判断重复元素
set<integer> set = new hashset<>(); for (int n : nums) if (!set.add(n)) return true;
分组（分类）
map<string, list<string>> map = new hashmap<>();
for (string s : strs) {
string key = sort(s);
map.computeifabsent(key, k -> new arraylist<>()).add(s);
}最近最少使用缓存（lru）
class lrucache extends linkedhashmap<integer, integer> {
protected boolean removeeldestentry(map.entry eldest) {
return size() > capacity;
}
}数组哈希 vs map 哈希
当 key 范围固定小（如 a-z）：
int[] hash = new int[26]; hash[c - 'a']++;
当 key 范围大或不连续：
map<integer, integer> map = new hashmap<>();
总结
到此这篇关于java中哈希在算法中的10大经典用法的文章就介绍到这了,更多相关java哈希用法内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论