算法学习(四)—— 散列表
2021/7/6 20:41:15
本文主要是介绍算法学习(四)—— 散列表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
系列文章目录
第一章:二分查找及大O表示法
第二章:选择排序
第三章:递归和快速排序
第四章:散列表
文章目录
- 系列文章目录
- 前言
- 一、散列表是什么
- 二、散列表用途
- 三、散列表内部机制
- 1、冲突
- 2、性能
- 四、总结
前言
积累算法,记录学习
一、散列表是什么
散列表是最有用的基本数据结构之一。
前面所提及的简单查找和二分查找的运行时间分别是O(n)和O(logn),虽然二分查找已经很优美的节省时间了,但我们总期望查找时间更短,期望查找时间为0!!!因此散列表出现满足了我们的要求。
从数据结构来看散列表:我们需要每个元素包含两项内容,包括索引名字和该元素的值,即Key和Value。相信到这小伙伴就明白了,Python中给出了散列表的实现形式就是:字典dict
关于字典的讲解请参考我的Pythonic编程(六)——关于字典(dict)那些事
对于字典结构的数据,查询程序的运行时间是O(1)
二、散列表用途
- 模拟映射关系
- 防止重复
- 缓存、记住数据,以免服务器再通过处理生成他们
三、散列表内部机制
1、冲突
当散列表过大时,同一个Key可能会来不同的value,程序自己的处理会使后来的值覆盖之前的值,但当我们不想这样做时,显然就变成了一个冲突。
处理它也简单,就是将重复映射的位置也存储为一个链表
2、性能
散列表(平均情况) | 数组 | 链表 | |
---|---|---|---|
查找 | O(1) | O(1) | O(n) |
插入 | O(1) | O(n) | O(1) |
删除 | O(1) | O(n) | O(1) |
在平均情况下,散列表的查找(获取给定索引处的值)速度与数组一样快,而插入和删除速度与链表一样快,因此它兼具两者的优点!但在最糟情况下,散列表的各种操作的速度都很慢。因此,在使用散列表时,避开最糟情况至关重要。为此,需要避免冲突。而要避免冲突,需要有:
- 较低的装填因子
- 良好的散列函数
四、总结
一般的编程语言都提供了散列表的实现形式,比如python的dict。
散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。
这篇关于算法学习(四)—— 散列表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求