章
目
录
Java面试题:Redis数据类型中zset和set的区别?底层是怎么实现的?
标准回答
Redis的有序集合(Sorted Set)与集合(Set)类似,都是存储字符串类型元素的集合,不允许重复的成员。不同之处在于有序集合中的每个成员都会关联一个双精度浮点数类型的分数,Redis通过这个分数来为集合中的成员进行从小到大的排序。有序集合的成员是唯一的,但分数(score)可以重复。
有序集合底层使用了不同的存储结构,具体使用哪种结构取决于集合的大小和元素的长度:
1)当集合保存的元素数量小于128个且所有元素的长度都小于64字节时,Redis会使用ziplist作为底层存储结构。在这种情况下,每个集合元素都由两个紧挨在一起的压缩列表节点来保存。第一个节点保存元素的成员,第二个节点保存元素的分值。
2)当集合保存的元素数量大于等于128个或者任何元素的长度超过64字节时,Redis会使用skiplist作为底层存储结构。使用skiplist按序保存元素及其分值,并使用字典(dict)来保存元素和分值之间的映射关系。
这种双重结构的设计允许Redis在不同场景下都能高效地处理有序集合的操作。
加分回答
实际上,使用单独的HashMap或单独的Skiplist也可以实现有序集合。然而,Redis之所以使用两种数据结构的组合,是为了在查找成员的分值时保持O(1)的时间复杂度,同时允许范围操作。
如果只使用HashMap,虽然查找分值的时间复杂度是O(1),但由于HashMap是无序的,进行范围操作时需要额外的排序操作,使得范围操作的复杂度变高。
另一方面,如果只使用Skiplist,虽然可以执行范围操作,但查找成员的时间复杂度由O(1)变为O(logN)。因此,Redis选择了两种数据结构的组合来实现有序集合,以平衡不同操作的性能需求。