Redis常见面试题：ZSet底层数据结构，SDS、压缩列表ZipList、跳表SkipList
文章目录 一、Redis数据结构概述 1.1 Redis有哪些数据类型1.2 Redis本质是哈希表1.3 Redis的哈希冲突与渐进式rehash1.4 数据结构底层1.4.1 简单动态字符串SDS1.4.2 双向链表LinkedList（后续已废弃）1.4.3 压缩列表ZipList1.4.4 哈希表HashTable1.4.5 跳表SkipList1.4.6 整...
面试官：为何Redis使用跳表而非红黑树实现SortedSet？（下）
插入和删除算法都是通过查找与连接（search and splice）：维护一个update数组，在搜索结束之后，update[i]保存的是待插入/删除结点在第i层的左侧结点。插入 若key不存在，则插入该key与对应的value；若key存在，则更新value。如果待插入的结点的层数高于跳表的当前层数listLevel，则更新listLevel。选择待插入结点的层数r....
面试官：为何Redis使用跳表而非红黑树实现SortedSet？（中）
跳表的搜索时间复杂度我们都知道单链表搜索时间复杂度O(n)，那如此快的跳表呢？若链表有n个结点，会有多少级索引呢？假设每两个结点抽出一个结点作为上级索引，则：第一级索引结点个数是n/2第二级n/4第三级n/8…假设索引有h级，最高级索引有2个结点，可得：n/(2h) = 2所以：h = log2n-1若包含原始链表这一层，整个跳表的高度就是log2 n。我们在跳表中查询某个数据的时候，如果每一层....
面试官：为何Redis使用跳表而非红黑树实现SortedSet？（上）
知道跳表（Skip List）是在看关于Redis的书的时候，Redis中的有序集合使用了跳表数据结构。接着就查了一些博客，来学习一下跳表。后面会使用Java代码来简单实现跳表。什么是跳表跳表由William Pugh发明，他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作，论文....
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
Java面试那些事儿
手把手带您学习Java，开启编程之路。
+关注