【算法】Python中哈希表的使用

💡引入概念

Hash Map

哈希表（Hash Map），又称作散列表。它是根据关键码值（Key, Value）对数据进行访问的一种数据结构。在Python中，与列表不同的是，哈希表通过键来直接访问数据，而列表通过数字下标访问。

对不同的关键字，可能会得到同一个散列地址，即同一个Value，可能会有不同的Key同时指向。这种现象我们称为冲突，具有相同函数值的关键字在哈希表中被叫做同义词。

而在Python中，字典（directory）就是哈希表的一个实现。

字典

以下是Python中的一个字典：

1	dict_1 = {'a': 1, 'b': 2, 'c': 3}

字典的每个键值对（key : value）之间用逗号分隔，整体使用大括号包围起来。

字典中，可以有重复的value，但不允许存在存在重复的key，但是使用重复的key并不会报错，而是在读取这个key的时候，总是取右边（后面）的值。

>>> ex_dict = {'a': 1, 'b': 2, 'b': 3}
>>> print('ex_dict['b']: '), ex_dict['b']

ex_dict: 3

🔨优化举例

实例题目

给定一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，使得nums[i] == nums[j]，并且 i 和 j 差的绝对值的最大值为 k 。要求所用时间尽量短。

例1：

1 2	in : nums = [1, 2, 3, 1], k = 3 out: True

例2：

1 2	in : nums = [1, 2, 3, 1, 2, 3], k = 2 out: False

难度：★★☆☆☆

未优化做法

如果不使用字典，直接按照一般思路，如下面这个代码：

def solution(nums: List[int], k: int) -> bool:
    if len(nums) <= 1: 
        return False
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] == nums[j] and abs(i-j) <= k:
                return True
    return False

这个算法的时间复杂度很高，嵌套了两个循环。在 nums 中的元素不多的时候还能凑合使用，可一旦 nums 中含有大量的元素（$n>=30000$）且相等元素间隔大时，很容易会出现超时的错误。

怎样才能在一次循环内将答案确定呢？

优化思路

给定一个在列表 nums 中的值 a ，要找到和其相等的值，如果通过下标来查找，必然要遍历一次 nums 。而要针对每一个元素都要去查找相同的值，就要嵌套又一层遍历。

如果将每一个 nums[i] 的值作为一个唯一的标识去对应下标 i ，即Key是 nums[i] ，而Value是 i 。这样就可以避免重复查找。

为此，我们需要使用Python中的字典。

代码如下：

def solution(nums: List[int], k: int) -> bool:
    nums_len = len(nums)
    if nums_len <= 1:
        return False
    nums_dict = {}					#用于查找的字典
    for i in range(nums_len):
        if nums[i] in nums_dict:			#如果字典有这个键，说明此时查找到了相等的值
            if i - nums_dict[nums[i]] <= k:		#再判断其是否满足下标差的绝对值不大于k
                return True
        nums_dict[nums[i]] = i				#没有在字典里的，以列表里的值为键，索引为值加入
    return False

如此一来，只用一次遍历，就可以完成整个过程。

这个算法的重点就是将列表元素的值作为关键字，而索引成为了值，由于索引不会重复，所以节省了许多不必要的时间，使得算法的复杂度降低了，达到了优化的效果。