代码随想录第六天: 哈希表(数组+HashSet+HashMap)

标签：map set HashSet int 元素 随想录 哈希

语言: Java

参考资料: 代码随想录、ChatGPT3.5

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

在C++中，set，multiset和unordered_set都是标准库中的容器，用于存储一组唯一的元素。它们之间的区别和联系如下：

1. set：
   • set 是一个有序的容器，其中的元素按照严格的弱序（默认为升序）排列。
   • 每个元素在set中是唯一的，插入相同元素时，新的插入会被忽略。
   • 底层实现通常是基于红黑树，因此插入、删除和查找的时间复杂度为 O(log n)。
   • set 中的元素是唯一的，且是有序的。
2. multiset：
   • multiset 也是有序容器，但与 set 不同的是，它允许存储重复的元素。
   • 插入相同元素时，multiset 会将所有元素都插入。
   • 底层实现同样是基于红黑树，时间复杂度为 O(log n)。
   • multiset 中的元素是有序的，但可以重复。
3. unordered_set：
   • unordered_set 是一个无序容器，其中的元素没有特定的顺序。
   • 元素在 unordered_set 中是唯一的，且不按照特定的顺序存储。
   • 底层实现通常是基于哈希表，插入、删除和查找的平均时间复杂度为 O(1)，但最坏情况下可能达到 O(n)。
   • unordered_set 中的元素是唯一的，但是无序的。

联系：

• set 和 multiset 都是有序容器，它们适用于需要保持元素有序的场景，而 unordered_set 则适用于不需要保持元素有序的场景。
• multiset 与 unordered_set 都允许存储多个相同的元素，而 set 不允许。
• set 和 multiset 的底层实现都是基于红黑树，而 unordered_set 的底层实现是哈希表。
• 所有三个容器都提供了类似的接口，如插入、删除和查找操作，但其性能特点不同。

在C++中，map，multimap和unordered_map也是标准库中的容器，用于存储键-值对。它们之间的区别和联系如下：

1. map：
   • map 是一个有序的关联容器，其中的元素按照键的严格弱序（默认为升序）排列。
   • 每个键在 map 中是唯一的，插入相同的键会覆盖旧值。
   • 底层实现通常是基于红黑树，因此插入、删除和查找的时间复杂度为 O(log n)。
   • map 中的键是唯一的，且是有序的。
2. multimap：
   • multimap 是有序关联容器，允许存储具有相同键的多个键-值对。
   • 插入相同的键会创建多个键-值对。
   • 底层实现同样是基于红黑树，时间复杂度为 O(log n)。
   • multimap 中的键是有序的，且可以重复。
3. unordered_map：
   • unordered_map 是无序关联容器，其中的元素没有特定的顺序。
   • 每个键在 unordered_map 中是唯一的，且不按照特定的顺序存储。
   • 底层实现通常是基于哈希表，插入、删除和查找的平均时间复杂度为 O(1)，但最坏情况下可能达到 O(n)。
   • unordered_map 中的键是唯一的，且无序的。

联系：

• map 和 multimap 都是有序关联容器，它们适用于需要保持键有序的场景，而 unordered_map 则适用于不需要保持键有序的场景。
• multimap 与 unordered_map 都允许存储多个相同的键，而 map 不允许。
• map 和 multimap 的底层实现都是基于红黑树，而 unordered_map 的底层实现是哈希表。
• 所有三个容器都提供了类似的接口，如插入、删除和查找操作，但其性能特点不同。

242.有效的字母异位词

力扣题目链接(opens new window)

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

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

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

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

思路

先看暴力的解法，两层for循环，同时还要记录字符是否重复出现，很明显时间复杂度是 O(n^2)。

暴力的方法这里就不做介绍了，直接看一下有没有更优的方式。

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

如果对哈希表的理论基础关于数组，set，map不了解的话可以看这篇：关于哈希表，你该了解这些！(opens new window)

需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

代码:

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        for (int i = 0; i < 26; i++)
            record[i] = 0;
        for (int i = 0; i < s.length(); i++)
            record[s.charAt(i) - 'a']++;
        for (int i = 0; i < t.length(); i++)
            record[t.charAt(i) - 'a']--;
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0)
                return false;
        }
        return true;
    }
}

注意Java中字符串取其中字符的方法: 用字符串.charAt()

在 Java 中，HashSet 是 java.util 包中的一个类，它实现了 Set 接口，用于存储唯一的元素，不允许重复。以下是关于 HashSet 的一些重要特性和用法：

