关键知识点

hash表的最常用的作用：快速判断一个元素是否在集合里！
hash表的三种结构：

• ①数组
• ②set（集合）
• ③map（映射）

这其中每一个结构都有其特点以及特定的使用场景！

Hash表三大结构分析

数组结构的使用

它的具体使用场景有力扣的242.有效的字母异位词和383.赎金信等

赎金信题目
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
输入: s = “anagram”, t = “nagaram”
输出: true

数组这个结构使用的较少，但是他的使用状况也非常容易判断。在涉及到26个大写字母，或小写字母的时候就可以使用此结构。其原理是因为，26个大小写的字母的ASCII码值是连在一起的，故可以"A"或"a"来做基准，把26个字母放在数组中去。
当然用数组的场景用map当然也可以，但是有点大炮打蚊子的意味，因为map的空间消耗更大，且其中涉及了维护与运算，所以这种场景下使用数组就更加的简洁高效！

核心代码展示

java实现

for(char chr:b.toCharArray()){
            box[chr - 'a'] += 1;
        }
        for(char chr:a.toCharArray()){
            box[chr - 'a'] -=1;
        }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

Set结构的使用

在java中常用的set结构有两种：

1. HashSet（可以接收null）
2. TreeSet（可以跟你排序，所以不能接收null）

在做算法题的时候个人认为set的最主要作用就是去重（不过有时候排序+指针也能解决重复问题，不过显然set更加简便）！

在力扣中的相关题目349.两个数组的交集和

349
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

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

在349这个题目中单纯的是把Set当成了一个去重的容器，对两个数组分别去重之后再取他们的交集就可以得到结果。而202中用到了Set的快速查询功能（也就是判断是否在容器内)。

那为什么这个题不用数组结构去做呢，而选择去用Set结构？（如下两点原因不建议使用数组）

• 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
• 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

Map结构的使用

java中常用的map结构，也是两种：

1. HashMap
2. TreeMap（自带排序功能）

Map结构的代表题目是力扣1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

使用map结构是因为存储，去重的同时还会附带有关联的信息，而两数之和这道题目，题目要求返回的是其角标，如果你去用Set的话，他只能记录你的值，而角标的信息就丢失了，有人会说不能用index查找吗？肯定不行!首先这是Set，是无序的，就算有序，有重复元素的话用index是区分不开相同元素的角标的。
在使用map结构的的时候，你还要思考，什么值放在values的位置上，什么值放在keys的位置上。

三大结构的总结

这三种结构可以说都是一种容器，而容器的本质是记录，这三种结构的记录方式各不相同，有快捷记录，重复记录，不可重复记录，连结信息记录，对应的场景使用对应的记录方式。

附录：代码的简洁性思考

重合性比对操作

可以举一个简单的例子

现在让你比对数据A，B是否相等。大多数人第一想法肯定是把A中数据统计出来放在一个数组中，把B中数据统计出来放在一个数组中，再用一个for循环去比对，而更简洁的方法是，将在统计表A的数据之后直接在表A数据的基础上，用表B的数据去做减法，如果最终得出来的数组每一项均为零，则说明两个数组相等。（有时候这样思考更加简便）

比对操作的高效合并性

同样假设现在有两个数据堆，要对其进行比对操作。
常见操作：对数据堆A进行处理，对数据堆B进行处理，将两者处理完毕后再进行对比，

高效操作：处理完数据堆A之后，在处理数据堆B的同时，去与数据堆A进行比对，从而提高代码的简洁性和执行效率。

文章来源: blog.csdn.net，作者：十八岁讨厌编程，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/zyb18507175502/article/details/122275767