一文详解Python中哈希表的使用_python_

1. 前言

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

哈希表属于抽象数据结构，需要开发者按哈希表数据结构的存储要求进行API定制，对于大部分高级语言而言，都会提供已经实现好的、可直接使用的API，如JAVA中有MAP集合、C++中的MAP容器，Python中的字典……

使用者可以使用API中的方法完成对哈希表的增、删、改、查……一系列操作。

如何学习哈希表？

可以从2个角度开始：

• 使用者角度：只需要知道哈希表是基于键、值对存储的解决方案，另需要熟悉不同计算机语言提供的基于哈希表数据结构的 API实现，学会使用 API中的方法。
• 开发者的角度：则需要知道哈希表底层实现原理，以及实现过程中需要解决的各种问题。本文将站在开发者的角度，带着大家一起探究哈希的世界。

2. 哈希表

什么是哈希表？

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

大家都知道，基于列表（数组）的查询速度非常快，时间复杂度是O（1），常量级别的。

列表的底层存储结构是连续的内存区域，只要给定数据在列表（数组）中的位置，就能直接查询到数据。理论上是这么回事，但在实际操作过程，查询数据的时间复杂度却不一定是常量级别的。

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

这里把学生的学号和列表的索引号进行关联，查询某一个学生时，知道了学生的学号也就知道了学生数据存储在列表中的位置，可以认为查询的时间复杂度为O(1)。

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

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

但是，不是存储任何数据时，都可以找到与列表位置相关联的信息。比如存储所有的英文单词，不可能为每一个英文单词编号，即使编号了，编号在这里也仅仅是流水号，没有数据含义的数据对于使用者来讲是不友好，谁也无法记住哪个英文单词对应哪个编号。

所以使用列表存储英文单词后需要询时，因没有单词的存储位置。还是需要使用如线性、二分……之类的查询算法，这时的时间复杂度由使用的查询算法的时间复杂度决定。

如果对上述存储在列表的学生信息进行了插入、删除……等操作，改变了数据原来的位置后，因破坏了学号与位置关联信息，再查询时也只能使用其它查询算法，不可能达到常量级。

是否存在一种方案，能最大化地优化数据的存储和查询？

通过上述的分析，可以得出一个结论，要提高查询的速度，得想办法把数据与位置进行关联。而哈希表的核心思想便是如此。

2.1 哈希函数

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

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

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

关键字是一个桥梁，即关联到真正数据又关联到哈希表中的位置。

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

哈希函数的功能：提供把关键字映射到列表中的位置算法，是哈希表存储数据的核心所在。如下图，演示数据、哈希函数、哈希表之间的关系，可以说哈希函数是数据进入哈希表的入口。

数据最终会存储在列表中的哪一个位置，完全由哈希算法决定。

当需要查询学生数据时，同样需要调用哈希函数对关键字进行换算，计算出数据在列表中的位置后就能很容易查询到数据。

如果忽视哈希函数的时间复杂度，基于哈希表的数据存储和查询时间复杂度是 O(1)。

如此说来哈希函数算法设计的优劣是影响哈希表性能的关键所在。

2.2 哈希算法

哈希算法决定了数据的最终存储位置，不同的哈希算法设计方案，也关乎哈希表的整体性能，所以，哈希算法就变得的尤为重要。

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

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。如下图所示。

采用这种哈希算法会导致列表的空间浪费严重，最直观想法是对哈希值再做约束，如除以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之间。

2.3 常见哈希算法

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

2.3.1 折叠法

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

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

• 移位叠加：将分割后的每一部分的最低位对齐，然后相加。
• 间界叠加：从一端沿分割线来回折叠，然后对齐相加。

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

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

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

第一步：把订单编号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 ''' 

2.3.2 平方取中法

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

求平方再取中算法，是

提示： 本文由神整理自网络，如有侵权请联系本站删除！
本站声明：
1、本站所有资源均来源于互联网，不保证100%完整、不提供任何技术支持；
2、本站所发布的文章以及附件仅限用于学习和研究目的;不得将用于商业或者非法用途；否则由此产生的法律后果，本站概不负责！