JAVA哈希基础:HashMap基本操作（HashSet），含常见算法题

哈希基础

一般哈希表都是用来快速判断一个元素是否出现集合里。

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• map(映射)
• set （集合）

Java数据结构

1.HashMap

//定义
HashMap<Integer, String> hashmap= new HashMap<Integer, String>();

//添加键值对
hashmap.put(1, "string1"); // 执行完后hash表内为{1=string1}
hashmap.put(2, "string2"); // 执行完后hash表内为{1=string1, 2=string2}
hashmap.put(2, "string2"); // 执行完后hash表内为{1=string1, 2=string2, 3=string3}

//根据键取值
hashmap.get(1); // 返回string1
hashmap.get(2); // 返回string2
hashmap.get(3); // 返回string3

//根据键删除
hashmap.remove(1); // 执行完后hash表内为{2=string2, 3=string3}

// 删除所有键值对
hashmap.clear();

//替换 hashMap 中是指定的key对应的 value
hashmap.replace(key,value); // 返回0

//返回hashmap中键值对的数量
hashmap.size(); // 返回0

hashmap.getOrDefault(key,defaultValue);

// foreach循环
for(var entry : map.entrySet()){
    // 获得key
    int key = entry.getKey();
	// 获得value
	int value = entry.getValue();
}

hashmap.containsKey(key); 
hashmap.containsValue(value); 
hashmap.isEmpty(); 
// 返回所有Value值组成的集合
hashmap.values(); 
/*
	如果有HashMap: {1=Google, 2=Runoob, 3=Taobao}
	则返回Values: [Google, Runoob, Taobao]
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.HashSet

定义：HashSet是基于HashMap的一个不允许有重复元素的集合，但其中允许存在null值。

//基本操作
Set<Integer> hashset= new HashSet<Integer>();
hashset.add(1);
hashmap.contains(1);
hashmap.remove(1);
hashmap.clear();
1
2
3
4
5
6

2.2HashSet如何实现去重？

HashSet是通过HashCode()与equals()方法实现去重的。

HashCode()的作用是对Java堆上的对象产生一个哈希码，用于确定该对象在哈希表中的索引位置，Java的任何类中都含有HashCode()。
equals()方法用于比较两个对象中存放的地址是否相等。

对象加入HashSet的过程： 对象加入HashSet时，HashSet会计算对象的hashcode值来判断对象加入的位置，如果该位置没有值，则直接放入；如果有值，则HashSet通过equals()方法来检查两个对象是否相同，如果两者相同，则加入失败，否则将会重新散列到其他的地方。

注意： 两个对象相等，也就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相等；
hashcode相等，两个对象不一定相等

242.有效的字母异位词

力扣题目链接

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length())  return false;
        int[] cnt=new int[26];
        for(char c:s.toCharArray()){
            cnt[c-'a']++;
        }
        for(char c:t.toCharArray()){
            cnt[c-'a']--;
            if(cnt[c-'a']<0)    return false;   
        }
        for(int i=0;i<26;i++){
            if(cnt[i]!=0)   return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

349. 两个数组的交集

力扣题目链接

题意：给定两个数组，编写一个函数来计算它们的交集。

版本一：使用HashSet

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        //方法1：将结果集合转为数组
        return resSet.stream().mapToInt(x -> x).toArray();
        
        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        return arr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

版本二：使用Hash数组

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1002];
        int[] hash2 = new int[1002];
        for(int i : nums1)
            hash1[i]++;
        for(int i : nums2)
            hash2[i]++;
        List<Integer> resList = new ArrayList<>();
        for(int i = 0; i < 1002; i++)
            if(hash1[i] > 0 && hash2[i] > 0)
                resList.add(i);
        int index = 0;
        int res[] = new int[resList.size()];
        for(int i : resList)
            res[index++] = i;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

202. 快乐数

力扣题目链接

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

class Solution {
    public int getNext(int n){
        int sum=0;
        while(n!=0){
            int c=n%10;
            sum=sum+c*c;
            n/=10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        Set<Integer> st=new HashSet<Integer>();
        while(n!=1&&!st.contains(n)){
            st.add(n);
            n=getNext(n);
        }
        return n==1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1. 两数之和

力扣题目链接(opens new window)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if(nums == null || nums.length == 0){
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int temp = target - nums[i];   // 遍历当前元素，并在map中寻找是否有匹配的key
        if(map.containsKey(temp)){
            res[1] = i;
            res[0] = map.get(temp);
            break;
        }
        map.put(nums[i], i);    // 如果没找到匹配对，就把访问过的元素和下标加入到map中
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18