❤️实现、冲突和散列函数❤️ 算法图解：第五章：散列表

Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照 ?

​​入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！​​

​​​最后，愿我们都能在看不到的地方闪闪发光，一起加油进步​​

​​“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~

第五章：散列表

• ​​5.1散列函数​​
• ​​5.2应用案例​​
• ​​5.3冲突​​
• ​​5.4性能​​
• ​​5.5小节​​
• ​​最后的福利​​

5.1散列函数

散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。

如果用专业的术语来表达的话，我们会说，散列函数“将输入映射到数字”。

散列函数需要满足一些要求：

它必须是一致的。即每次输入相同内容时，返回的都是同一个数字

它应将不同的输入映射到不同的数字。最理想的情况是，将不同的输入映射到不同的数字。

散列函数将不同的输入映射到不同的索引。

散列表是你学习的第一种包含额外逻辑的数字结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。

Python提供的散列表时限为字典，可以用汉化苏dict来创建：

book=dict（）

散列表由键和值组成！

5.2应用案例

# -*-coding:utf-8 -*-
# @Author:到点了,心疼徐哥哥
# 奥利给干！！！
vote={}
def check_voter(name):
if vote.get(name):
print('投过了哟')
else:
vote[name]=True
print('投呗')
check_voter('tom')
print(vote)
check_voter('tom')

如果“tom”在散列表中，函数get将返回True；否则返回None。

如果将已投票者的名字存储到列表中，这个函数的速度终将会变得非常慢，因为它必须得使用简单的查找搜索整个列表。使用散列表来检查是否重复，速度非常快。

散列表适用于：

1.模拟映射关系；

2.防止重复；

3.缓存/记住数据，以免服务器再通过处理来生成它们。

5.3冲突

两个元素映射到了同一个位置，就需要在这个位置再存储一个链表。

这里给我们两个教训：

散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。

如果散列表的存储链表很长，散列表的速度急剧下降，如果使用的散列函数很好，这些链表就不会很长。

5.4性能

简单查找的运行时间为线性时间；

二分查找的速度更快，所需时间为对数函数；

在散列表中查找所需要的时间为常量时间。

5.5小节

你几乎不需要自己去实现散列表，因为你使用的编程语言提供了散列表的实现。

散列表是一种功能强大的数据结构，其操作速度快。

1.可以结合散列函数和数组来创建散列表；

2.冲突很糟糕，应该使用最大限度减少冲突的散列函数；

3.散列表的查找、插入和删除速度都非常快；

4.散列表适合用于模拟映射关系；

5.一旦填装因子超过0.7，就该调整散列表的长度；

6.散列表可用于缓存数据；

7.散列表非常的适合用于防止重复。

最后的福利

☀️☀️☀️最后一点小福利带给大家：如果想快速上手python的小伙伴们，这个详细整理PPT可以迅速帮助大家打牢python基础，需要的小伙伴们可以下载一下 Python入门基础教程全套+小白速成+学不会来找我！

还有自制表白神器，需要自取：

Python表白神器，源码+解析+各种完美配置+浪漫新颖

好啦，这就是今天要给大家分享的全部内容了

如果你喜欢的话，就不要吝惜你的一键三连了~