标题: <Redis 高手心法> 读书笔记 | P2-数据结构- Sets
作者: #DT_Stone
板块: #读书成诗
编号: 310031
帖子: https://linux.do/t/topic/310031
时间: 2024-12-24 09:49:10
摘要:

去重
点赞
共同好友等

类似于 java 的 hashSet 通过散列表实现.所以增删差都是 O(1) 复杂度
Sets
无序与唯一
Sets 是字符串类型的无序集合.
java 中的 HashSet 底层是 HashMap 实现, Sets 底层数据结构是散列表实现, 散列表的 key 存储元素的 value. 散列表的 value 指向 null
注意:
当元素内容是 64 位以内的十进制整数,并且元素个数不超过 set-max-intset-entries 配置的值(默认是 512) Sets 会使用更加省内存的 intset(整型数组) 来存储




key: demoKey1
key: demoKey2
…




value = null
value = null
null


intset存储









1
2
3



场景
需要存储多个元素,并且要求不能重复.无须考虑元素的有序性时,可以使用 sets.sets 还支持集合之间做交集,并集,集差操作,

统计多个元素的共有元素 (交集)
对于两个集合 统计其中一个的独有元素 (集差)
统计多个集合的所有元素(并集)

实际场景:

社交中的共同关注: 通过交集实现
每日新增关注数: 对近两天的总注册用户量集合取差集
打标签: 为自己收藏的每一篇文章打标签,如微信的收藏功能,这样可以快速找到被添加了某个标签的所有文章

intset
结构
typedef struct intset{
 uint32_t encoding;
 uint32_t length;
 int8_t contents[];
}





length
记录整个集合存储的元素个数,即 contents 的数组长度




contents
存储整数集合的数组,是一块连续的区域,每个元素都是一个数组元素, 数组中的元素会按照值的大小升序存储,并且不会有重复的元素


encoding
INTSET_ENC_INT16 表示存储元素用的是 int16_t ,即 2 个字节表示一个整数元素INTSET_ENC_INT32 …4 字节表示一个元素INTSET_ENC_INT64 … 8 字节




如果一个 int16 类型的 intset 中插入一个 int64 的类型的值会如何?
A:
这种情况会触发 intset 升级,也就是 Sets 所有的元素都会转换成 int64 类型
具体步骤如下

根据新元素的类型和 sets 元素的数量,计算包括新添加的元素在内的新的空间的大小,对底层数组空间扩容,重新分配空间
将 intset 中原有的元素都转换成新的元素类型,把转换后的元素按照从大到小的顺序放到正确的位置上,需要保证 intset 的有序性
将 encoding 的值修改为 length+1


因此每次向 intset 添加新的元素都可能造成升级, 升级又会对原始数据进行类型转换,时间复杂度为 O(N)

如果删除刚刚添加的 int64 数据, intset 会降级吗?
A:
intset 不支持降级操作


Sets 是无序集合,为什么存储整型数字的场景中 contents 数组元素需要有序?
数组有序有助于使用二分法查找元素,提高效率.当 insetFind 函数返回值=0 时,表示 intset 中没有目标数据. 当 insetFind 返回 1 时, 表示存在目标数据方法内部会调用 intsetSearch 使用二分法查找数据

标题: 有没有新年喜庆的音乐歌单
作者: #Muumuyi
板块: #搞七捻三
编号: 310032
帖子: https://linux.do/t/topic/310032
时间: 2024-12-24 09:49:43
摘要:

准备过年在老家搞个大喇叭放，有没有类似金蛇狂舞、新年序曲、恭喜发财这种喜庆的音乐

标题: 【serv00】各s之间，有啥区别？？？？？？？？？？
作者: #kapas
板块: #搞七捻三
编号: 310040
帖子: https://linux.do/t/topic/310040
时间: 2024-12-24 09:53:53
摘要:

谁给科普下？
我的https://panel7.serv00.com/
是不是就是s7
才3g硬盘，512m内存
其他呢？？？

标题: 真困啊，这砖不搬也罢
作者: #碌卡森破
板块: #搞七捻三
编号: 310041
帖子: https://linux.do/t/topic/310041
时间: 2024-12-24 09:54:13
摘要:

瞌睡啊，目前处于神游状态

标题: 也许我们能够少一点反问
作者: #RerrentLinden
板块: #运营反馈
编号: 310051
帖子: https://linux.do/t/topic/310051
时间: 2024-12-24 09:57:50
摘要:

也许我们能够少一点反问
有的发帖中，在楼主提问题、提意见、寻推荐、寻购买后有时能看见的回复的格式是：

为什么要问xxx
为什么会觉得xxx
为什么不用xxx/为什么要用xxx，我都用yyy
为什么买xxx，明明yyy也可用
…

不是说不让问为什么，而是说在楼主提出疑问后，反问的回答在互联网环境，很多时候并不有助于解决问题，也不利于一个友善的交流氛围。
也许我们可以更多的：

xxx的回答是yyy/你可以在yyy找到解答
你可以yyy，达到和xxx一样的效果
我觉得yyy
我没用xxx，我在用yyy
我没买xxx，我在用yyy
亦或者直接的，我不同意你的观点

即使是550W也会说：“回答问题请勿使用比喻、反问或暗示等修辞”
在互联网交流中，更难免会出现信息不对等导致的传递过程中的信息熵导致的误会。直接、陈述式的交流也许有助于我们更好的沟通与营造社区环境。

标题: 今天我可以说话大声一点了吧
作者: #test
板块: #搞七捻三
编号: 310054
帖子: https://linux.do/t/topic/310054
时间: 2024-12-24 09:58:33
摘要:

标题: DBeaver今天的彩蛋
作者: #zhao
板块: #搞七捻三
编号: 310055
帖子: https://linux.do/t/topic/310055
时间: 2024-12-24 09:58:43
摘要:

有点意思

标题: 【蛇钞问题】
作者: #流水清花
板块: #搞七捻三
编号: 310058
帖子: https://linux.do/t/topic/310058
时间: 2024-12-24 10:00:35
摘要:

在工行抢到的，但是兑换时间当时看错了，时间不太方便
所以我想问一下，

我能在兑换期内，早于我的预约时间去兑换吗？

有没有之前操作过的大佬说一下

标题: 有用过hexo-blog-encrypt的佬吗？
作者: #笑红尘
板块: #搞七捻三
编号: 310065
帖子: https://linux.do/t/topic/310065
时间: 2024-12-24 10:02:49
摘要:

有用过hexo-blog-encrypt的佬吗？安全性如何呀？
hexo有其他加密方案吗？
hugo有加密方案吗？

标题: 有人试过SafePal吗？
作者: #chato
板块: #搞七捻三
编号: 310068
帖子: https://linux.do/t/topic/310068
时间: 2024-12-24 10:03:00
摘要:

有人注册过SafePal吗？看到可以开通万事达，充GPT会员。
使用护照注册

标题: 文章分享分享
作者: #善解人意屬實有點害羞
板块: #搞七捻三
编号: 310069
帖子: https://linux.do/t/topic/310069
时间: 2024-12-24 10:03:05
摘要:

說的好
Ai讓我們能
但腦袋總是空空的

标题: 三级了，抽个s15助助兴！
作者: #Nicker.cc
板块: #福利羊毛
编号: 310082
帖子: https://linux.do/t/topic/310082
时间: 2024-12-24 10:06:13
摘要:

庆祝三级，抽个s15助助兴。
Chat gpt 随机楼层抽取
截至12.25 0：00，辅导完作业开抽