当前位置：首页 > 科技 > 软件

Python 哈希表的实现——字典

来源：责编：时间：2023-11-28 09:37:23 185观看

导读哈喽大家好，我是咸鱼接触过 Python 的小伙伴应该对【字典】这一数据类型都了解吧虽然 Python 没有显式名称为“哈希表”的内置数据结构，但是字典是哈希表实现的数据结构在 Python 中，字典的键（key）被哈希，哈希值决定了键对

哈喽大家好，我是咸鱼

接触过 Python 的小伙伴应该对【字典】这一数据类型都了解吧

虽然 Python 没有显式名称为“哈希表”的内置数据结构，但是字典是哈希表实现的数据结构

在 Python 中，字典的键（key）被哈希，哈希值决定了键对应的值（value）在字典底层数据存储中的位置

那么今天我们就来看看哈希表的原理以及如何实现一个简易版的 Python 哈希表

ps：文中提到的 Python 指的是 CPyhton 实现

何为哈希表（hash table）

哈希表（hash table）通常是基于“键-值对”存储数据的数据结构

哈希表的键（key）通过哈希函数转换为哈希值（hash value），这个哈希值决定了数据在数组中的位置。这种设计使得数据检索变得非常快

举个例子，下面有一组键值对数据，其中歌手姓名是 key，歌名是 value

图片

如果我们想要将这些键值对存储在哈希表中，首先需要将键的值转换成哈希表的数组的索引，这时候就需要用到哈希函数了

哈希函数是哈希表实现的主要关键，它能够处理键然后返回存放数据的哈希表中对应的索引

一个好的哈希函数能够在数组中均匀地分布键，尽量避免哈希冲突（两个键返回了相同的索引）

图片

哈希函数是如何处理键的，这里我们创建一个简易的哈希函数来模拟一下（实际上哈希函数要比这复杂得多）

图片

这个简易版哈希函数将歌手名（即 key）首字母的 ASCII 值与哈希表大小取余，得出来的值就是歌名（value）在哈希表中的索引

那这个简易版哈希函数有什么问题呢？聪明的你一眼就看出来了：容易出现碰撞。因为不同的键的首字母有可能是一样的，就意味着返回的索引也是一样的

例如我们假设哈希表的大小为 10 ，我们以上面的歌手名作为键然后执行 simple_hash(key, 10) 得到索引

图片

可以看到，由于Juice WRLD 和 J.cole 的首字母都一样，哈希函数返回了相同的索引，这里就发生了哈希碰撞

虽然几乎不可能完全避免任何大量数据的碰撞，但一个好的哈希函数加上一个适当大小的哈希表将减少碰撞的机会

当出现哈希碰撞时，可以使用不同的方法（例如开放寻址法）来解决碰撞

应该设计健壮的哈希函数来尽量避免哈希碰撞

我们再来看其他的键，Kanye 通过 simple_hash() 函数返回 index 5，这意味着我们可以在索引 5 （哈希表的第六个元素）上找到其键 Kanye 和值Come to life

图片

哈希表优点

在哈希表中，是根据哈希值（即索引）来寻找数据，所以可以快速定位到数据在哈希表中的位置，使得检索、插入和删除操作具有常数时间复杂度 O(1) 的性能

与其他数据结构相比，哈希表因其效率而脱颖而出

不但如此，哈希表可以存储不同类型的键值对，还可以动态调整自身大小

Python 中的哈希表实现

在 Python 中有一个内置的数据结构，它实现了哈希表的功能，称为字典

Python 字典（dictionary，dict）是一种无序的、可变的集合（collections），它的元素以 “键值对（key-value）”的形式存储

字典中的 key 是唯一且不可变的，这意味着它们一旦设置就无法更改

图片

在底层，Python 的字典以哈希表的形式运行，当我们创建字典并添加键值对时，Python 会将哈希函数作用于键，从而生成哈希值，接着哈希值决定对应的值将存储在内存的哪个位置中

所以当你想要检索值时，Python 就会对键进行哈希，从而快速引导 Python 找到值的存储位置，而无需考虑字典的大小

图片

可以看到，我们通过方括号[key]来访问键对应的值，如果键不存在，则会报错

图片

为了避免该报错，我们可以使用字典内置的 get() 方法，如果键不存在则返回默认值

图片

在 Python 中实现哈希表

首先我们定义一个 HashTable 类，表示一个哈希表数据结构

图片

在构造函数 __init__() 中：

size 表示哈希表的大小
table是一个长度为 size 的数组，被用作哈希表的存储结构。初始化时，数组的所有元素都被设为 None，表示哈希表初始时不含任何数据

