为什么hash数据结构的底层，使用skiplist比直接使用hash会更节省内存呢？
- 面试其他
- 时间：2023-07-27 13:36
- 2791人已阅读
🔔🔔🔔好消息!好消息!🔔🔔🔔
有需要的朋友👉:联系凯哥
问题:
1. 为什么hash数据结构的底层，使用skiplist比直接使用hash会更节省内存呢？
2. 为什么要强调，在hash保存1000条数据以内时，底层使用skiplist呢？
skiplist是在数据量较大的场景下，查询性能有明显优势吧，数据量越多，查询性能的提高越明显吧，这和存储有什么关系？为什么能节约内存？
答：1.http://zhangtielei.com/posts/blog-redis-skiplist.html
从内存占用上来比较，跳表比平衡树更灵活一些。
平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针。
举个例子，下图有个 3 层级的跳表。
如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：
先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1];
「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；
「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。
2.Hash 类型的底层数据结构是由压缩列表或哈希表实现的：
如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；
如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的 底层数据结构。