数据结构与算法之美-散列表-极客时间笔记

2024-05-31 04:48

本文主要是介绍数据结构与算法之美-散列表-极客时间笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

散列表或者哈希表,就是数组的一种延伸应用,主要还是利用数组可以方便的理由下标索引进行元素操作。概念的核心点在于原始数据可能是键值对,将Key值通过哈希函数进行转化变成唯一(希望是唯一,但并无法保证,所以才有后面的散列冲突问题)的下标索引,以此来保证Value值。

 散列函数的设计有下列三点要求:

1、散列函数计算得到的散列值是一个非负整数;——因为散列的结果对应数组下标,必要要求非负整数。

2、如果 key1 = key2,那 hash(key1) == hash(key2);——相同Key对应的散列值要一致,涉及第一次存储和后续读取

3、如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)。——最好的结果是不同的Key对应不同的散列值,这样才能区分

但第三点是没办法实现的,因为无论如何数组大小是有限的,而可能的Key是无限的,这样用有限去对应无限,必然是会出现重复,这就是所谓的散列冲突问题。

处理散列冲突常用的有两种方法:开发寻址法和链表法。

1、开放寻址法是当遇到散列值被使用的情况下就继续做数组中顺序寻找空闲位置,这样会有个缺点,就是如果散列冲突很多的时候,这种顺序去查找的时间就会变得特别长。而且还有个问题就是,如果不是哈希插入,而是哈希查找。一般来说是发现空闲位置前还没有发现目标元素则认为元素不在散列表。但是如果数组之前有元素被删除,相应位置出现空缺,就会错误的认为元素不在散列表。虽然可以用删除标记来表示,但这种方法还是不够方便,实际应用不多。

2、链表法,如果出现散列值相同的情况,就在相应位置建立1条链表,只要散列的分布足够均匀,不让大多数散列值相同,就不会让散列表退化。不然很多元素在一个散列值组成链表就容易变成单链表。

为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子(load factor)来表示空位的多少。装载因子是目前已装入元素个数除以数组长度。装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

一个能应对各种异常情况的工业级散列表也应该从上述三方面出发:

1、散列函数的设计,不能过于复杂,因为散列值会需要经常计算,复杂计算势必会影响到性能;另外散列函数的结果要尽可能随机且平均分布,减少散列冲突的可能。

2、装载因子可以作为散列表是否需要扩容的因素指标,当到底某个阈值后启动动态扩容,将旧散列表的数据迁移至新散列表。虽然这种操作经过均摊还是O(1),但是对于那一次来说,用户体验还是糟糕。可以将摊还真实的进行分割,旧数据迁移不是一次进行,而是伴随新数据存入同步进行,这样就对于每个用户来说时间都不会太明显。

3、根据使用场景选择合适的散列冲突解决方法。当数据量比较小、装载因子小的时候,适合采用开放寻址法。利用数组的优点,但更加消耗内容,因为散列冲突的影响更加严重。基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表。

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说,它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历。那效率势必会很低。为了解决这个问题,我们将散列表和链表(或者跳表)结合在一起使用。可以看下图这个缓存系统的数据结构:

上图存在两种链表,一种是表示缓存更新时间的双向链表,另一种是散列表中用于解决散列冲突的链表。可以在O(1)时间里实现查找、删除、增加。散列表用于查找元素,删除和增加利用双向链表的指针也可以快速实现。

 

 

这篇关于数据结构与算法之美-散列表-极客时间笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1017399

相关文章

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》:本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价