一道很有意思的Redis面试题,关于Bitmap算法,我选出了一些优质评论

原创 吴就业 128 0 2020-03-19

本文为博主原创文章,未经博主允许不得转载。

本文链接:https://wujiuye.com/article/f0a45ae265ea47fe89c7988794e71aa8

作者:吴就业
链接:https://wujiuye.com/article/f0a45ae265ea47fe89c7988794e71aa8
来源:吴就业的网络日记
本文为博主原创文章,未经博主允许不得转载。

起源于我在一个短视频中分享的一道面试题,当然,这道面试题我确实在工作中用过,只是业务场景不同。

题目是:假设有这样一个需求场景,需要将所有用户的商品id存储到redis缓存,某个接口要求判断请求的商品id是否在数据库中,也就是是否在redis缓存中,请问你觉得使用哪种数据结构类型缓存商品id最合适?

这道题考察面试者:

1

某位朋友提问:

请教个问题,网上说bitmap常用来进行用户活跃度,签到的统计。它的bit位也只能存储01,为什么用bitmap能提升性能呢?

我的回答:

Set集合查询时间复杂度是O(1),但是有Hash冲突,可能带有链表的遍历,而bitmap访问相当于数组下标。

bitmap只用1bit存一个商品id,在商品id分布均匀情况下,节省的内存是存储商品id字符串的多少倍?需求场景是只需判断一个商品id是否在缓存中,那么01还不够吗?setbit key 商品id 0/1

追问:

我懂了,命令SETBIT key offset value,这里是将id作为offset使用,不同的id对应不同的位,而不是作为key使用,多谢解答[赞]。

另一位朋友作出的解答很好:

你确定bitmap一定可以?我要是没记错key范围是int,很多id都是long

我的解释:

确实[赞]。这时候就是下一个问题了。

key不是只能有一个,可以用多个key存储,这就是分桶的概念。假设第一个桶,也就是key1,用来1100000000id,那么第二个桶就可以存100000000200000000亿的id,不过是先将id减去100000000。有没有必要分桶,主要还是看商品数量到一个什么级别,以及商品id的最大值。

2

某位朋友提问:

我们项目里用户iduuid生成的14位数值,本来想存bitmap,想想还不如sql统计登陆的日志呢[泪奔]

我的回答:

非整数类型用不了这种数据类型存储,可以借用布隆过滤器插件实现,但是有误差存在,需要确保误差不会影响正常业务。

一般都是使用自增主键。id作为主键索引,使用自增主键比用uuid的插入性能高,这是索引B+树的知识点。

追问:

如果是分布式数据库用自增主键可能会有冲突吧?

我的回答:

分布式数据库可以用雪花算法等分布式 id生成算法,id可以不是自增,但最好是保持增长的,单个数据库节点的单个表的主键确保是增长的。uuid这种太随机。

提问者的自我回答:

对,因为插入时候b+数是按顺序向右扩展的。

#后端

声明:公众号、CSDN、掘金的曾用名:“Java艺术”,因此您可能看到一些早期的文章的图片有“Java艺术”的水印。

文章推荐

如何优化大表分页查询的Limit性能问题?

如果表的数据量非常大,我们除了优化查询总数的`sql`之外,还是需要优化`limit`的。

Redis实现原子操作的两种方式与商品入库出库解决方案

想要实现针对多个key的复杂原子操作有两种方法。一种是Watch+Multi,即监视器加事务方式,另一种便是通过执行lua脚本实现。

教你如何写出高性能的Mybatis分页插件

本篇介绍是什么原因导致的`mybatis-plus`分页插件性能下降,以及如何通过使用`JsqlParser`这个开源的`sql`解析工具包与`mybatis-plus`提供的自定义`sql`优化器功能,自己实现高性能的分页插件。

一篇文章说清楚Java的全局异常处理,深入到hotspot源码

本篇将介绍如何使用Java提供的全局异常处理,以及分析一点hotspot虚拟机的源码,让大家了解虚拟机是如何将异常交给全局异常处理器处理的。

使用Docker部署用于学习的ElasticSearch集群

在Linux服务器上使用 Docker安装ElasticSearch集群。

使用Mybatis-Plus提高开发效率

使用`mybatis-plus`可以少写很多常用的`SQL`,通过继承`BaseMapper`使用,还可以动态拼接`SQL`。第一眼看到我还以为是`JPA`。