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

相关文章

来自专栏程序你好

二叉树搜索树(程序员都知道)

861
来自专栏java技术学习之道

海量数据处理 - 找出最大的n个数(top K问题)

1594
来自专栏蘑菇先生的技术笔记

探索C#之布隆过滤器(Bloom filter)

2555
来自专栏企鹅号快讯

什么是B+Tree

推荐阅读 微服务: springboot系列教程学习 源码:Javaweb练手项目源码下载 调优:十五篇好文回顾 面试笔试:面试笔试整理系列 B+Tree的定义...

1826
来自专栏灯塔大数据

每周学点大数据 | No.34缩图法(一)

No.34期 缩图法(一) Mr. 王:接下来我们再谈一种常用于磁盘上存储的图的思想,叫作缩图法。我们不得不设计磁盘算法,重要原因就是内存存不下特别大的图...

31211
来自专栏小白客

每天学习一点儿算法--散列表

在之前我们已经学过了二分查找和简单查找,我们知道二分查找的运行时间为O(㏒ n), 简单查找的运行时间为O(n)。除此之外,还有没有更快的查找算法呢? 可能有人...

2576
来自专栏云霄雨霁

字符串查找----查找算法的选择

1760
来自专栏C语言及其他语言

【编程经验】优秀题解

今天给大家带来一个我站“Manchester”大神写的一份优质题解(j解题思路很清晰):原题问题:1709: 算法7-16:弗洛伊德最短路径算法:

921
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

34711
来自专栏Android相关

散列表(Hash Table)

散列表是一种以平均O(1)时间插入、删除和查找的数据结构,可是类似于findMax,findMin等操作则需要以O(N)的时间才能完成

923

扫码关注云+社区