数据结构与算法笔记(二)

跳表

前面的数据结构笔记中分析过链表,如图所示:

由于它的内存空间非连续,因此查找某个元素时只能从头到尾遍历,时间复杂度为 O(n)。那么能不能提高链表的查找效率呢?

我们可以对链表进行改造,在链表上建立一级“索引”,如图:

这样,在查找的时候就可以先在索引层查找,然后再根据索引去查数据(有点类似数据库的索引)。

为了进一步提高查找效率,还可以建立二级索引,如图:

以此类推,还可以建立更多层级的索引:

这种数据结构称为跳表(Skip List)。这样做查找速度更快了,但同时也会耗费更多的存储空间,它的思想其实就是空间换时间。

应用场景:Redis 的有序集合。

散列表

散列表(Hash table),又称“哈希表”或“Hash 表”。利用的是数组支持按照下标访问数据(时间复杂度为 O(1))的特性,是数组的一种扩展。示意图:

其中的 key 为可理解为要存入的数据的键(键-值对形式);hash() 是「散列函数」,它根据 key 计算得到一个非负整数,是哈希表实现的一个关键点;table 为存放数据的数组。

散列表存入数据的大概流程是:将 key 经过散列函数计算得到一个值(保证在数组长度范围内)作为数组的下标,然后将 key 的值保存在数组下标对应的位置。

散列函数

散列函数设计的基本要求:

1. 散列函数计算得到的散列值是一个非负整数(数组下标从 0 开始的);

2. 如果 key1 = key2,那么 hash(key1) = hash(key2)

3. 如果 key1key2,那么 hash(key1)hash(key2)

此外,散列函数的设计不能太复杂(会消耗很多计算时间),而且生成的值要尽可能随机并且均匀分布(尽量最小化散列冲突)。

例如,JDK 1.8 中 HashMap 的散列函数设计如下:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

注: 真实情况下,不同 key 对应的散列值都不一样的散列函数几乎是不存在的。业界著名的 MD5、SHA、CRC 等哈希算法也无法避免这种散列冲突。

因此,需要其他途径来解决散列冲突的问题。

散列冲突

解决散列冲突常用的有两种方法:开放寻址法(open addressing)和链表法(chaining)。

1. 开放寻址法

核心思想:如果出现了散列冲突,就重新探测一个空闲位置将其插入。常用的探测方法有三种:

1.1 线性探测(Linear Probing)

往散列表中插入数据时,若某个数据经散列函数散列之后,存储位置已经被占用,就从当前位置开始依次往后查找,直到找到空闲位置插入。示意图:

缺点:散列表中的数据越来越多时,空闲位置越来越少,散列冲突的可能性会越来越大,线性探测的时间会越来越久。

1.2 二次探测(Quadratic Probing)

线性探测每次探测的步长是 1,二次探测的步长则为“二次方”。

1.3 双重散列(Double hashing)

使用一组散列函数,当 hash1(key) 冲突时再用 hash2(key)……直至找到空闲的位置。

装载因子计算公式:

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

2. 链表法

该方法更为常用。在散列表中,每个“桶(bucket)”或“槽(slot)”会对应一条链表,所有散列值相同的元素都会放到相同槽位对应的链表中,如图所示:

二者对比

1. 当数据量比较小、装载因子小的时候,适合采用开放寻址法(例如 Java 中的 ThreadLocalMap)。

2. 链表法比较适合存储大对象、大数据量的散列表;而且比开放寻址法更灵活、支持更多的优化策略(比如用红黑树替代链表,JDK 1.8 中 HashMap 的实现)。

PS: 由于链表要存储指针,当存储比较小的对象时内存消耗可能会翻倍;而存储大对象,即存储对象的大小远大于一个指针的大小(4 或 8 个字节)时,链表中指针的内存消耗可以忽略了。

小结

1. 跳表

跳表是在链表的基础上增加索引层来提高查找效率,但同时也增加了存储空间开销,利用“空间换时间”的思想。

常见应用场景:Redis 中的有序集合。

2. 散列表

两个核心问题:散列函数设计散列冲突解决

散列冲突常用的解决方法有两种:开放寻址法链表法

散列函数设计的好坏决定了散列冲突的概率,也决定了散列表的性能。

相关文章:

数据结构与算法笔记(一)

Stay hungry, stay foolish.

本文分享自微信公众号 - WriteOnRead(WriteOnRead)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-08

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试技术圈

窥视WebSocket传输的内容(Fiddler抓取)

Fiddler(中文名称:小提琴)是一个HTTP的调试代理,以代理服务器的方式,监听系统的Http网络数据流动,Fiddler可以也可以让你检查所有的HTTP通...

37750
来自专栏Kiba518

WPF滑块控件(Slider)的自定义样式

点击确定后,我们的页面的Resources中,增加了一系列样式代码,而滑块代码会被修改为如下样子:

30330
来自专栏测试技术圈

这些Python库真的很“冷”,但是却很强大

Python是一种很棒的编程语言。事实上,它还是世界上发展最快的编程语言之一。它一次又一次证明了它在数据科学职位中的实用性。整个Python及其库的生态系统使其...

10230
来自专栏AI科技评论

一文带你了解视觉目标跟踪

视觉目标跟踪(Visual Object Tracking)是计算机视觉领域的一个重要问题。尽管近年来受到了广泛研究,目标跟踪问题由于本身的高难度、高质量数据的...

42220
来自专栏Java架构沉思录

线程本地变量,你只会ThreadLocal吗?

代码@3:如果线程对象的threadLocals属性不为空,则从该Map结构中,用threadLocal对象为键去查找值,如果能找到,则返回其value值,否则...

23630
来自专栏测试技术圈

持续交付之基于Git Flow代码分支策略实践

高效的持续交付体系,必定需要一个合适的代码分支策略。采用不同的代码分支策略,意味着实施不同的代码集成与发布流程,这会影响整个研发团队每日的协作方式,因此研发团队...

8720
来自专栏测试技术圈

【文章】Java应用程序运行时监控方法之JVMTI的应用

The JVM Tool Interface (JVMTI) 是一个由JVM提供的用于开发针对Java程序开发与监控工具的编程接口,通过JVMTI接口(Nati...

19430
来自专栏测试技术圈

Fiddler抓取websocket的包

50730
来自专栏北京马哥教育

加密传输原理

数字签名,就是通过在数据单元上附加数据,或对数据单元进行秘密变换,从而使接收者可以确认数据来源和完整性。简单说来,数字签名是防止他人对传输的文件进行破坏,以及确...

12240
来自专栏木又AI帮

【leetcode刷题】T131-二叉搜索树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

8440

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励