前言

今天是算法训练营的第六天，第五天究极大休，今天一觉睡到下午五点😆，下次休息日该尝试把之前的题重刷练练手了。

从今天开始进入哈希表环节，哈希表在之前刷 hot100 时经常用到，结果隔了一个多月不做题又忘差不多了。

哈希表理论基础

记得第一次看到哈希表这词儿时觉得好高大上，下意识认为这东西一定很难，由于畏难情绪加上校内数据结构课程没好好学，当我真的沉下心来认识它时发现并不如我想象中的那么骇人。

哈希表(英语：Hash table)，通常称为散列表，是根据键而直接访问在存储器存储位置的数据结构。哈希表通过使用一个计算键值的函数，将数据映射到表中的某一个位置，这种方式加快了查询速度，运用到的函数叫做哈希函数或散列函数，存放记录的数组(也可以是其他结构)叫做哈希表或散列表。

当我们需要快速判断一个元素是否出现在集合里时，需要第一时间考虑哈希法，哈希法究其本质是空间换时间。

基本概念

若关键词为k，则其值存放在f(k)的存储位置上，这个对应关系 f 为哈希函数，以这种方式建立的表称为哈希表。

如果经过哈希函数后得到的数值超过哈希表的大小了，此时为了保障映射出来的所有索引值都在哈希表上，会对数值进行取模操作保障数据一定能映射到哈希表上。

但是，这么做对不同的关键字可能得到同一哈希表地址即k1 ≠ k2，而f(k1) = f(k2)，这种现象称为冲突，具有相同函数值的关键字对该哈希函数称为同义词。

若对于关键字集合中的任一个关键字，经过散列函数镜像到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀哈希函数，这样做可以减少冲突。

解决冲突

一般哈希冲突有两种解决方法：拉链法和线性探测法，这两种方法分别对应 wiki 中记录到的聚集（或堆积）和开放寻址法。

拉链法

将发生冲突的元素都存储在链表当中，这样可以通过索引找到数据。在实现时，除了使用链表还可以选择使用栈等方式，具体设计模式完全取决于怎样方便。

线性探测法

逐个探测存放地址的表，直到查找到一个空单元，将哈希地址存放在该空单元。

在线性探测的基础上，根据探测模式的不同，还有平方探测和伪随机探测等方式。

常见的三种哈希结构

当我们想使用哈希表解决问题时，通常会选择使用以下三种数据结构：

• 数组
• set 集合
• map映射，在 python 里的具体实现为字典 dict

242.有效的字母异位词

题目链接：242. 有效的字母异位词

题目描述：

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

思路

首先是判断需要哪种哈希结构，如果数据结构使用不当将浪费大量空间，此处由于字母数量只有 26 位，所以选用数组。定义一个数组用来记录字符串 s 中，每个字符出现的次数，如果出现次数相等，那么两个字符串互为字母异位词。

具体的实现方式是先记录字符串 s 每个字符出现的次数，然后再判断字符串 t 中的元素是否有重合，如果有就在 record 哈希表里将对应字母次数减 1，最后如果 record 所有字母对应值皆为 0，那么说明两个字符串互为字母异位词。

实现写法

 class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            record[ord(i) - ord("a")] += 1
        for i in t:
            record[ord(i) - ord("a")] -= 1
        
        for i in range(26):
            if record[i] != 0:
                return False
        return True

349.两个数组的交集

题目链接：349. 两个数组的交集

题目描述：给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路

使用一个字典来记录 nums1 中每个数字的出现次数，然后再让 nums2 中每一个元素与字典进行比较，如果对应值在字典中存在且非零，就存入 result 集合中等待输出，然后删除字典中对应键值对（不删也能运行）。

实现写法

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        table = {}
        for i in nums1:
            table[i] = table.get(i, 0) + 1
        
        res = set()
        for i in nums2:
            if i in table:
                res.add(i)
                //delete table[i]
        return list(res)

202.快乐数

题目链接：202. 快乐数

题目描述：

编写一个算法来判断一个数 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

思路

刚看到这道题时我的想法被题目描述牵着走，以为又是一道类似过程模拟的写法，正当还在思考如何判断是否陷入无限循环，看了文档后才发现只需要判断每位数字平方和是否重复出现就可以判断出无限循环。

做法是先对数字 n 进行每位数字平方和的运算，然后使用哈希法判断数字平方和在先前是否有出现过，如果有则说明不是快乐数。

实现写法

 class Solution:
    def isHappy(self, n: int) -> bool:
        record = set()
        while True:
            n = self.get_sum(n)
            if n == 1:
                return True
            
           
            if n in record:
                return False
            else:
                record.add(n)
    
        
    def get_sum(self, n: int) -> int:
        num_sum = 0
        while n :
            n, r =divmod(n, 10)
            num_sum += r ** 2
        return num_sum

1.两数之和

题目链接:1. 两数之和

题目描述：

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

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

示例:

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

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

所以返回 [0, 1]

思路

这道题更是老生常谈了，暴力法不再赘述。先前已经有使用过哈希法解决这道题，具体思路就是对数组中每一个数值进行判断，判断 target – nums[i] 是否存在于 nums 中，如果存在就输出两个索引，总体来说比较简单，由于要使用到索引和值的键值对，所以选择使用字典来作为数据结构。

实现写法

 class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        for index, value in enumerate(nums):
            if target - value in record:
                return [record[target - value], index]
            record[value] = index
        return []

总结

在今天的训练里，我们主要学习了哈希表的基础概念以及三个常用的数据结构，在题目的训练中分别对三种数据结构的适用场景进行分析。总体来说，哈希法在理解起来还是相对来说比较简单，以后看到需要我们判断某个值是否在集合里的类似题目时，需要第一时间考虑能否用哈希表来解决。