剖析基础数据结构及其用法
|
首先ZSet如果数组存储的话，由于ZSet中存储的元素是有序的，存入的时候需要将元素放入数组中对应的位置。这样就会对数组进行频繁的增删，而频繁的增删在数组中效率并不高，因为涉及到数组元素的移动，如果元素插入的位置是首位，那么后面的所有元素都要被移动。 所以为了应付频繁增删的场景，我们需要使用到链表。但是随着链表的元素增多，同样的会出现问题，虽然增删的效率提升了，但是查询的效率变低了，因为查询元素会从头到尾的遍历链表。所有如果有什么方法能够提升链表的查询效率就好了。 于是跳表就诞生了。基于单链表，从第一个节点开始，每隔一个节点，建立索引。其实也是单链表。只不是中间省略了节点。 例如存在个单链表 1 3 4 5 7 8 9 10 13 16 17 18 抽象之后的索引为 1 4 7 9 13 17 如果要查询16只需要在索引层遍历到13，然后根据13存储的下层节点(真实链表节点的地址)，此时只需要再遍历两个节点就可以找到值为16的节点。 所以可以重新给跳表下一个定义，链表加多级索引的结构，就是跳表 在跳表中，查询任意数据的时间复杂度是O(logn)。时间复杂度跟二分查找是一样的。可以换句话说，用单链表实现了二分查找。但这也是一种用空间换时间的思路，并不是免费的。 除了能够对其中的元素添加权重之外，使用ZSet还可以实现延迟队列。 延迟队列用于存放延迟任务，那什么是延迟队列呢? 举个很简单的例子， 你在某个电商APP中下订单，但是没有付款，此时它会提醒你，「订单如果超过1个小时没有支付，将会自动关闭」;再比如在某个活动结束前1个小时给用户推送消息;再比如订单完成后多少天自动确认收货等等。 用人话解释一遍，那就是过会才要干的事情。 那ZSet怎么实现这个功能? 其实很简单，就是将任务的执行时间设置为ZSet中的元素权重，然后通过一个后台线程定时的从ZSet中查询出权重最小的元素，然后通过与当前时间戳判断，如果大于当前时间戳(也就是该执行了)就将其从ZSet中取出。 那，怎么取? 其实我看很多讲Redis实现延迟队列的博客都没有把这个怎么取讲清楚，到底该用什么命令，传什么参数。我们使用zrangebyscore命令来实现，还记得-inf和inf吗，其全称是infinity，分别表示无限小和无限大。 基础的命令如下：
其实大多数情况下的使用跟HashMap是差不多的，没有什么较为特殊的地方。 4.2 原理 hash的底层实现也是有两种，ZipList和HashTable。但具体采用哪一种与Redis的版本无关，而与当前hash中所存的元素有关。首先当我们创建一个hash的时候，采用的ZipList进行存储。随着hash中的元素增多，达到了Redis设定的阈值，就会转换为HashTable。 其设定的阈值如下：
ZipList上面我们专门简单分析了一下，理解这个设定应该也比较容易。当ZipList中的元素过多的时候，其查询的效率就会变得低下。而HashTable的底层设计其实和Java中的HashMap差不多，都是通过拉链法解决哈希冲突。具体的可以参考从基础的使用来深挖HashMap这篇文章。 （编辑：江门站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
