【Python 数据结构 15.哈希表】

目录

一、哈希表的基本概念

1.哈希表的概念

2.键值对的概念

3.哈希函数的概念

4.哈希冲突的概念

5.常用的哈希函数

Ⅰ、直接定址法

Ⅱ、平方取中法

Ⅲ、折叠法

Ⅳ、除留余数法

Ⅴ、位与法

6.哈希冲突的解决方案

Ⅰ、开放定址法

Ⅱ、链地址法

7.哈希表的初始化

8.哈希表的元素插入

9.哈希表的元素删除

10.哈希表的元素查找

二、Python中的哈希表

1.哈希表的创建（字典）

2.哈希表的元素修改

Ⅰ、元素的索引

Ⅱ、元素的添加

Ⅲ、元素的删除

Ⅳ、元素的修改

3.哈希表的查找与遍历

Ⅰ、通过键查找值

Ⅱ、遍历哈希表的键

Ⅲ、遍历哈希表的值

Ⅳ、遍历哈希表的键和值

三、代码实战

1512. 好数对的数目

方法一、哈希表

思路与算法

方法二、二重循环

思路与算法

961. 在长度 2N 的数组中找出重复 N 次的元素

方法一、哈希表

思路与算法

编辑

1207. 独一无二的出现次数

方法一哈希表

思路与算法

你每次都会自己站起来，这次又怎会是意外

—— 25.3.13

一、哈希表的基本概念

1.哈希表的概念

哈希表又叫散列表，我们需要把查找的数据通过一个函数映射，找到存储数据的位置，这个过程被称为哈希。需要查找的数据本身被称为关键字，通过一个函数映射将关键字变成哈希值的过程，这里的函数被称为哈希函数。

生成哈希值的过程可能产生冲突（两个关键字通过一个哈希函数后得到的哈希值相同），需要进行冲突解决，解决完冲突以后，实际存储数据的位置被称为哈希地址。通俗的说，它就是一个数组下标，存储所有这些数据的表，就被称为哈希表。

为了方便索引，哈希表底层实现结构是一个顺序表，每个位置被称为一个槽，存储一个键值对。以下就是一个长度为 8 的哈希表：

2.键值对的概念

键值对由键和值组成，键和值都可以是任意类型(比如整型、浮点型、字符串、类等等)。

哈希表的实现过程中，我们需要通过一些手段将一个非整型的键转换成整数，也就是哈希值，从而通过 O(1) 的时间快速索引到它对应在哈希表中的位置。而将一个非整形的关键字转换成整型的手段，就是哈希函数。

3.哈希函数的概念

哈希函数可以理解为小学课本上的那个函数 y=f(x)，这里的 f(x) 就是哈希函数。x 是键，y 是哈希值。好的哈希函数应该具备两个特征：(1)单射 (2)雪崩效应

单射：哈希值 y 与键 x 一一对应

雪崩效应：为了让哈希值，更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。

4.哈希冲突的概念

哈希函数在生成哈希值的过程中，如果不同的关键字传入哈希函数后得到相同的哈希值，就被称为 哈希冲突

5.常用的哈希函数

Ⅰ、直接定址法

直接定址法就是：键本身就是哈希值，表示成函数就是 f(x) = x，例如计数排序的原理，采用的就是直接定址法。由于哈希值是需要映射到顺序表中作为索引的，所以直接定址法只能处理数据量较小的且为非负整数的键。

Ⅱ、平方取中法

平方取中法就是对键进行平方运算，再取中间的某几位作为哈希值。例如：对于键 1314 平方后得到 1726596，取中间三位作为哈希值，即 265。平方取中法比较适合于不清楚键的分布，且位数不是很大的情况。

Ⅲ、折叠法

折叠法是将关键字分割成位数相等的几部分，然后再进行求和，得到一个哈希值。例如：对于关键字 5201314，将它分为四组，并且相加得到52+01+31+4=88，这个就是哈希值。

Ⅳ、除留余数法

除留余数法，就是键的值模上哈希表长度，表示成函数 f(x) = x mod m，其中 m 代表了哈希表的长度。这种方法，不仅可以对关键字取模，也可以在平方取中法、折叠法之后再取模。

例如：对于一个长度为 4 的哈希表，可以将关键字模4 得到哈希值。而这个方法也是我们要重点介绍的方法。

Ⅴ、位与法

哈希表的长度一般选择 2 的幂