在内部函数 _hash() 中，用于计算给定 key 的哈希值。它采用给定键 key 的第一个字符的 ASCII 值，并使用取余运算 % 将其映射到哈希表的索引范围内，以便确定键在哈希表中的存储位置。

然后我们接着在 HashTable 类中添加对键值对的增删查方法

图片

其中，set() 方法将键值对添加到表中，而 get() 该方法则通过其键检索值。该 remove() 方法从哈希表中删除键值对

现在，我们可以创建一个哈希表并使用它来存储和检索数据：

图片

前面我们提到过，哈希碰撞是使用哈希表时不可避免的一部分，既然 Python 字典是哈希表的实现，所以也需要相应的方法来处理哈希碰撞

在 Python 的哈希表实现中，为了避免哈希冲突，通常会使用开放寻址法的变体之一，称为“线性探测”（Linear Probing）

当在字典中发生哈希冲突时，Python 会使用线性探测，即从哈希冲突的位置开始，依次往后查找下一个可用的插槽（空槽），直到找到一个空的插槽来存储要插入的键值对。

这种方法简单直接，可以减少哈希冲突的次数。但是，它可能会导致“聚集”（Clustering）问题，即一旦哈希表中形成了一片连续的已被占用的位置，新元素可能会被迫放入这片区域，导致哈希表性能下降

为了缓解聚集问题，假若当哈希表中存放的键值对超过哈希表长度的三分之二时（即装载率超过66%时），哈希表会自动扩容

最后总结一下：

在哈希表中，是根据哈希值（即索引）来寻找数据，所以可以快速定位到数据在哈希表中的位置
Python 的字典以哈希表的形式运行，当我们创建字典并添加键值对时，Python 会将哈希函数作用于键，从而生成哈希值，接着哈希值决定对应的值将存储在内存的哪个位置中
Python 通常会使用线性探测法来解决哈希冲突问题

本文链接：http://www.28at.com/showinfo-26-34685-0.htmlPython 哈希表的实现——字典

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇：十个杀手级VS Code插件

下一篇： PHP 8.3 正式发布！

标签：

热门焦点

跑分安卓第一！Redmi K60至尊版8月发布！卢伟冰：目标年度性能之王

8月5日消息，Redmi K60至尊版将于8月发布，在此前举行的战略发布会上，官方该机将搭载搭载天玑9200+处理器，安兔兔V10跑分超177万分，是目前安卓阵营最高的分数
28个SpringBoot项目中常用注解，日常开发、求职面试不再懵圈

前言在使用SpringBoot开发中或者在求职面试中都会使用到很多注解或者问到注解相关的知识。本文主要对一些常用的注解进行了总结，同时也会举出具体例子，供大家学习和参考。注解
把LangChain跑起来的三个方法

使用LangChain开发LLM应用时，需要机器进行GLM部署，好多同学第一步就被劝退了，那么如何绕过这个步骤先学习LLM模型的应用，对Langchain进行快速上手？本片讲解3个把LangChain跑起来
不容错过的MSBuild技巧，必备用法详解和实践指南

一、MSBuild简介MSBuild是一种基于XML的构建引擎，用于在.NET Framework和.NET Core应用程序中自动化构建过程。它是Visual Studio的构建引擎，可在命令行或其他构建工具中使用
如何正确使用:Has和:Nth-Last-Child

我们可以用CSS检查，以了解一组元素的数量是否小于或等于一个数字。例如，一个拥有三个或更多子项的grid。你可能会想，为什么需要这样做呢？在某些情况下，一个组件或一个布局可能会
雅柏威士忌多款单品价格大跌，泥煤顶流也不香了？

来源 | 烈酒商业观察编 | 肖海林今年以来，威士忌市场开始出现了降温迹象，越来越多不断暴涨的网红威士忌也开始悄然回归市场理性。近日，LVMH集团旗下苏格兰威士忌品牌雅柏（Ardbeg
得物宠物生意「狂飙」，发力“它经济”

作者｜花花小萌主近日，得物宣布正式上线宠物鉴别，通过得物App内的“在线鉴别”，可找到鉴别宠物的选项。通过上传自家宠物的部位细节，就能收获拥有专业资质认证的得物鉴
网红炒股不为了赚钱，那就是耍流氓！

来源：首席商业评论6月26日高调宣布入市，网络名嘴大v胡锡进居然进军了股市。在一次财经媒体峰会上，几个财经圈媒体大佬就“胡锡进炒股是否知道认真报道”展开讨论。有
华为Mate60标准版细节曝光：经典星环相机模组回归

这段时间以来，关于华为新旗舰的爆料日渐密集。据此前多方爆料，今年华为将开始恢复一年双旗舰战略，除上半年推出的P60系列外，往年下半年的Mate系列也将