[leetcode刷题]面试经典150题之9python哈希表详解（知识点+题合集）

为了方便理解哈希表，我们先从python中的字典讲起。

字典 (Dictionary)

字典是 Python 中一种内置的数据结构，它是一种 键值对（key-value pair）存储形式。每个键（key）都有一个对应的值（value）。字典的特点是键是唯一的，而值可以是任何数据类型。字典允许我们通过键快速查找对应的值。

# 定义一个字典
my_dict = {
    'name': 'Alice', 
    'age': 25, 
    'city': 'New York'
}

# 访问字典中的值
print(my_dict['name'])  # 输出 'Alice'
print(my_dict['age'])   # 输出 25

在这个字典 my_dict 中：

• 'name', 'age', 'city' 是 键（key）。
• 'Alice', 25, 'New York' 是 值（value）。

通过键，你可以快速查找对应的值。

字典相关的常用函数

1. keys()：返回字典中所有的键。

print(my_dict.keys())  # 输出 dict_keys(['name', 'age', 'city'])

 2.values()：返回字典中所有的值。

print(my_dict.values())  # 输出 dict_values(['Alice', 25, 'New York'])

3.items()：返回字典中的所有键值对，形式是 (key, value) 的元组。

print(my_dict.items())  # 输出 dict_items([('name', 'Alice'), ('age', 25), ('city', 'New York')])

4.get()：通过键获取值，但如果键不存在，不会报错，而是返回 None 或自定义的默认值。

print(my_dict.get('name'))  # 输出 'Alice'
print(my_dict.get('country', 'USA'))  # 输出 'USA'，因为'country'键不存在

字典背后的实现机制是 哈希表。哈希表是一种数据结构，它使用一种称为哈希函数的算法，将键映射到存储数据的位置。这种映射允许字典在平均情况下能够非常快速地查找数据。

哈希表的基本概念

• 哈希函数（Hash Function）：将输入的数据（通常是键）转化为一个整数（称为哈希值），并使用这个整数作为存储位置的索引。
• 哈希值（Hash Value）：由哈希函数生成的整数值，它决定了数据存储在哈希表中的位置。
• 哈希表（Hash Table）：一种通过哈希函数将键映射到值的结构，类似于一个巨大的数组，使用哈希值作为数组的索引。

2. 哈希表的工作原理

2.1 插入数据

1. 哈希函数：对于每个键 key，通过哈希函数 hash(key) 计算出哈希值（一个整数）。
2. 映射到索引：这个哈希值决定了数据在哈希表中的存储位置。通常，哈希表的大小是有限的，所以我们会使用 模运算 将哈希值映射到一个较小的索引范围上。
   • 假设哈希表的大小为 N，那么存储位置为 hash(key) % N。
3. 存储键值对：将键和对应的值存储到计算出的索引位置。

2.2 查找数据

1. 通过哈希函数计算哈希值：首先对要查找的键 key 计算哈希值。
2. 查找存储位置：根据哈希值查找存储位置，读取存储在该位置的值。

3. 哈希冲突 (Hash Collision)

由于哈希表的大小有限，不同的键通过哈希函数可能会映射到相同的位置，这种现象称为 哈希冲突。

3.1 处理哈希冲突的方法

1. 链地址法（Separate Chaining）：

   • 在每个哈希表的索引位置存储一个链表，当多个键映射到同一个位置时，使用链表存储这些键值对。

哈希表：
Index 0: [(key1, value1), (key2, value2)]  # key1 和 key2 发生了冲突
Index 1: [(key3, value3)]

      2.开放地址法（Open Addressing）：

• 如果发生冲突，寻找下一个空闲的位置（通过某种探测方式，如线性探测、二次探测等），将新的键值对存储到下一个空位。

4. 哈希表的优缺点

4.1 优点：

1. 查找、插入、删除速度快：平均时间复杂度是 O(1)。
2. 高效性：在数据量较大的情况下，哈希表仍能保持良好的性能。
3. 简单性：插入和查找操作都非常简单，通过键直接查找到值。

4.2 缺点：

