面试官：我在你的简历上看到，你在项目中使用了Redis，并用它来做缓存。能介绍一下Redis的五种基本数据类型吗？于是我说：emmm，在Redis中有string字符串，hash哈希，list列表，set无序集合，zset有序集合，这五种数据类型。面试官：除了这五种基本数据类型，你了解过Redis提供的其他附加数据类型吗？你说你用Redis做缓存。比如我查询一个用户用一个本来就不存在的ID调用你Interface，如何防止这样的缓存穿透？没办法硬着头皮上去：emm，我学过bitMap，但是没接触过缓存穿透。面试官：你用过bitMap实现过什么功能吗？面试官心想：完了，完了，完了，都是FrancisQ惹的祸，回去找他算账。我的心已经凉了：不会。..我上面写的其实只是一个没有参加过面试的新手。我大三了，明年想实习，所以我会写一些文章来分享和总结自己（不是为了赚钱）。如果觉得FrancisQ写的还不错，请给我点个赞(#^.^#)，其实我只是想尽快上LV4。当然我也分享了SSM框架、MySQL等的原理分析和实现等其他文章，有兴趣的也可以关注我。当然，如果你有实习岗位，可以帮帮我，哈哈哈。话不多说，今天就为大家带来Redis中四种特殊的数据结构：bitmap、hyperLogLog、bloomFilter、GeoHash。这四种数据结构其实和算法层面有些类似。比如GeoHash其实是一个zset，bitmap是一个string，但是使用的方法不同导致的功能更多。BloomFilter介绍及场景使用如果你对BloomFilter还不熟悉，下图你一定很熟悉吧？别告诉我你只玩过杀虫王。BloomFilter的中文名称是布隆过滤器。作为滤镜，是不是感觉有点像LOL里布卢姆的E技能（坚不可摧）？Bloomfilter是由一个叫Bloom的人提出的。正是通过一个大的位数组和几个不同的哈希函数，我们可以将布隆过滤器理解为一个不精确的集合。我们都知道set可以去重，使用set可以帮助我们判断某个元素是否已经存在于set中或者帮助我们实现去重功能。然而set在提供精准去重的同时，也给我们带来了一个更大的问题——空间消耗。比如我们此时在爬取网页时，需要对爬取的url进行去重，避免爬到已经爬取过的网站。如果我们使用set，就意味着我们需要将所有爬取到的url放入一个集合中。假设一个url是64字节，那么1亿个url意味着我们需要占用6GB，10亿大概是60GB。注意是内存。比如这个时候我们需要过滤垃圾邮件或者垃圾短信，我们需要从数十亿的垃圾邮件列表或者垃圾电话列表中判断此时的邮件或者短信是不是垃圾邮件。如果这时候用set，占用的空间不用我多说，也是几百GB的级别。在上面的采访中，我提到了缓存穿透。用户故意请求数据库不存在（例如，ID=-1）。几千，几万同时进来？你的数据库能承受得住吗？那我们这时候就用set来处理，占用这么多内存空间，你觉得值得吗？？？或者，还有更好的方法？已经？上面提到的三个典型场景，网站去重、垃圾邮件过滤、缓存穿透，都可以使用BloomFilter完美解决。大家有没有发现上面三种场景都不需要非常高的精度，尤其是垃圾邮件过滤。事实上，偶尔收到几封垃圾邮件也没关系。和缓存穿透一样，也正好遇到了BloomFilter的一个特性。他说可能没有，他说一定没有。我说如果你的ID在数据库中不存在，那就真的不存在了。我过滤你。这么自信，干嘛打我？？？讨论了这么久的概念和应用场景，你是否还在为BloomFilter如何去重而困惑？下面说说BloomFilter的实现原理。首先给大家看一张结构图。其中F、G、H是几个无偏Hash函数，最下面是一个大的位数组。当我们向BloomFilter添加数据时，它会先对我们的数据（key）（这里是FGH）进行几次哈希运算，每次哈希运算都会得到一个未使用的位数组索引下标。这个时候我们将计算出来的下标位置的值都改为1，如果判断一个元素是否存在，判断的地方所有的索引下标值都是1。其实你也发现了在BloomFilter中，不同key计算出的下标会重复出现，如上图，这就是错误的来源（可以配置初始大小和错误率来控制错误）他说有的是错误的有一定有，而且他说如果没有，就一定没有这个特征的根本原因，因为如果全是0或者有0，那肯定是不存在的。如果全为1，则可能是其他键输入的1。基本使用由于BloomFilter是Redis的扩展模块，需要另外下载，可以使用Docker拉取。安装步骤我就不详细解释了，大家可以去它的github上学习如何安装，安装后我们就可以愉快的使用了。bf.addkeyelement添加bf.existskeyelement判断是否存在bf.maddkeyelement1element2...批量添加bf.mexistskeyelement1element2...批量判断命令很简单，大家可以自己试试。HyperLogLog介绍及场景使用Redis中还有一个数据结构HyperLogLog可能会出错。我们先想一个场景。老板让我们计算页面的UV怎么办？如果访问量不大，用set去重用户是完全可以的，但是如果有几百万或者几千万的访问量，那么又会遇到上面说的浪费空间的问题。如果这时候我们有一个可以去重和计数的数据结构就好了。这时，HyperLogLog登场了！它可以提供一个不准确的去重计数方案（误差值在0.81%左右），不准确就是不准确。您希望UV的准确度如何？我们可以接受0.81%。最重要的是HyperLogLog只占用12KB内存。使用方法和场景实践pfaddkeyelementAddpfcountkeyCalculatepfmergedestkeysourcekey1sourcekey2...合并命令都是以pf开头的，因为它是由一个叫PhilippeFlajolet的教授发明的。可以看到这三个基本命令非常简单易掌握。让我们手工完成吧。BitMap介绍及使用场景首先我们来思考一个比较有意思的场景。老板要你统计一年内多个用户同时在线的天数。这个时候你该怎么办？你可能会想到使用hash存储，太浪费空间了，有没有更好的办法？答案是肯定的，Redis中使用的是bitmap位图。我们知道字符串中的一个字符是用8位来表示的（如上图所示）。在Redis中，位图的底层是字符串，也可以说字符串的底层是位图。如果我们有这个，我们可以用它来统计用户在指定时间内登录的次数吗？即一个位置代表一天，0表示不签到，1表示签到。上图中，用户八天内签到四次Second-rate。Redis中的位图也提供了对多个位图进行AND、OR、XOR运算的命令，当然也提供了单个位图的NOT操作。这是否为您提供了一些满足我们最初需求的想法？基本命令setbitkeyindex0/1设置某位的值getbitkeyindex获取某位的值bitcountkeystartend获取指定范围内的1的值需要注意的是这里的开始和结束指的是字符位置不是位位置！！！包括下面的bitpos也是bitposkeybitstartend获取start到end其值为bit的第一个字符索引范围的位置bitopand/or/xor/notdestkeykey1key2对多个位图进行逻辑运算。位图还有一个比较有意思的命令是bitfield，这里就不过多介绍了，有兴趣的同学可以自行了解。动手实践我们先来实现统计用户签到次数的功能。还记得我们最初的问题吗？要统计一年中多个用户同时在线的天数，有了位图还怕什么？GeoHash介绍及场景应用GeoHash常用来计算附近的人和附近的商店。想象一下，如果我们使用关系型数据库来存储一个元素的地址（id、经度、纬度）。我们如何计算此时附近的人呢？是不是要遍历所有元素位置，做距离计算？这显然是不可能的。当然你可以划分区域，用SQL语句圈出区域，然后构建双向复合索引来提高性能，但是数据库的并发能力毕竟有限，用Redis可以吗？答案是肯定的，Redis中使用GeoHash提供了很好的解决方案。具体原理是把地球看成一个平面，把二维坐标映射成一维（精度损失原因）。对算法感兴趣的可以自行深入了解，篇幅有限就不过多解释了。基本命令与实战geoaddkeylongitudelatitude元素（后面可以配置多个三元组）添加元素geodistkeyelement1element2unit计算两个元素的距离geoposkeyelement[element]获取元素的位置geohashkeyelement获取元素hashgeoradiusbymemberkeyelementdistanceValueunitcountcountValueASC/DESC[withdist][withhash][withcoord]获取元素附近的元素可以附加选项[distance][hash][coordinates]georadiuskeylongitudelatitudedistanceValueunitcountcountValueASC/DESC[withdist][withhash][withcoord]同上，只是将元素改为指定的坐标值。小结在这篇文章中，我想你已经介绍了Redis另外四种特殊的数据结构，分别是BloomFilter、HyperLogLog、BitMap和GeoHash。而且我还想让大家介绍一下它们的使用方法，它们的应用场景是什么。希望对您有所帮助。非常感谢你能看到这篇，如果你喜欢或者对你有帮助，别忘了点个赞哦。也可以关注我，我会经常做一些学习分享给大家。
