哈希表底层采用数组+链表实现，它是将 key 通过哈希函数计算出一个整数，然后以这个整数作为数组的下标，然后将 value 存放到对应下标的数组中。对于不同的 key，在经过哈希函数计算后，可能出现相同的值，这种情况叫做哈希冲突，这就意味着同一个数组下标处要存放两个元素了，这里主要使用拉链法，用链表的方式将这个两个元素串联起来。哈希表对于删除、查找、更新、插入操作，都是先根据 key 计算出一个值，就能定位到数据的目标位置了，时间复杂度都是 O(1)

Hash散列表 - 图1

散列函数的冲突

对于不同的KEY，使用散列函数却得到同一个散列地址

如何处理散列冲突

一般使用除留余数法获取新的存储地址 H=(Hash(key)+d) % m
开放定址法

  • 线性探测法：冲突了就放到下一个位置
  • 二次探测法：冲突了就放在计算完散列函数的整数的平方的位置，而不是像前面那样就是单纯的不停地加1，这样就可以不让关键字对集中在一块地方
  • 双重散列法：思就就是使用一组散列函数hash1(key),hash2(key),hash3(key)，如果第一个散列函数找到的位置被占用，再找第二个散列函数，一次类推

拉链法：将散列值一样的键值对保存在一个单链表中。（常用）

散列表性能影响因素

  1. 散列函数是否均匀
  2. 散列表的负载因子
  • 负载因子 = 表中元素个数/散列表长度
  • α 越大，冲突的可能性就越大。

扩容

  • 一次性扩容：当负载因子过大时会触发扩容机制，哈希表的容量增加为原先的两倍，并且需要对原来的数据重新rehash做散列计算，但是这时增加新一个元素的性能是比较差的，因为要等待原先的表rehash之后才能增加该元素
  • 穿插扩容：将扩容过程穿插在插入过程中，将新数据都插入新散列表的同时将原来的散列表取出一个数据插入新表，经过多次插入过程，原来的散列表就慢慢的转移到新表中了，查询数据时先去旧散列表中查询，如果没有则在新表中查询

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

  1. class Solution:
  2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
  3.         # 方法一：散列表
  4.         dicts = {}
  5.         for i in range(len(nums)):
  6.             tmp = target - nums[i]
  7.             if tmp not in dicts:
  8.                 dicts[nums[i]] = i
  9.             else:
  10.                 return [dicts[tmp], i]
  12.         # 方法二：双指针（最优解）
  13.         left = 0
  14.         right = len(nums) - 1 
  15.         while left < right:
  16.             tmp = target - nums[right]
  17.             if tmp > nums[left]:
  18.                 left += 1
  19.             elif tmp < nums[left]:
  20.                 right -= 1
  21.             else:
  22.                 return [left, right]

四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2

  1. class Solution(object):
  2.     def fourSumCount(self, A, B, C, D):
  3.         # 两两相加，最后转换成两数之和
  4.         res = 0
  5.         dicts = {}
  7.         for i in A:
  8.             for j in B:
  9.                 tmp = i + j
  10.                 if tmp not in dicts:
  11.                     dicts[tmp] = 1
  12.                 else:
  13.                     dicts[tmp] += 1
  15.         for i in C:
  16.             for j in D:
  17.                 tmp = i + j
  18.                 if -tmp in dicts:
  19.                     res += dicts[-tmp]
  20.         return res

