做网站运营工资是不是很低,网站不被百度收录,高效的客户管理crm系统,wap浏览器在线哈喽大家好#xff0c;我是咸鱼
接触过 Python 的小伙伴应该对【字典】这一数据类型都了解吧
虽然 Python 没有显式名称为“哈希表”的内置数据结构#xff0c;但是字典是哈希表实现的数据结构
在 Python 中#xff0c;字典的键#xff08;key#xff09;被哈希#x…哈喽大家好我是咸鱼
接触过 Python 的小伙伴应该对【字典】这一数据类型都了解吧
虽然 Python 没有显式名称为“哈希表”的内置数据结构但是字典是哈希表实现的数据结构
在 Python 中字典的键key被哈希哈希值决定了键对应的值value在字典底层数据存储中的位置
那么今天我们就来看看哈希表的原理以及如何实现一个简易版的 Python 哈希表
ps文中提到的 Python 指的是 CPyhton 实现
何为哈希表
哈希表hash table通常是基于“键-值对”存储数据的数据结构
哈希表的键key通过哈希函数转换为哈希值hash value这个哈希值决定了数据在数组中的位置。这种设计使得数据检索变得非常快
举个例子下面有一组键值对数据其中歌手姓名是 key歌名是 value
------------------------------
| Key | Value |
------------------------------
| Kanye | Come to life |
| XXXtentacion | Moonlight |
| J.cole | All My Life |
| Lil wanye | Mona Lisa |
| Juice WRLD | Come Go |
------------------------------如果我们想要将这些键值对存储在哈希表中首先需要将键的值转换成哈希表的数组的索引这时候就需要用到哈希函数了
哈希函数是哈希表实现的主要关键它能够处理键然后返回存放数据的哈希表中对应的索引 一个好的哈希函数能够在数组中均匀地分布键尽量避免哈希冲突两个键返回了相同的索引 哈希函数是如何处理键的这里我们创建一个简易的哈希函数来模拟一下实际上哈希函数要比这复杂得多
def simple_hash(key, size):return ord(key[0]) % size这个简易版哈希函数将歌手名即 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 字典dictionarydict是一种无序的、可变的集合collections它的元素以 “键值对key-value”的形式存储
字典中的 key 是唯一且不可变的这意味着它们一旦设置就无法更改
my_dict {Kanye: Come to life, XXXtentacion: Moonlight, J.cole: All My Life}在底层Python 的字典以哈希表的形式运行当我们创建字典并添加键值对时Python 会将哈希函数作用于键从而生成哈希值接着哈希值决定对应的值将存储在内存的哪个位置中
所以当你想要检索值时Python 就会对键进行哈希从而快速引导 Python 找到值的存储位置而无需考虑字典的大小
my_dict {}
my_dict[Kanye] Come to life # 哈希函数决定了 Come to life 在内存中的位置
print(my_dict[Alice]) # Come to life 可以看到我们通过方括号[key]来访问键对应的值如果键不存在则会报错
print(my_dict[Kanye]) # Come to life # Raises KeyError: Drake
print(my_dict[Drake])为了避免该报错我们可以使用字典内置的 get() 方法如果键不存在则返回默认值
print(my_dict.get(Drake, Unknown)) # Unknown在 python 中实现哈希表
首先我们定义一个 HashTable 类表示一个哈希表数据结构
class HashTable:def __init__(self, size):self.size sizeself.table [None]*sizedef _hash(self, key):return ord(key[0]) % self.size在构造函数 __init__() 中
size 表示哈希表的大小table是一个长度为 size 的数组被用作哈希表的存储结构。初始化时数组的所有元素都被设为 None表示哈希表初始时不含任何数据
在内部函数 _hash() 中用于计算给定 key 的哈希值。它采用给定键 key 的第一个字符的 ASCII 值并使用取余运算 % 将其映射到哈希表的索引范围内以便确定键在哈希表中的存储位置。
然后我们接着在 HashTable 类中添加对键值对的增删查方法
class HashTable:def __init__(self, size):self.size sizeself.table [None]*sizedef _hash(self, key):return ord(key[0]) % self.sizedef set(self, key, value):hash_index self._hash(key)self.table[hash_index] (key, value)def get(self, key):hash_index self._hash(key)if self.table[hash_index] is not None:return self.table[hash_index][1]raise KeyError(fKey {key} not found)def remove(self, key):hash_index self._hash(key)if self.table[hash_index] is not None:self.table[hash_index] Noneelse:raise KeyError(fKey {key} not found)其中set() 方法将键值对添加到表中而 get() 该方法则通过其键检索值。该 remove() 方法从哈希表中删除键值对
现在我们可以创建一个哈希表并使用它来存储和检索数据
# 创建哈希表
hash_table HashTable(10)# 添加键值对
hash_table.set(Kanye, Come to life)
hash_table.set(XXXtentacion, Moonlight)# 获取值
print(hash_table.get(XXXtentacion)) # Outputs: Moonlight# 删除键值对
hash_table.remove(XXXtentacion)# 报错 KeyError: Key XXXtentacion not found
print(hash_table.get(XXXtentacion))前面我们提到过哈希碰撞是使用哈希表时不可避免的一部分既然 Python 字典是哈希表的实现所以也需要相应的方法来处理哈希碰撞
在 Python 的哈希表实现中为了避免哈希冲突通常会使用开放寻址法的变体之一称为“线性探测”Linear Probing
当在字典中发生哈希冲突时Python 会使用线性探测即从哈希冲突的位置开始依次往后查找下一个可用的插槽空槽直到找到一个空的插槽来存储要插入的键值对。
这种方法简单直接可以减少哈希冲突的次数。但是它可能会导致“聚集”Clustering问题即一旦哈希表中形成了一片连续的已被占用的位置新元素可能会被迫放入这片区域导致哈希表性能下降
为了缓解聚集问题假若当哈希表中存放的键值对超过哈希表长度的三分之二时即装载率超过66%时哈希表会自动扩容
最后总结一下
在哈希表中是根据哈希值即索引来寻找数据所以可以快速定位到数据在哈希表中的位置Python 的字典以哈希表的形式运行当我们创建字典并添加键值对时Python 会将哈希函数作用于键从而生成哈希值接着哈希值决定对应的值将存储在内存的哪个位置中Python 通常会使用线性探测法来解决哈希冲突问题
