前面几篇文章,我已经对 rosedb 有了一定的讲解了,如果还没有看前面的内容,请先看一下之前的内容,这样你才能更好的理解本篇文章的内容。
这一节我会给大家分享我的开源项目当中所涉及到的一些数据结构,有链表、跳表、哈希表、有序集合,比较硬核的数据结构分析,请一定要看完哦!
视频参考在文章的底部!可以先看下文字内容,辅助理解。
链表
链表应该是大家都很熟悉的数据结构了,它指的是使用指针将一组连续的内存块串联起来的一种结构,如下图:
因为链表的内存块不是连续的,因此在链表中查找数据,需要从头到尾遍历链表,平均时间复杂度是 O(n)。
和它相对应的数据结构是数组,数组占用连续的内存空间,因此可直接根据内存寻址定位元素,随机访问的时间复杂度是 O(1)。
在具体实践当中,其实使用得更多的是双向链表,它不仅有指向下一个内存块的 next 指针,还有指向前一个内存块的 prev 指针。
这样的话,可以双向遍历,在某些情况下,能够减少节点遍历的次数。
哈希表
哈希表基于数组,通过一个哈希函数,将不同的 key 映射为数组的下标,将 value 存储至数组对应的下标处。
由于它基于数组,查找的时间复杂度是 O(1) 的,删除的时候,会直接做一个标记,不会大规模移动数据,因此时间复杂度也是 O(1) 的。
只不过哈希表也有一个缺点,那便是数据是无序的。
哈希表的设计比较复杂,需要考虑到装载因子、哈希函数、扩容、哈希冲突等等,在大多数编程语言中都有了内置的实现,比如 Java 中的 HashMap,Go 语言的 map。
跳表
跳表是针对链表的劣势而进行改进的,我们知道传统的链表查找数据只能从头到尾开始遍历,那么有没有什么办法能够加速这个查询呢?
在原始链表上不太好解决这个问题,因为链表的节点内存地址不是连续的,既然在一维解决不了这个问题,那么我么可以上升到二维。
这也是常见的解决问题的一个思路,一维解决不了的问题,我们会上升到二维,一些常见的数据结构其实都是这个思路,比如二叉树、图。
在原始的链表基础之上,加一层索引,每次查找的时候都从索引层下来,这样不用从原始链表挨个遍历,查找的速度加快了。
这就是跳表的基本思路,通过在原始链表之上,加上一级一级的索引,减少节点遍历的个数。
跳表还有一个优势,那就是链表节点的数据是有序排列的,这样很容易就能够实现区间查找、前缀扫描、排名统计等功能。
有序集合
有序集合是一个组合的数据结构,使用跳表 + 哈希表,其中跳表主要是保证节点有序,这一点在前面已经说过了,而哈希表则提供了O(1)的访问性能,有序集合的结构如下图:
有序集合节点由一个哈希表 dict 和一个跳表 skipList 组成,dict 的 key 是 member,value 是一个跳表节点。而 skipList 则存储的是 score 和 member 信息。
参考视频
题图:from wallheaven.cc
本文分享自 roseduan写字的地方 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!