1. 哈希冲突：虽然哈希表的查找和插入操作在平均情况下是 O(1)，但是如果哈希冲突较多，最坏情况下时间复杂度可能上升到 O(n)。
2. 无序性：哈希表通常不维护元素的顺序，数据是以哈希值的顺序存储的，因此元素的顺序是不可预测的。
3. 空间浪费：哈希表通常需要分配大量空间来减少冲突，这可能导致一定的空间浪费。

5. 哈希表在 Python 字典中的应用

在 Python 中，字典就是使用哈希表实现的。当你向字典中插入、删除或查找元素时，Python 背后会使用哈希函数计算键的哈希值，并将键值对存储在相应的存储位置。

• 通过哈希表，Python 字典在绝大多数情况下能够实现 O(1) 的查找和插入操作。
• Python 字典通过链地址法来处理哈希冲突。

下面我们结合一些题来深入学习哈希表

例1 

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路

因为字母异位词的特点是它们的字母相同、顺序不同，我们可以通过对每个单词的字母排序，得到一个唯一的“标准形式”作为哈希表的键。例如，"eat" 和 "tea" 都排序为 "aet"。我们把相同键（排序后的字母组合）的单词存放在哈希表对应的值（列表）里。这样，哈希表的每一个键对应的列表就是一组字母异位词，最后返回这些列表即可。

代码

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 创建哈希表，默认值为列表
        hash_map = defaultdict(list)

        # 遍历每个字符串
        for word in strs:
            # 将字符串按字母排序，并作为哈希表的键
            sorted_word = ''.join(sorted(word))
            # 将原始字符串加入对应的列表
            hash_map[sorted_word].append(word)

        # 返回哈希表的值，即每个异位词的组合
        return list(hash_map.values())

例2

两数之和

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路

这个题是力扣的第一个题，刚开始刷力扣的时候以为很简单，结果想了半天也没想出来，现在学完哈希表再做就容易多了。思路就是形成一个哈希表，将列表中的数作为键值，该数对应的位置作为值，为了避免重复的数，我们使用做差的方式，只返回一个值和一个位置组合。

代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d={}
        for i in range(len(nums)):
            a=target-nums[i]
            if a in d:
                return [d[a],i]
            d[nums[i]]=i

例3

存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

思路

这个题我看解题中说必须要用set函数才能做，其实跟例2一样，用个哈希表就做出来了。

1. 哈希表记录最近的索引：创建一个哈希表，键是数组的元素，值是该元素最后出现的索引。
2. 遍历数组：
   • 如果当前元素已经在哈希表中，检查它的上一次出现的索引与当前索引之差是否小于等于 k。如果满足条件，返回 true。
   • 如果不满足条件，更新该元素的最新索引为当前索引，继续遍历。
3. 如果遍历结束仍未找到符合条件的索引对，返回 false。

代码

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d = {}  # 用于存储数字和对应的索引
        for i in range(len(nums)):
            if nums[i] in d and i - d[nums[i]] <= k:  # 检查是否存在，并且索引差值是否小于等于k
                return True
            d[nums[i]] = i  # 更新索引为当前i
        return False

例4

 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路：

1. 使用哈希表来记录数组中的所有数字：我们可以将所有数字存入哈希表，以便能够快速检查一个数字是否存在。
2. 寻找序列起点：一个数字是序列的起点当且仅当它的前一个数字不在哈希表中。例如，数字 x 是一个序列的起点当 x - 1 不存在于哈希表中。
3. 向后查找最长的连续序列：对于每一个序列起点，我们通过不断寻找它的下一个数字，直到找到该序列的末尾。然后计算序列的长度。
4. 记录最长序列的长度：遍历过程中，记录找到的最长连续序列的长度。

算法步骤：

1. 将所有的数字存入哈希表，确保查找的时间复杂度为 O(1)。
2. 对于每个数字，只有当它是序列的起点时（即它的前一个数字不在哈希表中），才开始向后寻找。
3. 计算从这个起点开始的序列长度，并更新最长的长度。
4. 返回最长的长度。

代码

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 将所有数字存入哈希表中，便于查找
        num_set = set(nums)
        longest_streak = 0

        # 遍历每个数字
        for num in num_set:
            # 只有当 num 是序列的起点时，才开始查找
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # 不断找下一个连续的数字
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                # 更新最长序列的长度
                longest_streak = max(longest_streak, current_streak)

        return longest_streak