取模运算比较耗时，而位运算相对较高效，选择 2 的幂作为哈希表长度，可以将取模运算转换成二进制位与，令 m 等于 2 的 k 次，其二进制表示为：

任何一个数模上 m，相当于取了 m 的二进制的低 k 位：

m 的模运算与 m - 1 的位于运算效果是一样的：x % S == x & (S - 1)

除了直接定址法，其他方法都可能导致哈希冲突

6.哈希冲突的解决方案

解决哈希冲突的主要两种方法：开放定址法和链地址法，无论是开放地址法，还是链地址法，都可以实现哈希表，我们只需要选择其中一种即可。

Ⅰ、开放定址法

开放定址法就是一旦发生冲突，就去寻找下一个空的地址，只要哈希表足够大，总能找到一空的位置，并且记录下来作为它的哈希值，公式：

d_i是一个数列，可以是常数列，也可以是等差数列

哈希表的每个数据就是一个键，插入之前需要先进行查找，如果找到的位置未被插入则执行插入，否则找到下一个未被插入的位置进行插入。

这种方法需要注意的是：当插入数据超过哈希表长度时，不能再执行插入，否则会造成死循环。

Ⅱ、链地址法

当产生冲突后，我们也可以选择不换位置，还是在原来的位置，只是把哈希值相同的用链表串联起来，这种方法被称为链地址法。

哈希表的每个数据，保留了链表头结点和尾结点，插入前需要先进行查找，如果找到的位置链表非空，则插入尾结点，并且更新尾结点。否则生成一个新的链表头结点和尾结点。

7.哈希表的初始化

给定一个大小 n，申请一个 n 个元素的数组，元素类型是：哈希表键值对

8.哈希表的元素插入

给定元素，利用哈希函数计算它的哈希值，对数组长度 n 取模以后，找到合适的位置，遍历这个位置上的链表，如果发现没有键值对相等的元素，则插入这个链表

9.哈希表的元素删除

给定元素，利用哈希函数计算它的哈希值，对数组长度 n 取模以后，找到合适的位置，遍历这个位置上的链表，如果发现有键值对相等的元素，则从链表上进行删除

10.哈希表的元素查找

给定元素，利用哈希函数计算它的哈希值，对数组长度 n 取模以后，找到合适的位置，遍历这个位置上的链表，如果发现有键值对相等的元素，返回 True；否则，返回 False。

二、Python中的哈希表

1.哈希表的创建（字典）

hash = {}
hash = {"e":3, "t":6, "a":1, "o":4, "i":5, "n":2}
print(hash)

2.哈希表的元素修改

Ⅰ、元素的索引

hash['u'] = 9
print(hash)hash['u'] = 4
print(hash)

Ⅱ、元素的添加

hash['z'] = 13
print(hash)

Ⅲ、元素的删除

hash.pop()：用于移除字典中指定键的项，并返回该键对应的值。如果指定的键不存在，可提供一个默认值，否则会引发 KeyError 异常。

参数名	类型	是否必需	描述
key	任意可哈希类型	是	需要从字典中移除的键
default	任意类型	否	如果指定的键不存在时返回的默认值，默认为 `None`

hash.pop('o')
print(hash)

Ⅳ、元素的修改

hash['z'] += 1print(hash['z'])

3.哈希表的查找与遍历

Ⅰ、通过键查找值

hash.get()：用于返回指定键的值。如果键存在于字典中，则返回对应的值；如果键不存在，则返回默认值（默认为 None），不会引发 KeyError 异常。

hash.get(x, 0) + 1：通过遍历列表 nums，使用哈希表（字典）hash 可以统计每个元素的出现次数。

参数名	类型	是否必需	描述
key	任意可哈希类型	是	需要查找值的键
default	任意类型	否	如果指定的键不存在时返回的默认值，默认为 `None`

print(hash.get('x', 9))

Ⅱ、遍历哈希表的键

hash.keys()：返回一个视图对象，该对象包含了字典中所有的键。

for k in hash.keys():print(k, end = " ")

Ⅲ、遍历哈希表的值

hash.values()： 返回一个视图对象，该对象包含了字典中所有的值。

for v in hash.values():print(v, end = " ")

Ⅳ、遍历哈希表的键和值

hash.items()：返回一个视图对象，该对象包含了字典中所有的键值对，每个键值对以元组的形式表示。

for k,v in hash.items():print(k, v, end = " ")

三、代码实战

1512. 好数对的数目

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

示例 1：
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3]
输出：0
提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100