《算法图解》NOTE 5 散列表1.散列表简介2.散列表的特点2.1优点2.2缺点3.应用

这是《算法图解》的第五篇读书笔记,内容主要涉及散列表(hash table)。

1.散列表简介

散列表,又名哈希表,是一种数据结构。它是将用于搜索的键按照一个函数(哈希函数)转化为数组的索引,然后在索引所对应的数组元素中存放与键关联的内容。 从本质上来说,哈希表是一个数组,一个稀疏数组,但这个数组的索引是某个键的映射值,键与索引的映射关系可用哈希函数来表示。 在python中,最常见的哈希表的数据类型就是字典(dict)。

2.散列表的特点

2.1优点

由于散列表本质上是数组,因此支持随机访问,其时间复杂度为O(1)。同时,键的逻辑顺序并不是依赖于数组的索引序列,所以支持快速插入和删除键。

2.2缺点

对散列函数有较高的要求。为避免不同的键映射到同一个索引的情况(此种情况被称为冲突),散列函数必须能尽可能地将键均匀地映射到数组地索引。 可能需要重新调整数据的大小,即迁移数据的内存位置。发生调整数据的大小的情况主要是由于为减少冲突情况的发生概率,数组中有2/3的元素被填充后数据就需要调整内存大小。 同时,为避免冲突引起问题,需预先设定发生冲突时的解决方案。 综上所述,散列表使用时,对于内存的开销较大,但能依次获得较高的数据处理速度。即“用空间换时间”。

3.应用

散列表可用于查找以及信息加密。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列9

✎一、Java有没有goto? java中的保留字,现在没有在java中使用。 ✎二、必须要知道的运行时异常 ArithmeticException 是...

2694
来自专栏专注数据中心高性能网络技术研发

HERD--GCC宏

减少跳转语句失效时CPU等待取指令时间,提高CPU效率 使用__builtin_expect(EXP,N) 意思是EXP==N的概率很大 一般封装为LIKELY...

2915
来自专栏塔奇克马敲代码

第 17 章 标准库特殊设施

692
来自专栏章鱼的慢慢技术路

Go指南_指针接收者

992
来自专栏我的博客

Laravel 辅助函数

array_add() 如果给定的键不在数组中,会把给定的键值对加到数组中.否则则不加入 array_divide() 函数返回两个数组,一个包含原本数组的键...

27910
来自专栏海天一树

小朋友学数据结构(5):顺序查找法

查找是最常见的数据操作之一,也是数据结构的核心运算之一,其重要性不言而喻。 顺序查找是最简单的查找策略,对于小规模的数据,顺序查找是个不错的选择。

1162
来自专栏阮一峰的网络日志

awk 入门教程

它依次处理文件的每一行,并读取里面的每一个字段。对于日志、CSV 那样的每行格式相同的文本文件,awk可能是最方便的工具。

902
来自专栏xiaoxi666的专栏

vector作为参数的三种传参方式

c++中常用的vector容器作为参数时,有三种传参方式,分别如下(为说明问题,用二维vector):

1012
来自专栏林德熙的博客

dotnet 设计规范 · 数组定义

X 不建议设置数组类型的字段为只读。虽然用户不能修改字段,但是可以修改字段里面的元素。如果需要一个只读的集合,建议定义为只读集合。

671
来自专栏Java技术栈

8张图带你轻松温习Java知识

大年初四好,一图胜千言,下面图解均来自Program Creek 网站,目前它们拥有最多的票选。 如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。 ?...

3657

扫码关注云+社区