1. 唯一性：HashSet 中的元素是唯一的，它不允许存储重复的元素。如果试图将重复元素添加到 HashSet 中，重复的元素将被忽略。
2. 无序性：HashSet 不保证元素的顺序，元素存储的顺序可能与添加的顺序不同。如果需要有序性，可以使用 LinkedHashSet 或 TreeSet。
3. 基于哈希表：HashSet 的内部实现是基于哈希表的，这使得它在查找、插入和删除元素方面具有很高的性能。在大多数情况下，这些操作的时间复杂度为 O(1)。
4. 线程不安全：HashSet 不是线程安全的，如果多个线程同时访问一个 HashSet 实例并且至少有一个线程修改了该实例的结构（如添加或删除元素），则它必须通过外部同步（如使用 Collections.synchronizedSet() 方法）进行保证。
5. null 元素：HashSet 允许存储一个 null 元素。
6. 迭代：可以使用迭代器或者增强型 for 循环来遍历 HashSet 中的元素。
7. 不保证顺序：HashSet 中的元素是无序的，不会按照特定的顺序进行存储。如果需要有序性，可以使用 LinkedHashSet。

349. 两个数组的交集

力扣题目链接(opens new window)

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

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序

这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。

那么用数组来做哈希表也是不错的选择，例如242. 有效的字母异位词(opens new window)

但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

• std::set
• std::multiset
• std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

拓展

那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。

代码:

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 注意如何创建HashSet
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> res = new HashSet<>();
        for (int i : nums1)
            // 注意如何给HashSet添加元素
            set1.add(i);
        for (int i : nums2) {
            // 注意如何判断HashSet中是否存在元素
            if (set1.contains(i))
                res.add(i);
        }
        // 注意如何获得HashSet中的元素数目
        int[] arry = new int[res.size()];
        int j = 0;
        for (int i : res)
            arry[j++] = i;
        return arry;
    }
}

第202题. 快乐数

力扣题目链接(opens new window)

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

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

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

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路

这道题目看上去貌似一道数学问题，其实并不是！

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

正如：关于哈希表，你该了解这些！ (opens new window)中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

代码:

class Solution {
    public int getsum(int n) {
        int sum = 0;
        while (n != 0) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        // 注意如何创建HashSet
        HashSet<Integer> res = new HashSet<>();
        int sum;
        while (true) {
            sum = getsum(n);
            if (sum == 1)
                return true;
            // 注意如何判断HashSet中是否存在元素
            else if (res.contains(sum))
                return false;
            // 注意如何在HashSet中添加元素
            else
                res.add(sum);
            n = sum;
        }
    }
}

1. 两数之和

力扣题目链接(opens new window)

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

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

示例:

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

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

所以返回 [0, 1]

思路

很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。

建议大家做这道题目之前，先做一下这两道

• 242. 有效的字母异位词(opens new window)
• 349. 两个数组的交集(opens new window)

242. 有效的字母异位词 (opens new window)这道题目是用数组作为哈希表来解决哈希问题，349. 两个数组的交集 (opens new window)这道题目是通过set作为哈希表来解决哈希问题。

首先我再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。 更多哈希表的理论知识请看关于哈希表，你该了解这些！ (opens new window)。

这道题目中并不需要key有序，选择std::unordered_map 效率更高！ 使用其他语言的录友注意了解一下自己所用语言的数据结构就行。

接下来需要明确两点：

• map用来做什么
• map中key和value分别表示什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

总结

本题其实有四个重点：

• 为什么会想到用哈希表
• 哈希表为什么用map
• 本题map是用来存什么的
• map中的key和value用来存什么的

把这四点想清楚了，本题才算是理解透彻了。

很多录友把这道题目 通过了，但都没想清楚map是用来做什么的，以至于对代码的理解其实是 一知半解的。

代码:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        // 注意Map的创建方法
        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;
                // 注意Map如何通过key查找value
                res[0] = map.get(temp);
                break;
            }
            // 注意Map如何添加元素
            else map.put(nums[i], i);
        }
        return res;
    }
}

HashMap是Java中非常常用的数据结构之一，它实现了Map接口，基于哈希表（Hash Table）实现。HashMap允许存储键值对，并且提供了快速的数据访问和查找能力。以下是HashMap的一些关键特点和用法：

1. 键值对映射：HashMap 存储的数据是键值对的映射关系，每个键都映射到一个值上。通过键可以快速查找到对应的值。
2. 无序性：HashMap 不保证键值对的顺序，即它不会保持插入顺序或任何其他顺序。如果需要有序性，可以使用 LinkedHashMap。
3. 键的唯一性：HashMap 中的键是唯一的，每个键只能对应一个值。当尝试使用已经存在的键插入新值时，会覆盖原有的值。
4. 允许空键和空值：HashMap 允许使用 null 作为键，并且可以将键映射到 null 值。但在 HashMap 中，只允许有一个键的值为 null。
5. 线程不安全：HashMap 不是线程安全的，如果多个线程同时访问一个 HashMap 实例并且至少有一个线程修改了该实例的结构（如添加或删除元素），则它必须通过外部同步进行保证。
6. 哈希表实现：HashMap 的内部实现是基于哈希表的，它使用键的哈希码来存储和查找键值对。通过哈希码，可以快速地定位到存储桶（buckets），然后在桶内进行查找。
7. 迭代器：HashMap 提供了迭代器（Iterator）用于遍历键值对。迭代器遍历的顺序不确定，但通常情况下与元素的插入顺序无关。

标签：map,set,HashSet,int,元素,随想录,哈希
From： https://blog.csdn.net/sevune/article/details/137024608