存在重复元素 III（桶排序）

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

  1. class Solution(object):
  2.     def containsNearbyAlmostDuplicate(self, nums, k, t):
  3.         # 方法一：桶排序
  4.         # 对所有数字//t+1可以把数字装进不同的桶里，桶里面的数字满足abs(nums[i] - nums[j]) <= t，并且i<k时桶里面的数字满足abs(i - j) <= k
  5.         # 对数组进行遍历，从i到k时，如果有桶里有俩数，很明显满足
  6.         # 超过k的时候，就需要把i-k的数从桶里删除，因为不再考虑他们了
  7.         dicts = {}
  8.         bucket_size = t + 1
  9.         for i in range(len(nums)):
  10.             bucket_num = nums[i] // bucket_size  # 放入哪个桶
  11.             # 要加入的这个桶值存在，说明之前有某个j，使得nums[j]//(t+1)==nums[i]//(t+1),根据上面第一条那就返回True（所以根据这条，这些桶最多只有一个数，如果有俩早就返回True了）
  12.             if bucket_num in dicts:  # 桶中已经有元素了
  13.                 return True
  14.             else:
  15.                 # 如果不存在，把nums[i]放入桶中，然后跟相邻的桶的value比较一下，如果满足abs(nums[i] - nums[j]) <= t ，返回True。
  16.                 dicts[bucket_num] = nums[i]
  18.                 if (bucket_num - 1) in dicts and abs(dicts[bucket_num - 1] - nums[i]) <= t:  # 检查前一个桶
  19.                     return True
  21.                 if (bucket_num + 1) in dicts and abs(dicts[bucket_num + 1] - nums[i]) <= t:  # 检查后一个桶
  22.                     return True
  24.                 # 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，以维持桶中的元素索引跟下一个i+1索引只差不超过k
  25.                 if i >= k:
  26.                     dicts.pop(nums[i-k] // bucket_size)
  27.         return False
  29.         # 方法二： 滑动窗口
  30.         if t < 0:
  31.             return False
  32.         window = []  # 滑动窗口
  34.         for i in range(len(nums)):
  35.             idx = bisect.bisect_left(window, nums[i] - t)  # 第一个 >= (num-t)的index
  36.             if idx < len(window) and window[idx] <= (nums[i] + t):
  37.                 return True
  39.             idx = bisect.bisect_left(window, nums[i])
  40.             window.insert(idx, nums[i])  # 进R
  42.             if i >= k:  # 弹L
  43.                 window.remove(nums[i - k])
  44.         return False

字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

  1. class Solution(object):
  2.     def groupAnagrams(self, strs):
  3.         dicts = {}
  4.         res = []
  5.         for i in strs:
  6.             j = list(i)
  7.             j.sort()
  8.             if ''.join(j) in dicts:
  9.                 dicts[''.join(j)].append(i)
  10.             else:
  11.                 dicts[''.join(j)] = [i]
  13.         for key, value in dicts.items():
  14.             res.append(value)
  15.         return res

同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
输入：s = “egg”, t = “add”
输出：true
输入：s = “foo”, t = “bar”
输出：false

  1. class Solution(object):
  2.     def isIsomorphic(self, s, t):
  3.         # 方法一：散列表，s当key，t当value
  4.         if not s:
  5.             return True
  7.         dicts = {}
  8.         for i in range(len(s)):
  9.             if s[i] not in dicts:
  10.                 if t[i] in dicts.values():
  11.                     return False
  12.                 else:
  13.                     dicts[s[i]] = t[i]
  14.             else:
  15.                 if dicts[s[i]] != t[i]:
  16.                     return False
  17.         return True
  19.         # 方法二
  20.         for i in range(len(s)):
  21.             if s.index(s[i]) != t.index(t[i]):
  22.                 return False
  23.         return True

最大交换

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
输入: 2736
输出: 7236
解释: 交换数字2和数字7。

  1. class Solution:
  2.     def maximumSwap(self, num):
  3.         if num < 10:
  4.             return num
  5.         lists = [int(i) for i in str(num)]
  6.         dicts = {}
  7.         for i in range(len(lists)):
  8.             dicts[lists[i]] = i  # 对0-9 十个键创建字典，数值相同时value取靠后的下标位置
  10.         for i in range(len(lists)):
  11.             for j in range(9, 0, -1):  # 从9到1遍历，保证交换数是最大的
  12.                 if dicts.get(j) > i and j > lists[i]:  # 只要有一个在在右边且比当前数大就交换 
  13.                     lists[i], lists[dicts[j]] = lists[dicts[j]], lists[i]
  14.                     return int(''.join([str(i) for i in lists]))
  15.         return num

特殊情况

有些时候题目用散列表很简单，但是要求空间复杂度为O（1），所以不能用散列表，可以使用正负数解决这个问题，这里会用到一个特殊的方法abs(i)，它可以返回i的绝对值

找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

  1. class Solution(object):
  2.     def findDisappearedNumbers(self, nums):
  3.         res = []
  4.         for num in nums:
  5.             num = abs(num)
  6.             if nums[num-1] > 0:
  7.                 nums[num-1] *= -1
  9.         for i in range(len(nums)):
  10.             if nums[i] > 0:
  11.                 res.append(i + 1)
  12.         return res

数组中重复的数据

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]

  1. class Solution(object):
  2.     def findDuplicates(self, nums):
  3.         if not nums:
  4.             return []
  5.         res=[]
  7.         # 1<=num<=n 遍历到 num 则令第 num 个元素变成-num
  8.         for i in range(len(nums)):
  9.             # abs是返回绝对值
  10.             num = abs(nums[i])
  11.             # 如果第num个数字已经是负的 说明之前遇到过num 说明num出现两次
  12.             if nums[num-1] < 0:
  13.                 res.append(num)
  14.             nums[num-1] =- nums[num-1]
  15.         return res
  17. [4, 3, 2, 7, 8, 2, 3, 1]
  18. [4, 3, 2, -7, 8, 2, 3, 1]
  19. [4, 3, -2, -7, 8, 2, 3, 1]
  20. [4, -3, -2, -7, 8, 2, 3, 1]
  21. [4, -3, -2, -7, 8, 2, -3, 1]
  22. [4, -3, -2, -7, 8, 2, -3, -1]
  23. [4, 3, -2, -7, 8, 2, -3, -1]
  24. [4, 3, 2, -7, 8, 2, -3, -1]
  25. [-4, 3, 2, -7, 8, 2, -3, -1]

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
输入：nums = [1,2,0]
输出：3
输入：nums = [3,4,-1,1]
输出：2
输入：nums = [7,8,9,11,12]
输出：1

  1. class Solution(object):
  2.     def firstMissingPositive(self, nums):
  3.         for i in range(len(nums)):
  4.             # 如果小于0，就给他丢到最后边
  5.             if nums[i] <= 0:
  6.                 nums[i] = len(nums) + 1
  8.         for i in range(len(nums)):
  9.             num = abs(nums[i])
  10.             if num <= len(nums):
  11.                 nums[num-1] = -abs(nums[num-1])
  13.         for i in range(len(nums)):
  14.             if nums[i] > 0:
  15.                 return i + 1
  17.         return len(nums) + 1