Python 散列表查询_进入哈希函数＞为结界的世界

哈希表或称为散列表，是一种常见的数据存储方案，使用频率很高。

哈希表属于抽象数据结构，需要开发人员按照哈希表数据结构的存储要求 API 对于大多数高级语言，定制将提供已实现并可直接使用的服务 API，如 JAVA 中有 MAP 集合、C 中的 MAP 容器，Python 中的字典……

可供用户使用 API 完成正确的方法哈希表增、删、改、查……一系列操作。

如何学习哈希表？

可以从 2 角度开始:

什么是哈希表？

哈希表是基于键、值对于存储的数据结构，底层一般采用列表(数组)。

众所周知，基于列表(数组)查询速度很快，时间复杂 O（1），常量级别。

列表的底层存储结构是一个连续的内存区域，只要给定数据在列表(数组)中的位置，就可以直接查询数据。理论上是这样，但在实际操作过程中，查询数据的时间复杂性不一定是常量级的。

如果存储以下学生信息，学生信息包括学生姓名和学号。存储学生数据时，如果学号是 0 学生存储在列表中 0 位置，学号为 1 学生存储在列表中 1 位置……

在这里，学生的学号与列表中的索引号相关。当查询学生时，如果你知道学生的学号，你就会知道学生数据存储在列表中的位置。可以认为查询时间的复杂性是 O(1)。

之所以能达到常量级，是因为这里有信息关联(学生学号关联到数据存储位置)。

还有一点，学生的学号是公开信息和常用信息，容易获得。

然而，当不存储任何数据时，都可以找到与列表位置相关的信息。例如，存储所有的英语单词，不可能为每个英语单词编号，即使编号，编号只是这里的流量，没有数据意义的数据对用户不友好，没有人能记住哪个英语单词对应哪个数字。

因此，当使用列表存储英语单词时，由于没有单词的存储位置。它仍然需要使用，如线性、二分……此类查询算法的时间复杂性取决于使用查询算法的时间复杂性。

如果列表中存储的上述学生信息插入、删除……操作改变数据原始位置后，只能使用其他查询算法，因为学号和位置相关信息被破坏，无法达到常量级。

是否有一种方案可以最大限度地优化数据存储和查询？

通过以上分析，我们可以得出结论，为了提高查询速度，我们必须找到提高查询速度的方法数据与位置关联哈希表这就是核心思想。

哈希表引入了关键字概念，关键字可以认为是数据的别名。如上表所示，每个学生都可以得到一个别名，这就是关键字。

Tip： 这里的关键字是姓名的拼音缩写，关键字和数据相关性强，便于记忆和查询。

有了关键字后，再把关键字映射法是映射列表中的有效位置哈希表中最重要的概念哈希函数。

关键字它是一座桥，它与真实数据和哈希表中的位置有关。

关键字也可以是需要保存的数据本身。

哈希算法不同的数据决定了数据的最终存储位置哈希算法也与设计方案有关哈希表因此，哈希算法尤其重要。

下面将介绍几种常见的纵横比较 哈希算法设计方案。

Tip： 不管用什么哈希算法，都有根，哈希结果必须是一个数字，表示列表（哈希表）中的有效位置。也被称为哈希值。

使用哈希表存储数据时，关键字实际上，数字类型也可以是非数字类型，关键字可以是任何类型。这里先讨论一下关键字设计非数字类型哈希算法基本思路。

如前所述，它为每个学生提供了一个拼音缩写的名字关键字。

现在如何把关键字映射到列表有效位置？

在这里，拼音可以简单地看作是英文中的字母。首先计算每个字母在字母表中的位置，然后添加以获得数字。

使用上面的哈希思想对每个学生关键字进行哈希：

• zjl的哈希值为 26 10 12=48。
• llj的哈希值为 12 12 10=34。
• cl 的哈希值为 3 12=15。
• zxy的哈希值为 26 25 24=75。

前文说过哈希值它表示列表中数据的存储位置。现在假设一个理想的状态，学生的名字是 3 一个汉字，关键字也是 3 使用上面的字母哈希算法，最大的哈希值应该是zzz=26 26 26=78，这意味着至少应该提供一个长度 78的列表 。

