哈希表是一种常见的数据结构，用于实现映射关系。在Python中，哈希表常被实现为字典（dictionary）类型，也就是Python中常用的一种数据类型。
哈希表基于哈希函数实现。哈希函数将输入映射到一个固定大小的输出，这个输出通常称为哈希值。哈希函数应该具有以下两个特点：
- 相同的输入总是产生相同的输出。
- 不同的输入很难产生相同的输出。
哈希表中每个元素都对应一个键和一个值。键通过哈希函数计算得到哈希值，然后根据哈希值存储在哈希表的相应位置。当需要查找一个键对应的值时，首先根据哈希函数计算键的哈希值，然后在哈希表中查找对应位置上的值即可。
一般来说啊，实现哈希表我们可以采用两种方法：
1、数组+链表
2、数组+二叉树
有效的字母异位词
题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。
解题
这道题使用数组来解决，数组是一种简单的哈希表。符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
char = [0] * 26
b = 0
for i in s:
char[ord(i)-ord('a')] +=1
for ii in t:
char[ord(ii)-ord('a')] -=1
for i in char:
if i != 0:
return False
return True两个数组的交集
题目
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
解题
这道题通过字典来进行解题，字典可以说是哈希表的一种常见形式，在进行两个数组相同元素的判断前，建立了一个字典来放置其中一个数组的元素，让元素作为字典的键，存在该元素则领该键对应的值为1. 还需要掌握的是字典的基本用法，如dict.keys()
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
val_dict = {} # 创建空字典
ans = []
for i in nums1:
val_dict[i] = 1
for i_2 in nums2:
if i_2 in val_dict.keys() and val_dict[i_2] == 1: # 判断键存在
ans.append(i_2)
val_dict[i_2] = 0
return ans快乐数
题目
编写一个算法来判断一个数 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
解题
class Solution:
def isHappy(self, n: int) -> bool:
def happy_check(num):
sum1 = 0
while num:
sum1 += (num % 10 )** 2 # 取余数得到一个整数，即个位数，取平方
num = num // 10 # 完成一位计算后，进一位
return sum1
sum_set = set()
while True:
n = happy_check(n)
if n == 1:
return True
else:
if n in sum_set: # 如果存在重复，则证明进入了循环。
return False
else :
sum_set.add(n) # 添加出现过的数两数之和
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题
了解Python内置函数enumerate的用法：用于将一个可遍历的数据对象（如列表、元组、字符串等）组合为一个带有索引的序列，同时返回索引和对应的元素。简单的例子介绍：
fruits = ['apple', 'banana', 'orange']
for index, fruit in enumerate(fruits):
print(index, fruit)
这道题需要构建字典，将数组的内容作为键，索引作为值来构建字典。然后在通过对应的键值存在与否来进行搜索。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_map = dict()
for index, value in enumerate(nums):
if target - value in nums_map:
return [nums_map[target - value] , index]
nums_map[value] = index
return []四数相加II
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
解题
建立字典，匹配关系一般从划分为两个部分来思考，所以两个数组两个数组来进行考虑，设定一个地方放一个数值，然后对应和的数值来进行匹配。
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
hash = dict()
for n1 in nums1:
for n2 in nums2:
if n1 + n2 in hash:
hash[n1 + n2] += 1
else:
hash[n1 + n2] = 1
count = 0
for n3 in nums3:
for n4 in nums4:
if -(n3 + n4) in hash:
count += hash[-(n3 + n4)]
return count赎金信
题目
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
解题
我的解法是使用map，利用第二个字符构建字典，然后查第一个字符能否在字典中完全寻找到：
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
strsame = dict()
for n1 in magazine:
if n1 in strsame:
strsame[n1] += 1
else:
strsame[n1] = 1
for n2 in ransomNote:
if n2 in strsame :
if strsame[n2] <= 0 :
return False
else:
strsame[n2] -= 1
else:
return False
return True代码随想录提出说用数组可以更加节约空间，都是小写字母，所以数组可以在26位内解决，但其实提交后没啥区别。
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
arr = [0] * 26
for x in magazine: # 记录 magazine里各个字符出现次数
arr[ord(x) - ord('a')] += 1
for x in ransomNote: # 在arr里对应的字符个数做--操作
if arr[ord(x) - ord('a')] == 0: # 如果没有出现过直接返回
return False
else:
arr[ord(x) - ord('a')] -= 1
return True
