如何构建Python哈希函数2025年1月4日 | 阅读 19 分钟 哈希表是一个众所周知的数据库结构，已被证明是编程的基本要素，其发明至今已有半个多世纪。即使在今天，它仍然可以解决各种实际问题，这些问题需要索引数据库表、缓存计算值，甚至实现集合。它在工作面试中也经常被讨论，因为 Python 在各种地方使用哈希表来几乎即时地搜索名称。 虽然 Python 本身就带有哈希表（称为“dict”），但了解哈希表在后台的运作方式仍然很有用。代码评估可能会要求我们构建一个。本教程将从头开始，带您完成构建哈希表的过程，就好像 Python 中不存在一样。在此过程中，我们将面临一些挑战，这些挑战将解释基本概念，并让我们理解为什么哈希表速度很快。 了解哈希表数据结构在我们深入研究之前，我们必须确保熟悉使用的术语，因为它们有时有点令人困惑。在本节中，“哈希表”或“哈希映射”一词经常与“字典”一词互换使用。这两个概念之间有细微的区别，因为前者比后者更具体。 哈希表与字典在计算机科学领域，“字典”是一个在计算机科学中使用的术语。“字典”是一种抽象数据类型，由键元素和值组成，按对放置。此外，它为其中包含的元素定义了以下操作：
在某种程度上，这种数据类型类似于“双语词典”，其中关键词是外来词，值是定义和不同语言的翻译。然而，键和值之间不必有等价的概念。例如，电话簿是字典的另一个实例，它将姓名和电话号码组合在一起。 字典是信息的绝佳来源。它们具有几个有趣的特征。其中之一是能够将字典视为一个数学函数，该函数为一个或两个参数分配一个且仅一个值。该事实的直接结果是：
其他概念可以扩展到字典的概念。例如，“多值映射”允许用户为每个键拥有多个值。但是，双向映射不仅仅是将键转换为值，还允许反向映射。本指南将研究标准的字典，它为每个键分配一个且仅一个值。 这是字典的一个可能映射抽象概念与相应英语单词的图形表示。  它是一对一的键值映射，键和值是两种不同类型的组件。由于“bow”这个词是多义词，有多种含义，因此我们发现值比键少。然而，字典有四对值。根据我们选择的方法，我们可以重复使用值来节省内存，或者复制值以简化。 我们如何用编程语言创建字典？答案是我们不这样做，因为大多数现代语言都将字典函数作为基本数据类型，或者将其作为标准类库的一部分。Python 带有内置的字典类型，它已经封装了一个用C编写的高度优化的数据结构，这样我们就不需要编写自己的字典。 Python 的字典允许我们执行本文开头描述的所有与字典相关的操作。 代码 输出 'air bat car' 输入 输出 {'abc': 'air bat car'}
使用方括号语法（[]），我们可以向字典添加新的键值对。我们还可以更改由键标识的现有对的值。我们还可以确定与键关联的值。 然而，我们可能会提出一个不同的问题。内置字典是什么？它是如何工作的？将键映射到各种不同数据类型的过程是什么，它是如何如此快速地完成的？ 实现这种抽象数据类型被称为“字典问题”。最流行的解决方案是使用我们即将探讨的哈希表数据结构。但是请记住，这并不是普遍创建字典的唯一选择。另一种流行的方法是基于红黑树。 哈希表：带哈希函数的数组用户可能曾想过，为什么在 Python 中访问序列元素的过程如此之快，而不管他们请求的索引是什么？如果用户处理的是一个非常长的字符序列，例如 输出 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABC' 输入 输出 2600000000 上面文本中重复的ASCII字母派生出的字符估计有 26 亿个，我们可以使用 Python 的len()函数来计算。但是，查找字符串中的第一个、中间、最后一个以及任何其他字符同样容易。 输入 输出 'A' 输入 输出 'A' 输入 输出 'Z' 对于 Python 中可用的任何类型的序列（包括列表和元组），情况也是如此。原因是什么？如此快的速度的原因是 Python 的序列。Python 支持数组，这是一个随机访问信息结构。它遵循两个基本原则：
如果我们知道数组中的内存地址（也称为“偏移量”），则可以通过简单的公式快速定位数组中所需的元素。  以上是计算序列元素内存地址的公式。 数组从其偏移量开始。这是一个地址，是第一个元素，从零开始。之后，我们通过添加所需的字节数来前进，这些字节数可以通过将元素的大小乘以元素的索引来获得。加几个数字总是需要相同的时间。  我们知道如何快速定位数组中的项，无论元素在物理位置上的实际位置如何。我们能否使用相同的概念并将其应用于字典？是的！ 哈希表因一种称为哈希的方法而得名，该方法允许它们将任何键转换为整数，该整数可以用作普通数组中的索引。因此，我们不必使用数字索引搜索特定值，而是可以使用任意键进行搜索，而不会有明显的性能下降。这很酷！ 实际上，哈希与每个键都不兼容。但是，Python 中的大多数内置类型都可以进行哈希。如果我们遵守一些规则，我们也可以创建自己的可哈希类型。在下一节中学习如何哈希。 理解哈希函数哈希函数是一种哈希方法，它将任何数据转换为固定的字节序列，称为“哈希值或哈希码”。它是一个数字，可以作为指纹或摘要，通常比文件大，允许我们检查其真实性。例如，如果您曾经从互联网上下载过大型文件（例如 Linux 发行版的磁盘映像），您可能在下载页面上看到过 MD5 或 SHA-2 校验和。 除了确认数据完整性和解决字典问题之外，哈希函数还可以用于其他领域，例如安全和加密。例如，我们通常将哈希后的密码存储在数据库中，以减少信息泄露的可能性。数字签名使用哈希在加密前创建加密的消息摘要。区块链交易是另一个利用哈希函数进行安全目的的绝佳例子。 尽管有各种哈希算法，但它们都具有相同的特征，将在下面讨论。正确实现可靠的哈希函数是一项艰巨的任务，可能需要对涉及素数的复杂数学有深入的掌握。幸运的是，我们不需要手动实现这种算法。 Python 有一个内置的hashlib模块，它提供了许多流行的加密哈希函数以及更安全的校验和算法。它还带有一个通用的hash()函数，用于在集合和字典中执行快速元素搜索。我们可以学习它的工作原理来理解哈希函数最显著的特点。 如何检查 Python 的内置 hash()在您尝试从头开始创建哈希函数之前，您应该研究 Python 的hash()以提炼其特性。这将使您能够理解创建自己的哈希函数所涉及的挑战。 尝试在 Python 中包含的一些数据类型文字（如字符串和数字）上调用 hash() 函数，以测试会发生什么。 输入 输出 322818021289917443 输入 输出 326490430436040707 输入 输出 -3852290318913306444 输入 输出 8945776761251421587 我们可以从结果中学到很多东西。首先，内置的哈希函数可能会为我们上面提到的一些输入给出不同的结果。虽然数字输入似乎返回相同的哈希值，但字符串可能不会。原因是什么？这可能看起来是hash()是一个非确定性函数，但事实并非如此！ 如果我们使用相同的参数在当前解释器会话中运行 hash()，我们将获得相同的结果。 输入 输出 -3852290318913306444 输入 输出 -3852290318913306444 输入 输出 -3852290318913306444 这是因为哈希值是不可变的，并且在对象的生命周期内永远不会改变。但是，如果我们退出 Python 并重新启动，我们将观察到不同 Python 执行之间的哈希值不同。可以通过使用-c选项在终端中执行以下单行程序来测试这一点。  这是正常行为。它已被实现到 Python 中，作为一种对抗拒绝服务 (DoS) 攻击的措施，该攻击利用了 Web 服务器上哈希算法已知的安全漏洞。攻击者可以利用不安全的哈希算法故意创建哈希冲突，导致服务器过载并使其无法访问。赎金是这种攻击的常见动机，因为大多数受害者通过持续的在线存在来赚钱。 如今，Python 为包括字符串在内的某些输入启用了哈希随机化作为默认功能，这使得哈希值更难预测。这使得 hash() 更安全，攻击更困难。可以禁用随机化；但是，我们可以使用PYTHONHASHSEED环境变量设置固定的种子值，例如： 输入 输出 3248502820309220970 输入 输出 3248502820309220970 输入 输出 3248502820309220970 总的来说，Python 的hash()函数确实是一个确定性函数，并且是该函数的基本特征之一。每次 Python 执行都会生成一个已知的输入的确切哈希值。这有助于在分散的 Python 解释器数组之间拆分或共享数据。请小心并注意关闭哈希随机化所带来的风险。 此外，hash()似乎相当通用，因为它接受任何输入。也就是说，它可以接受不同大小和类型的数值。该程序可以毫无问题地处理字符串和浮点数，而不管它们的大小或长度。也可以计算更晦涩类型的哈希值。 输入 输出 -9223363242224569907 输入 输出 8652138113829 输入 输出 145274959535 输入 输出 145274845263 输入 输出 145274845224 在这里，我们调用 Python 的none对象的哈希函数，并使用 hash() 函数本身以及一个类，该类有几个实例。但是有些对象没有相同的哈希值。如果我们尝试对其中一个对象调用 hash() 函数，它可能会生成一个错误。 输入 Error Traceback (most recent call last): File " 输入的类型可以决定我们是否能够计算哈希值。在 Python 中，内置可变类型的实例（如资产、列表和字典）是不可哈希的。这有一些原因的提示，但我们将在下一节中详细了解。同时，可以安全地假设大多数数据类型通常都可以与哈希算法一起使用。 深入了解 Python 的 hash()另一个有趣的特性是hash()总是生成固定大小的值，而不管我们的输入大小如何。在 Python 中，这是一个中等大小的整数。它可能显示为负数，因此如果我们打算以任何方式依赖哈希值，我们必须考虑到这一点。 输入 输出 9052257963471308498 生成标准大小输出的正常结果是，原始数据的很大一部分会永久丢失。这没关系，因为我们最终希望最终的哈希值成为大量数据的统一摘要。但是，由于哈希函数可能将无限数量的值投影到未定义空间中，因此可能导致哈希冲突，即两个输入创建相同的值。 哈希冲突是哈希表中的一个重要概念，当我们在未来创建自定义哈希表时，我们将有机会更详细地重新讨论它。在此期间，我们可以认为它们是高度不可取的。请在任何情况下避免与哈希键的冲突，因为它们可能导致查找效率低下，并且黑客可能会利用它们。因此，安全的哈希函数应尽量减少冲突的可能性，以确保安全性和有效性。 我们可以通过在终端上绘制文本直方图来查看 Python 的 hash() 函数生成的值的分布。这意味着 hash 函数必须在空间中分配均匀分布的值。用户可以复制以下代码块并将其保存到一个名为 hash_distribution.py 的文件中。 它使用计数器实例轻松描绘给定项的哈希值直方图。哈希数通过模数运算符包裹在指定数量的容器中进行分布。然后，我们可以选择一百个打印的 ASCII 字符作为示例，然后确定它们的哈希值并显示它们的分布。 输出 0 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ (56) 1 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ (44) 输入 输出 0 ■■■■■■■■■■■■■■■■■■■■ (20) 1 ■■■■■■■■■■■■■■ (14) 2 ■■■■■■■■■■■■■■■■■■■■■■■■ (24) 3 ■■■■■■■■■■■■■■■■■■■ (19) 4 ■■■■■■■■■■■■■■■■■■■■■■■ (23) 正如我们所观察到的，使用内置的hash()函数效果相当好，但分布并不理想。如果只有两个容器，则预计分布约为 50-50。如果添加更多容器，它们将填充得或多或少相等。 因此，哈希值的常规分布通常是伪随机的，在密码学函数中尤其重要。这可以阻止潜在的攻击者使用统计分析来识别输入和函数输出之间的关系。考虑更改字符串中的单个字母，看看它如何影响 Python 中哈希值的最终结果。 输入 输出 9052257963471308498 输入 输出 8158704031393424069 这是一个不同的哈希值，即使只有一个字母不同。哈希值经常容易受到雪崩效应的影响，这意味着即使输入最微小的变化也会被放大。然而，哈希函数中的这一点对于实现哈希表数据结构来说并不是必需的。 在大多数情况下，Python 的hash()表现出加密哈希函数的另一个非必需的特征，这是由于前面提到的鸽巢原理。它是一个单向操作，因为在大多数情况下，几乎不可能找到它的逆运算。但是，有一些值得注意的例外情况。 输入 输出 47 小整数的哈希值与其值相同，这是CPython实现的设计方面，旨在确保简单性和有效性。请记住，在我们可以精确计算它们的情况下，实际的哈希值并不重要。 使用 Python 计算哈希号非常快，即使是大型输入。现代计算机使用hash()，将一个包含超过 1 亿个字符的字符串作为参数，并会立即返回结果。如果它不够快，那么计算哈希值的附加成本将抵消最初哈希处理的优势。 如何识别哈希函数属性根据我们从 Python 的 hash() 函数收集的信息，我们现在可以决定哈希函数的一般期望属性。下面是一个可用功能的列表，它比较了普通哈希函数与其加密版本。  两个哈希函数的目标相似，并且在特征方面有许多相似之处。相比之下，加密哈希函数提供了额外的安全保证。 在创建自己的哈希函数之前，您将需要查看 Python 中的另一个内置函数，该函数似乎是最简单的替代方案。 如何比较对象的身份与其哈希值也许 Python 中最简单的哈希函数实现之一是内置的id()，它提供了对象的身份。在正常的 Python 解释器中，身份与对象的内存地址相同，表示为整数。 输入 输出 2324401272432 id()函数拥有所有期望的哈希函数属性。最终，它非常高效，并且无论输入如何都能正常工作。它可预测地返回一个固定大小的整数。然而，无法从内存地址访问原始对象。内存地址在对象的生命周期内保持不变，并且在解释器运行之间也会随机生成。 那么，为什么 Python 坚持使用不同的方法进行哈希处理呢？ 首先需要注意的是，id()的目的与hash()不同，因此不同的 Python 发行版可以以不同的方式实现身份。此外，内存地址是已知的，并且没有均匀的分布。此外，相同的对象通常会生成相同的哈希码，即使它们具有不同的身份。这既不安全也不足以进行哈希处理。 如何制作我们自己的哈希函数创建满足所有要求的哈希函数并不容易。但是，尝试从头开始创建哈希函数是了解其工作原理的绝佳方法。完成本教程后，我们将拥有一个基本的哈希函数，它并不完美。然而，我们将获得重要的知识。 在这种情况下，我们可以首先将自己限制在一种数据类型，然后使用哈希函数。例如，我们可以查看字符串，然后对字符串中的字符的序数值求和。 我们使用生成器重复文本，然后使用其内置的ord()函数将每个字符转换为相应的 Unicode 代码点，以添加序数值。结果将是为作为参数提供的每个给定文本生成一个数字。 输入 输出 511 输入 输出 512 输入 输出 512 我们很快就会注意到这种方法的一些问题。它不仅是字符串特定的，而且它还遭受哈希码分布不均的问题，倾向于创建具有相同输入值的集群。对输入进行的任何微小修改都不会影响输出。更重要的是，该函数对文本中的字符顺序不敏感。这就是为什么同一个单词的变位词，例如 Loner 和 Loner，可能会在哈希代码中产生冲突。 为了解决这个问题，尝试使用str()调用将输入转换为 Unicode 字符串。现在我们的函数应该可以处理任何参数。 输入 输出 512 输入 输出 197 输入 输出 491 我们可以使用任何数据（如字符串、浮点数、布尔值）的参数调用hash_function()。 此实现仅相当于字符串的表示。某些对象可能没有与下面的代码匹配的表示。特别是，没有正确实现特定 .__str__() 和 .__repr__() 方法的类的自定义实例就是一个很好的例子。此外，无法区分不同类型的数据。 输入 输出 197 输入 输出 197 实际上，我们希望将“3.14”和浮点数 3.14 视为不同的对象，每个对象都有不同的哈希码。一种减少问题的方法是将str()替换为repr()，它通过添加一个额外的撇号（'）来包装字符串的表示形式。 输入 输出 "197" 输入 输出 '197' 这将会在一定程度上改进我们的哈希函数。 输入 输出 275 输入 输出 197 字符串现在与数字区分开来。为了解决像 Loren 和 Loner 这样的变位词问题，我们可以修改我们的哈希函数，使其考虑文本中字符的值和位置。 在这里，我们计算通过将字符的序数值与其索引相乘而产生的乘积的总和。请注意，我们必须从一开始列出索引，而不是从零开始。否则，第一个字符将被始终忽略，因为它的值将被零除。 我们的哈希函数非常通用，并且不像以前那样产生更多冲突，但是输出可能会很大，因为字符串越长，哈希算法就越复杂。此外，在输入大量数据时它非常慢。 输入 输出 1677 输入 输出 38150 输入 输出 66139005681000117 我们可以通过对我们的哈希码（%）取一个指定的最大值（例如 100）模数来解决无界增长的问题。 输入 输出 77 输入 输出 50 输入 输出 17 如果我们不确定在做决定之前有多少输入值，最好将其推迟到以后。确保选择较少数量的哈希码将增加哈希码之间发生冲突的可能性。我们也可以使用一个合理的最大值（如sys.maxsize，Python 原生支持的最大整数）来限制我们使用的哈希码。 如果我们暂时忽略函数性能缓慢的问题，我们会发现另一个不同寻常的问题。这会导致哈希码的分布不理想，通过集群和未充分利用可用插槽。 输入 输出 0 ■■■■■■■■■■■■■■■ (15) 1 ■■■■■■■■■■■■■■ (14) 2 ■■■■■■■■■■■■■■■ (15) 3 ■■■■■■■■■■■■■ (13) 4 ■■■■■■■■■■■■■■ (14) 5 ■■■■■■■■■■■■■■ (14) 6 ■■■■■■■■■■■■■■■ (15) 容器的分布不均匀。此外，确实有7个容器可供选择，其中一个在直方图中没有显示。这是因为为repr()创建的两个撇号导致几乎所有的键（在本例中）产生偶数哈希数。可以通过删除前导撇号（如果存在）来避免此问题。 输入 输出 (396, 398, 400) 输入 输出 (198, 199, 200) 输入 输出 0 ■■■■■■■■■■■■■■■ (15) 1 ■■■■■■■■■■■■■■■ (15) 2 ■■■■■■■■■■■■■ (13) 3 ■■■■■■■■■■■■■■■ (15) 4 ■■■■■■■■■■■■■■ (14) 5 ■■■■■■■■■■■■■ (13) 6 ■■■■■■■■■■■■■■■ (15) str.lstrip()方法仅在字符串以指定的字符串作为前缀时才会影响该字符串。 当然，我们还可以选择将我们的哈希函数提升到一个新的水平。如果您有兴趣在 Python 中实现字符串和字节的hash()，当前的实现使用SipHash。如果前者不可用，SipHash 算法可能会切换到 FNV 的替代变体。要确定 Python 解释器选择了使用哪种算法，请参阅此系统模块。 输入 输出 'siphash24' 结论完成本教程后，您将对哈希函数的工作原理、其预期性能以及在实现它时将面临的挑战有一个很好的理解。 下一个主题Python 中的 Yield 关键字 |
我们请求您订阅我们的新闻通讯以获取最新更新。
我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Python
Java
JavaScript
SQL
C
C++
HTML
CSS
React
Node.js
Spring Boot
C#
PHP
MySQL
MongoDB
AI
ML
DSA
DBMS
OS
Aptitude
Reasoning