面试题：Redis集合对象常用的底层实现方式有哪些及适用场景

Question

请阐述Redis集合对象常见的两种底层实现方式（intset和hashtable），并说明在何种情况下Redis会选择使用intset，何种情况下会使用hashtable来实现集合对象。

Answer 1

intset

1. 底层结构：intset是Redis集合对象的一种紧凑、高效的整数集合实现方式，它是一个有序的、无重复元素的整数数组。根据数组中所包含元素的类型，intset可以调整自身的编码方式，以节省内存空间。它有三个属性：encoding（编码方式，决定元素类型）、length（集合元素个数）、contents（存储元素的数组）。
2. 适用场景：当集合中的元素都是整数且元素数量较少时，Redis会选择使用intset。因为intset结构紧凑，在这种情况下能有效节省内存，并且由于其有序性，在查找元素时可以使用二分查找，具有较好的查找性能。

hashtable

1. 底层结构：这里的hashtable指的是字典结构（dict），它由哈希表（dict ht[2]）、哈希表节点（dictEntry）等组成。哈希表是一个数组，数组的每个元素都是一个指向哈希表节点的指针，哈希表节点保存了键值对。在处理哈希冲突时，Redis采用链地址法，即同一个哈希值的键值对都被分配到同一个链表中。
2. 适用场景：当集合中的元素不是整数，或者元素数量较多时，Redis会使用hashtable来实现集合对象。这是因为hashtable可以存储各种类型的元素，且在元素数量较多时，其基于哈希的查找操作平均时间复杂度为O(1)，能提供高效的查找、插入和删除操作，尽管在哈希冲突较多时性能会有所下降，但总体上适合大规模数据的存储和操作。