《算法图解》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技术栈

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

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

3587
来自专栏我的博客

Laravel 辅助函数

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

26710
来自专栏运维小白

linux基础(day27)

9.4 sed(上) sed工具 sed -n '5'p test.txt sed -n '1,5'p test.txt sed -n '1,$'p test....

1797
来自专栏我的博客

AWK第二课

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

3517
来自专栏java一日一条

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

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

763
来自专栏xiaoxi666的专栏

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

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

822
来自专栏海天一树

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

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

1012
来自专栏高爽的专栏

Java线程(十一):Fork/Join-Java并行计算框架

并行计算在处处都有大数据的今天已经不是一个新鲜的词汇了,现在已经有单机多核甚至多机集群并行计算,注意,这里说的是并行,而不是并发。严格的将,并行是指系统内...

2180
来自专栏Coco的专栏

Javascript优化细节:短路表达式

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

Go指南_指针接收者

922

扫码关注云+社区