京东科技技术新知-编程思维
作者:京东物流 纪卓志目前市面上充斥着大量关于跳跃表结构与Redis的源码解析,但是经过长期观察后发现大都只是在停留在代码的表面,而没有系统性地介绍跳跃表的由来以及各种常量的由来。作为一种概率数据结构,理解各种常量的由来可以更好地进行变化并应用到高性能功能开发中。本文没有重复地以对现有优秀实现进行代码分析,而是通过对跳跃表进行了系统性地介绍与形式化分析,并给出了在特定场景下的跳跃表扩展方式,方便读
morethink program
最近换了工作,因为工作的需要,也正好自己想好好研究一下Java这门牛逼的语言,看了一下ElasticSearch和Lucene的源码,之前从来没有写过也没有看过Java的东西,所以也算是恶补了一下Java吧,由于是从C程序员开始的,所以对这种带虚拟机的语言总有一些偏见,老觉得内存不好控制,所以一直以来都没有怎么碰过Java,最近静下心来好好看了一下Java和相关的源码,除了感觉语言本身啰嗦了一点
原创公众号「bigsai」文章已收录在 我的Github bigsai-algorithm前言跳表是面试常问的一种数据结构,它在很多中间件和语言中得到应用,我们熟知的就有Redis跳表。并且在面试的很多场景可能会问到,偶尔还会让你手写试一试(跳表可能会让手写,红黑树是不可能的),这不,给大伙复原一个场景:但你别慌,遇到蘑菇头这种面试官也别怕,因为你看到这篇文章了(得意😏),不用像熊猫那样窘迫。对于
简介 有序集合是一个数据类型和集合和hash表很相似,数据是不重复的。由于集合中的元素是没有排序的,因此有序集合中的每个元素都和一个浮点型数字关联起来,这个浮点型数字叫做score(所以它和hash很像)。有序集合内的元素是按照以下规则排序的。① A和B是2个分数不同的元素。如果A的分数大于B的分数,那么A>B。② 如果A和B分数相同,那么当A的字符串词典顺序比B的到时候,A>B(A
Redis的复合数据结构 我们之前已经讲过了Redis的数组列表(List),但其实Redis中最常用的数据结构是字典(hash),可以说,Redis整体的设计都是基于字典的,这不仅仅体现在我们存取数据都是通过键值对的方式,还在于其他的复合数据结构set/zset也都是基于hash来设计的。 hash 字典 字典在任何语言中都是非常基础和常见的数据结构,在Java中它是HashMap,在PHP中
跳跃表入门跳跃表这个东西,一直在听说,但从未手动实现过,所以理解的也不是很透彻。最近闲来无事,用golang实现了一个基础版本,加深一下理解。跳跃表的逻辑结构如下:这里不解释基础原理了,网上大把的资料,总结几点加深理解:跳跃表的底层还是链表,而且是有序链表,在构造跳跃表的时候就必须保证数据有序;跳跃表用的是空间换时间的思想;有点类似有序数组的二分查找;跳表的查询,插入和删除操作的期望时间复杂度都为
Sorted Set (ZSet) 数据结构 Sorted Set (ZSet), 即有序集合, 底层使用 压缩列表(ziplist) 或者 跳跃表(skiplist) 使用 压缩列表(ziplist) 当同时满足下面两个条件时,使用 ziplist 存储数据 元素个数少于128个 (zset-max-ziplist-entries: 128) 每个元素长度小于64字节 (zset-max-z
最近在阅读redis设计与实现,关于redis数据结构zset的一种底层实现跳跃表一直没有太理解,所以在搜了一下资料,终于搞懂了它的设计思路,记录一下。 参考链接:https://mp.weixin.qq.com/s?src=11×tamp=1553915878&ver=1515&signature=SuSdA-Ka7Bs7CzSnNHgHFR7DkFFibGd