Redis数据结构Redis有哪些数据类型？说说Redishashslot的概念？Hash是如何做到O(1)的查询和设置速度，以及扩容原理的？Redis布隆过滤器的数据类型有哪些？出现概率：★★★★★这个出现在面试过程中的概率特别高。Redis支持五种常用的数据类型：字符串（string）、散列（hash）、列表（list）、集合（set）和zsetsorted（集合：有序集合）。Redis的基本数据结构对应的底层实现如下图所示：1）Redis的字符串是可以修改的动态字符串。内部结构类似于Java的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，如图：len为当前字符串的实际长度，capacity为该字符串分配的可用空间.当字符串长度小于1M时，扩容会将现有空间扩大一倍。如果超过1M，在扩展的时候，一次只会多扩展1M的空间。字符串最大长度为512M。2)、hashRedisHash通过bucketing的方式解决hash冲突。它是一个无序字典。内部实现结构同样是数组+链表二维结构。当第一维哈希的数组位置发生碰撞时，碰撞的元素将使用链表串联起来。第一维是数组，第二维是链表。array_北京java训练中存放的是二维链表第一个元素的指针。3)、listRedis的链表相当于Java语言中的LinkedList，注意是链表而不是数组。这意味着列表的插入和删除操作非常快，O(1)时间复杂度，但是索引定位很慢，O(n)时间复杂度。链表的特点是：顺序可以从右到左或者从左到右重复，那么链表可以作为队列从左到左进入或者从右到退出对了，那么list就可以充当栈了4)、setset和字典很相似，它的内部实现就是上面hashTable的特殊实现，和字典的区别有两点：只关注key值，并且所有的值都是NULL。添加新数据时将执行重复数据删除。5)、zsetsortedsetzset是Redis一个很有特色的数据结构，它基于Set，提供了sortedorderedcollection。最重要的特点是它支持通过分数的权重来指定权重。一些排行榜和延时任务，比如指定1小时后执行，就是用这个数据结构实现的。6）如果你说你知道一些其他的数据结构比如：HyperLogLog、Geo、Pub/Sub、RedisModule、BloomFilter、RedisSearch、Redis-ML，面试官的眼睛会开始放光。Redis5.0带来了Stream类型。从字面上看，它是一种流类型，但实际上，从功能上看，它应该是Redis对消息队列（MQ，MessageQueue）的完美实现。用过Redis做消息队列的都知道，基于Reids的消息队列实现有很多种，比如：PUB/SUB，基于List的LPUSH+BRPOP的订阅/发布方式，基于Sorted-Set的。RedisStream的结构如图所示，它有一个消息链表，将所有添加的消息串在一起，每条消息都有唯一的ID和对应的内容。消息是持久化的，Redis重启后内容还在。Hash是如何做到O(1)的查询和设置速度，以及发生概率的扩展原理：★★★★★RedisHash通过bucketing解决hash冲突。它是一个无序字典。内部实现结构同样是数组+链表二维结构。当第一维哈希的数组位置发生碰撞时，碰撞的元素将使用链表串联起来。第一维是数组，第二维是链表。数组中存放的是指向二维链表第一个元素的指针。因为是通过数组取模的方式，可以实现O(1)的查询和设置速度。但是如果概率比较多，链表长度过长，查询时间复杂度会降为O(n)。这需要扩展。大字典的扩容非常耗时，需要重新申请一个新的数组。一般情况下，当哈希表中的元素个数等于一维数组的长度时，就会开始扩容。新扩充的数组是原数组的两倍旧字典大小，然后将旧字典的所有链表中的元素重新附加到新数组中。这是一个O(n)级别的操作。Redis使用progressiverehashexpansion将旧数组中的键值对rehash到新数组中的操作称为progressiverehash。Progressiverehash可以避免集中式rehash带来的巨大计算量。在progressiverehash的过程中，因为里面可能会存入新的键值对，Redis此时的做法是将新加入的键值对统一放入。进入ht[1]，这保证了ht[0]中键值对的数量只会减少。在进行rehash操作时，需要进行查询操作。这时候你会先查询ht[0]，然后再去ht[1]中的Query。说说Redishashslot的概念？出现概率：★★★Redis集群没有使用一致性哈希，而是引入了哈希槽的概念。Redis集群有16384个哈希槽。每个key通过CRC16校验后，取16384取模，决定放置在哪个slot，集群的每个节点负责一部分hashslot。Bloomfilter出现概率：★★★这个在面试中出现的概率主要取决于面试官的喜好，但如果被问到并且你能回答得更好，那可能是一个更好的加分项。布隆过滤器是Redis的一个高级功能。虽然这种结构的去重率并不完全准确，但它和其他结构一样有特定的应用场景。比如在处理海量数据时，可以使用Bloomfilter来实现去重。一些场景：百度的爬虫系统每天都会面对海量的URL数据。我们希望它每次只抓取最新的页面，不抓取没有更新的页面。去重，否则会严重影响执行效率。但是如果使用一个集合（collection）来加载这些URL地址，会造成资源空间的严重浪费。布隆过滤器（BloomFilter）是一种空间利用率高的概率数据结构，它由两部分组成：二进制向量（即位数组）和一系列随机映射函数（即哈希函数）。布隆过滤器使用exists()来确定元素是否存在于它自己的结构中。当布隆过滤器判断某个值存在时，这个值可能真的存在；当它说某个值不存在，那么这个值肯定不存在，误判的概率在1%左右。BloomFilter的原理1）、工作流程——添加元素Bloomfilter主要由一个位数组和一系列哈希函数组成，位数组的初始状态为0。下面简单介绍一下其工作流程布隆过滤器，如下图所示：2）、工作流程——判断一个元素是否存在当我们需要判断一个元素是否存在时，流程如下：首先对给定的元素再次执行hash计算，得到与添加元素时相同的位数组位置，判断得到的位置是否全为1，如果有一个为0，则说明该元素不存在。如果都为1，说明该元素可能存在。3）为什么可能“存在”你可能会问，为什么可能存在？其实原因很简单，那些设置为1的位置也有可能因为其他元素的操作而改变。比如元素1和元素2，这两个元素同时改变一个位置为1（如图1）。在这种情况下，我们无法确定“元素1”一定存在，这就是布隆过滤器误判的根本原因。BloomFilter的缺点Bloomfilter牺牲了判断的准确性和删除的便利性，在时间和空间上实现了比较高的效率，因为1）存在误判，可能找到的元素不在容器中，而是k个位置哈希后得到的都是1。如果bloomfilter中存储了黑名单，可以通过创建白名单来存储可能被误判的元素。2)、删除数据。放置在容器中的元素映射到位数组的k个位置中的1。删除的时候不能简单的直接设置为0，这样可能会影响其他元素的判断。可以考虑从walkingcoding转载的CountingBloomFilter文章