如果现在只保存， 4 虽然只有名学生 4 名学生，因为不能保证学生关键字不出现zzz，因此，列表长度仍然需要 78。如下图所示。

[外链图片转存失败源站可能有防盗链机制,建议将图片保存下来直接上传(img-sY2XOwRg-1652143602408)(https://s2.51cto.com/images/20220510/1652143515926702.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)]

采用这种哈希算法会导致列表的空间浪费严重，最直观想法是对哈希值再做约束，如除以 4 再取余数，把哈希值限制在 4 之内，4 个数据对应 4 个哈希值。我们称这种取余数方案为取余数算法。

取余数法中，被除数一般选择小于哈希表长度的素数。本文介绍其它哈希算法时，也会使用取余数法对哈希值进行适当范围的收缩。

重新对 4 名学生的关键字进行哈希。

• zjl的哈希值为 26+10+12=48，48 除以 4 取余数，结果是0。
• llj的哈希值为 12+12+10=34，34 除以 4 取余数，结果是2。
• cl 的哈希值为 3+12=15，15 除以 4 取余数，结果是3。
• zzz的哈希值为 26+26+26=78，78 除以 4 取余数，结果是2。

演示图上出现了一个很奇怪的现象，没有看到李连杰的存储信息。

4个存储位置存储 4学生，应该是刚刚好，但是，只存储了 3名学生。且还有 1个位置是空闲的。现在编码验证一下，看是不是人为因素引起的。

''' 哈希函数 '''
def hash_code(key):
    # 设置字母 A 的在字母表中的位置是 1
    pos = 0
    for i in key:
        i = i.lower()
        res = ord(i) - ord('a') + 1
        pos += res
    return pos % 4

测试代码：

# 哈希表
hash_table = [None] * 4
# 计算关键字的哈希值
idx = hash_code('zjl')
# 根据关键字换算出来的位置存储数据
hash_table[idx] = '周杰伦'
idx = hash_code('llj')
hash_table[idx] = '李连杰'
idx = hash_code('cl')
hash_table[idx] = '成龙'
idx = hash_code('zzz')
hash_table[idx] = '张志忠'
print('哈希表中的数据：', hash_table)
''' 输出结果： 哈希表中的数据： ['周杰伦', None, '张志忠', '成龙'] '''

执行代码，输出结果，依然还是没有看到李连杰的信息。

原因何在？

这是因为李连杰和张志忠的哈希值都是 2 ，导致在存储时，后面存储的数据会覆盖前面存储的数据，这就是哈希中的典型问题，哈希冲突问题。

所谓哈希冲突，指不同的关键字在进行哈希算法后得到相同的哈希值，这意味着，不同关键字所对应的数据会存储在同一个位置，这肯定会发生数据丢失，所以需要提供算法，解决冲突问题。

Tip： 研究哈希表，归根结底，是研究如何计算哈希值以及如何解决哈希值冲突的问题。

针对上面的问题，有一种想当然的冲突解决方案，扩展列表的存储长度，如把列表扩展到长度为 8。

直观思维是：扩展列表长度，哈希值的范围会增加，冲突的可能性会降低。

''' 哈希函数 '''
def hash_code(key):
    # 设置字母 A 的在字母表中的位置是 1
    pos = 0
    for i in key:
        i = i.lower()
        res = ord(i) - ord('a') + 1
        pos += res
    return pos % 8

# 哈希表
hash_table = [None] * 8

# 保存所有学生
idx = hash_code('zjl')
hash_table[idx] = '周杰伦'
idx = hash_code('llj')
hash_table[idx] = '李连杰'
idx = hash_code('cl')
hash_table[idx] = '成龙'
idx = hash_code('zzz')
hash_table[idx] = '张志忠'
print('哈希表中的数据：', hash_table)
''' 输出结果： 哈希表中的数据： ['周杰伦', None, '李连杰', None, None, None, '张志忠', '成龙'] '''

貌似解决了冲突问题，其实不然，当试着设置列表的长度为6、7、8、9、10时，只有当长度为 8时没有发生冲突，这还是在要存储的数据是已知情况下的尝试。

如果数据是动态变化的，显然这种扩展长度的方案绝对不是本质解决冲突的方案。即不能解决冲突，且产生大量空间浪费。

如何解决哈希冲突，会在后文详细介绍，这里还是回到哈希算法上。

综上所述，我们对哈希算法的理想要求是：

• 为每一个关键字生成一个唯一的哈希值，保证每一个数据都有只属于自己的存储位置。
• 哈希算法的性能时间复杂度要低。

现实情况是，同时满足这 2 个条件的哈希算法几乎是不可能有的，面对数据量较多时，哈希冲突是常态。所以，只能是尽可能满足。

因冲突的存在，即使为 100 个数据提供 100 个有效存储空间，还是会有空间闲置。这里把实际使用空间和列表提供的有效空间相除，得到的结果，称之为哈希表的占有率（载荷因子）。

如上述，当列表长度为 4时， 占有率为 3/4=0.75，当列表长度为 8 时，占有率为 4/8=0.5，一般要求占率控制 在0.6~0.9之间。

前面在介绍什么是哈希算法时，提到了取余数法，除此之外，还有几种常见的哈希算法。

**折叠法：**将关键字分割成位数相同的几个部分（最后一部分的位数可以不同）然后取这几部分的叠加和（舍去进位）作为哈希值。

折叠法又分移位叠加和间界叠加。

• 移位叠加：将分割后的每一部分的最低位对齐，然后相加。

• 间界叠加：从一端沿分割线来回折叠，然后对齐相加。

因有相加求和计算，折叠法适合数字类型或能转换成数字类型的关键字。假设现在有很多商品订单信息，为了简化问题，订单只包括订单编号和订单金额。

现在使用用哈希表存储订单数据，且以订单编号为关键字，订单金额为值。

移位叠法换算关键字的思路：

**第一步：**把订单编号 20201011 按每3位一组分割，分割后的结果：202、010、11。

按 2 位一组还是 3 位一组进行分割，可以根据实际情况决定。

第二步： 把分割后的数字相加 202+010+11，得到结果：223。再使用取余数法，如果哈希表的长度为 10，则除以 10后的余数为3。

这里除以 10 仅是为了简化问题细节，具体操作时，很少选择列表的长度。

**第三步：**对其它的关键字采用相同的处理方案。

编码实现保存商品订单信息：

''' 移位叠加哈希算法 '''
def hash_code(key, hash_table_size):
    # 转换成字符串
    key_s = str(key)
    # 保存求和结果
    s = 0
    # 使用切片
    for i in range(0, len(key_s), 3):
        s += int(key_s[i:i + 3])
    return s % hash_table_size

# 商品信息
products = [[20201011, 400.00], [19981112, 300], [20221212, 200]]
# 哈希表长度
hash_size = 10
# 哈希表
hash_table = [None] * hash_size
# 以哈希表方式进行存储
for p in products:
    key = hash_code(p[0], hash_size)
    hash_table[key] = p[1]
# 显示哈希表中的数据
print("哈希表中的数据：",hash_table)
# 根据订单号进行查询
hash_val = hash_code(19981112, hash_size)
val = hash_table[hash_val]
print("订单号为{0}的金额为{1}".format(19981112, val))
''' 输出结果 哈希表中的数据： [None, None, 300, 400.0, None, None, 200, None, None, None] 订单号为19981112的金额为300 '''

间界叠加法：

间界叠加法，会间隔地把要相加的数字进行反转。

如订单编号 19981112 按3位一组分割，分割后的结果：199、811、12，间界叠加操作求和表达式为 199+118+12=339，再把结果 339 % 10=9。

编码实现间界叠加算法：

''' 间界叠加哈希算法 '''
def hash_code(key, hash_table_size):
    # 转换成字符串
    key_s = str(key)
    # 保存求和结果
    s = 0
    # 使用切片
    for i in range(0, len(key_s), 3):
        # 切片
        tmp_s = key_s[i:i + 3]
        # 反转
        if i % 2 != 0:
            tmp_s = tmp_s[::-1]
        s += int(tmp_s)
    return s % hash_table_size

# 商品信息（数据样例）
products = [[20201011, 400.00], [19981112, 300], [20221212, 200]]
# 哈希表长度
hash_size = 10
# 哈希表
hash_table = [None] * hash_size
# 以哈希表方式进行存储
for p in products:
    key = hash_code(p[0], hash_size)
    hash_table[key] = p[1]
# 显示哈希表中的数据
print("哈希表中的数据：", hash_table)
# 根据订单号进行查询
hash_val = hash_code(19981112, hash_size)
val = hash_table[hash_val]
print("订单号为{0}的金额为{1}".format(19981112, val))
''' 输出结果： 哈希表中的数据： [None, None, None, 400.0, None, None, 200, None, None, 300] 订单号为19981112的金额为300 '''

平方取中法：先是对关键字求平方，再在结果中取中间位置的数字。

求平方再取中算法，是一种较常见的哈希算法，从数学公式可知，求平方后得到的中间几位数字与关键字的每一位都有关，取中法能让最后计算出来的哈希值更均匀。

因要对关键字求平方，关键字只能是数字或能转换成数字的类型，至于关键字本身的大小范围限制，要根据使用的计算机语言灵活设置。

如下面的图书数据，图书包括图书编号和图书名称。现在需要使用哈希表保存图书信息，以图书编号为关键字，图书名称为值。

使用平方取中法计算关键字的哈希值：

**第一步：**对图书编号 58 求平方，结果为 3364。

第二步：取 3364的中间值36，然后再使用取余数方案。如果哈希表的长度为 10，则 36%10=6。

**第三步：**对其它的关键字采用相同的计算方案。

编码实现平方取中算法：

''' 哈希算法 平方取中 '''
def hash_code(key, hash_table_size):
    # 求平方
    res = key ** 2
    # 取中间值，这里取中间 2 位（简化问题）
    res = int(str(res)[1:3])
    # 取余数
    return res % hash_table_size

hash_table_size = 10
hash_table = [None]*hash_table_size
# 图书信息
books = [[58, "python 从入门到精通"], [67, "C++ STL"], [78, "Java 内存模型"]]
for b in books:
    hash_val = hash_code(b[0],hash_table_size)
    hash_table[hash_val]=b[1]

# 显示哈希表中的数据
print("哈希表中的数据：", hash_table)
# 根据编号进行查询
hash_val = hash_code(67, hash_table_size)
val = hash_table[hash_val]
print("编号为{0}的书名为{1}".format(67, val))

上述求平方取中间值的算法仅针对于本文提供的图书数据，如果需要算法具有通用性，则需要根据实际情况修改。

不要被 取中的中字所迷惑，不一定是绝对中间位置的数字。

直接地址法：提供一个与关键字相关联的线性函数。如针对上述图书数据，可以提供线性函数 f(k)=2*key+10。

系数2和常数10的选择会影响最终生成的哈希值的大小。可以根据哈希表的大小和操作的数据含义自行选择。

key 为图书编号。当关键字不相同时，使用线性函数得到的值也是唯一的，所以，不会产生哈希冲突，但是会要求哈希表的存储长度比实际数据要大。

这种算法在实际应用中并不多见。

实际应用时，具体选择何种哈希算法，完全由开发者定夺，哈希算法的选择没有固定模式可循，虽然上面介绍了几种算法，只是提供一种算法思路。

哈希冲突是怎么引起的，前文已经说过。现在聊聊常见的几种哈希冲突解决方案。

当发生哈希冲突后，会在冲突位置之后寻找一个可用的空位置。如下图所示，使用取余数哈希算法，保存数据到哈希表中。

哈希表的长度设置为 15，除数设置为 13。

解决冲突的流程：

1. 78和26的哈希值都是 0。而因为78在26的前面，78先占据哈希表的 0位置。

2. 当存储 26时，只能以 0位置为起始位置，向后寻找空位置，因 1位置没有被其它数据占据，最终保存在哈希表的1位置。

3. 当存储数字 14时，通过哈希算法计算，其哈希值是1，本应该要保存在哈希表中1的位置，因1位置已经被26所占据，只能向后寻找空位置，最终落脚在2位置。

线性探测法让发生哈希冲突的数据保存在其它数据的哈希位置，如果冲突的数据较多，则占据的本应该属于其它数据的哈希位置也较多，这种现象称为哈希聚集。

查询流程：

以查询数据14为例。

1. 计算 14的哈希值，得到值为 1 ，根据哈希值在哈希表中找到对应位置。
2. 查看对应位置是否存在数据，如果不存在，宣告查询失败，如果存在，则需要提供数据比较方法。
3. 因 1位置的数据 26并不等于14。于是，继续向后搜索，并逐一比较。
4. 最终可以得到结论14在哈希表的编号为2的位置。

所以，在查询过程中，除了要提供哈希函数，还需要提供数据比较函数。

删除流程：

以删除数字26为例。

1. 按上述的查询流程找到数字26在哈希表中的位置1。

2. 设置位置1为删除状态，一定要标注此位置曾经保存过数据，而不能设置为空状态。为什么？

   如果设置为空状态，则在查询数字14时，会产生错误的返回结果，会认为 14不存在。为什么？自己想想。

编码实现线性探测法：

添加数据：

''' 线性探测法解决哈希冲突 '''
def hash_code(key, hash_table, num):
    # 哈希表的长度
    size = len(hash_table)
    # 取余数法计算哈希值
    hash_val = key % num
    # 检查此位置是否已经保存其它数据
    if hash_table[hash_val] is not None:
        # 则从hash_val 之后寻找空位置
        for i in range(hash_val + 1, size + hash_val):
            if i >= size:
                i = i % size
            if hash_table[i] is None:
                hash_val = i
                break
    return hash_val

# 哈希表
hash_table = [None] * 15
src_nums = [25, 78, 56, 32, 88, 26, 73, 81, 14]
for n in src_nums:
    hash_val = hash_code(n, hash_table, 13)
    hash_table[hash_val] = n

print("哈希表中的数据：", hash_table)
''' 输出结果： 哈希表中的数据： [78, 26, 14, 81, 56, None, 32, None, 73, None, 88, None, 25, None, None] '''

**Tip：**为了保证当哈希值发生冲突后，如果从冲突位置查到哈希表的结束位置还是没有找到空位置，则再从哈希表的起始位置，也就是 0 位置再搜索到冲突位置。冲突位置是起点也是终点，构建一个查找逻辑环，以保证一定能找到空位置。

for i in range(hash_val + 1, size + hash_val):
	 pass

基于线性探测的数据查询过程和存储过程大致相同：

def get(key, hash_table, num):
    # 哈希表的长度
    size = len(hash_table)
    # 取余数法计算哈希值
    hash_val = key % num
    is_exist = False
    # 检查此位置是否已经保存其它数据
    if hash_table[hash_val] is None:
        # 不存在
        return None
    if hash_table[hash_val] != key:
        # 则从hash_val 之后寻找空位置
        for i in range(hash_val + 1, size + hash_val):
            if i >= size:
                i = i % size
            if hash_table[i] == key:
                hash_val = i
                is_exist = True
                break
    else:
        is_exist=True
    if is_exist:
        return hash_val

# 测试 
res = get(25, hash_table, 13)
print(res)

为了减少数据聚集，可以采用增量线性探测法，所谓增量指当发生哈希冲突后，探测空位置时，使用步长值大于 1的方式跳跃式向前查找。目的是让数据分布均匀，减小数据聚集。

除了采用增量探测之外，还可以使用再哈希的方案。也就是提供 2 个哈希函数，第 1 次哈希值发生冲突后，再调用第 2 个哈希函数再哈希，直到冲突不再产生。这种方案会增加计算时间。

上面所述的冲突解决方案的核心思想是，当冲突发生后，在哈希表中再查找一个有效空位置。

这种方案的优势是不会产生额外的存储空间，但易产生数据聚集，会让数据的存储不均衡，并且会违背初衷，通过关键字计算出来的哈希值并不能准确描述数据正确位置。

链表法应该是所有解决哈希冲突中较完美的方案。所谓链表法，指当发生哈希冲突后，以冲突位置为首结点构建一条链表，以链表方式保存所有发生冲突的数据。如下图所示：

链表方案解决冲突，无论在存储、查询、删除时都不会影响其它数据位置的独立性和唯一性，且因链表的操作速度较快，对于哈希表的整体性能都有较好改善。

使用链表法时，哈希表中保存的是链表的首结点。首结点可以保存数据也可以不保存数据。

编码实现链表法：链表实现需要定义 2 个类，1 个是结点类，1 个是哈希类。