《算法图解》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 条评论
登录 后参与评论

相关文章

来自专栏塔奇克马敲代码

第 17 章 标准库特殊设施

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

awk 入门教程

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

1012
来自专栏Java技术栈

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

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

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

Go指南_指针接收者

1042
来自专栏我的博客

AWK第二课

1、工作原理 例子: cat /etc/passwd |awk -F ‘:’ ‘BEGIN {print “name”} {print $1} END {p...

3677
来自专栏前端迷

很实用的前端开发规范

1.标准变量命名使用驼峰式命名 eg. let thisIsMyName; 2.常量全部大写,并使用下划线连接 eg. const MAX_COUNT = 10...

1162
来自专栏java一日一条

Java 程序优化:字符串操作、基本运算方法等优化策略

字符串对象或者其等价对象 (如 char 数组),在内存中总是占据最大的空间块,因此如何高效地处理字符串,是提高系统整体性能的关键。

1203
来自专栏Python小屋

Python编写编程作业批量自动打分程序的思路与实现

总体思路:把接口明确地告诉学生(本文后面的代码要求学生程序中必须有个函数叫做searchOnede),然后学生把Python程序文件(学号_姓名.py)以任何方...

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

HERD--GCC宏

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

2985
来自专栏Coco的专栏

Javascript优化细节:短路表达式

1494

扫码关注云+社区

领取腾讯云代金券