[TOC] ## **什么是整數集合** **整數集合（intset）是集合鍵的底層實現之一**，當一個集合只包含整數值元素，并且這個集合的元素數量不多時，Redis就會使用整數集合作為集合鍵的底層實現。 如果我們創建一個只包含五個元素的集合鍵，并且集合中的所有元素都是整數值，那么這個集合鍵的底層實現就會是整數集合： ``` redis>?SADD?numbers?1?3?5?7?9 (integer)?5 redis>?OBJECT?ENCODING?numbers "intset" ``` ` ` ## **整數集合實現原理** 整數集合（intset）是Redis用于保存整數值的集合抽象數據結構，它可以保存類型為int16\_t、int32\_t或者int64\_t的整數值，并且保證集合中**不會出現重復元素**。 ### **整數集合的實現** 整數集合intset.h/intset結構: ``` typedef?struct?intset?{ ????// 編碼方式 ????uint32_t?encoding; ????//? 集合包含的元素數量 ????uint32_t?length; ????//? 保存元素的數組 ????int8_t?contents[]; }?intset; ``` contents數組是整數集合的底層實現：整數集合的每個元素都是contents數組的一個數組項（item），各個項在數組中按值的大小從小到大有序地排列，并且數組中不包含任何重復項。 length屬性記錄了整數集合包含的元素數量，也即是contents數組的長度。 contents數組并不保存任何int8\_t類型的值，contents數組的真正類型取決于encoding屬性的值： ``` 如果encoding屬性的值為INTSET\_ENC\_INT16，那么contents就是一個int16\_t類型的數組，數組里的每個項都是一個int16\_t類型的整數值（最小值為-32768，最大值為32767）。 ·如果encoding屬性的值為INTSET\_ENC\_INT32，那么contents就是一個int32\_t類型的數組，數組里的每個項都是一個int32\_t類型的整數值（最小值為-2147483648，最大值為2147483647）。 ·如果encoding屬性的值為INTSET\_ENC\_INT64，那么contents就是一個int64\_t類型的數組，數組里的每個項都是一個int64\_t類型的整數值（最小值為-9223372036854775808，最大值為9223372036854775807）。 ``` ` ` **整數集合示例：**  * encoding屬性的值為INTSET\_ENC\_INT16，表示整數集合的底層實現為int16\_t類型的數組，而集合保存的都是int16\_t類型的整數值。 * length屬性的值為5，表示整數集合包含五個元素。 * contents數組按從小到大的順序保存著集合中的五個元素。 * 因為每個集合元素都是int16\_t類型的整數值，所以contents數組的大小等于sizeof（int16\_t）\*5=16\*5=80位。 **升級整數集合示例：**  * encoding屬性的值為INTSET\_ENC\_INT64，表示整數集合的底層實現為int64\_t類型的數組，而數組中保存的都是int64\_t類型的整數值。 * length屬性的值為4，表示整數集合包含四個元素。 * contents數組按從小到大的順序保存著集合中的四個元素。 ·因為每個集合元素都是int64\_t類型的整數值，所以contents數組的大小為sizeof（int64\_t）\*4=64\*4=256位。 >雖然contents數組保存的四個整數值中，只有-2675256175807981027是真正需要用int64\_t類型來保存的，而其他的1、3、5三個值都可以用int16\_t類型來保存，不過根據整數集合的升級規則，當向一個底層為int16\_t數組的整數集合添加一個int64\_t類型的整數值時，整數集合已有的所有元素都會被轉換成int64\_t類型，所以contents數組保存的四個整數值都是int64\_t類型的，不僅僅是-2675256175807981027。 ` ` ## **升級** 每當我們要將一個新元素添加到整數集合里面，并且新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行升級（upgrade），然后才能將新元素添加到整數集合里面。 ` ` **升級分三個步驟進行**： * 根據新元素的類型，擴展整數集合底層數組的空間大小，并為新元素分配空間。 * 將底層數組現有的所有元素都轉換成與新元素相同的類型，并將類型轉換后的元素放置到正確的位上，而且在放置元素的過程中，需要繼續維持底層數組的有序性質不變。 * 將新元素添加到底層數組里面 ### **升級的示例** 示例：現在有一個INTSET\_ENC\_INT16編碼的整數集合，集合中包含三個int16\_t類型的元素：  每個元素都占用16位空間，所以整數集合底層數組的大小為3\*16=48位。 ` ` 整數集合的三個元素在這48位里的位置：  ` ` ### **升級過程** 將類型為int32\_t的整數值65535添加到整數集合里面，因為類型int32\_t比整數集合當前所有元素的類型都要長，所以在將65535添加到整數集合之前，程序需要先對整數集合進行升級。 1. 開始對底層數組進行空間重分配。 目前有3個元素，加上新元素int32_t 類型的數字65535，需要分配四個元素的空間，空間重新分配，底層數組的大小將是32*4=128位。  ` ` 雖然程序對底層數組進行了空間重分配，但數組原有的三個元素1、2、3仍然是int16\_t類型，這些元素還保存在數組的前48位里面 2. 三個元素轉換成int32\_t類型, 插入 將轉換后的元素放置到正確的位上面，而且在放置元素的過程中，需要維持底層數組的有序性質不變。 ` ` 首先，因為元素3在1、2、3、65535四個元素中排名第三，所以它將被移動到contents數組的索引2位置上，也即是數組64位至95位的空間內:  ` ` 接著，因為元素2在1、2、3、65535四個元素中排名第二，所以它將被移動到contents數組的索引1位置上，也即是數組的32位至63位的空間內：  ` ` 之后，因為元素1在1、2、3、65535四個元素中排名第一，所以它將被移動到contents數組的索引0位置上，即數組的0位至31位的空間內:  ` ` 然后，因為**元素65535**在1、2、3、65535四個元素中排名第四，所以它將被**添加到contents數組的索引3位置**上，也即是數組的96位至127位的空間內:  ` ` 最后，程序將**整數集合encoding屬性**的值**從INTSET\_ENC\_INT16改為INTSET\_ENC\_INT32**，并將**length屬性的值從3改為4**，設置完成之后的整數集合: >因為每次向整數集合添加新元素都可能會引起升級，而每次升級都需要對底層數組中已有的所有元素進行類型轉換，所以**向整數集合添加新元素的時間復雜度為O（N）**。 ` ` ### **升級之后新元素的擺放位置** 因為引發升級的新元素的長度總是比整數集合現有所有元素的長度都大，所以這個新元素的值要么就**大于所有現有元素**，要么就**小于所有現有元素**： * 在新元素小于所有現有元素的情況下，新元素會被放置在底層數組的最開頭（索引0）； * 在新元素大于所有現有元素的情況下，新元素會被放置在底層數組的最末尾（索引length-1）。 ## **升級的好處** ***** 整數集合的升級策略有兩個好處，一個是**提升整數集合的靈活性**，另一個是盡可能地**節約內存**。 ` ` ### 提升靈活性 整數集合可以通過自動升級底層數組來適應新元素，所以我們可**以隨意地將int16\_t、int32\_t或者int64\_t類型的整數添加到集合中**，而不必擔心出現類型錯誤，這種做法非常靈活。 >C語言是靜態類型語言，為了避免類型錯誤，我們通常不會將兩種不同類型的值放在同一個數據結構里面。我們一般只使用int16\_t類型的數組來保存int16\_t類型的值，只使用int32\_t類型的數組來保存int32\_t類型的值，諸如此類。 ### 節約內存 整數集合現在的做法既可以讓集合能同時保存三種不同類型的值，又可以確保升級操作只會在有需要的時候進行，這可以盡量節省內存 >要讓一個數組可以同時保存int16\_t、int32\_t、int64\_t三種類型的值，最簡單的做法就是直接使用int64\_t類型的數組作為整數集合的底層實現。不過這樣一來，即使添加到整數集合里面的都是int16\_t類型或者int32\_t類型的值，數組都需要使用int64\_t類型的空間去保存它們，從而出現**浪費內存**的情況。 如果我們一直只向整數集合添加int16\_t類型的值，那么整數集合的底層實現就會一直是int16\_t類型的數組，只有在我們要將int32\_t類型或者int64\_t類型的值添加到集合時，程序才會對數組進行升級。 ## **降級** 整數集合不支持降級操作，一旦對數組進行了升級，編碼就會一直保持升級后的狀態。 示例： 即使我們將集合里唯一一個真正需要使用int64\_t類型來保存的元素4294967295刪除了，整數集合的編碼仍然會維持INTSET\_ENC\_INT64，底層數組也仍然會是int64\_t類型的：   ## **整數集重點回顧** * 整數集合是集合鍵的底層實現之一。 * 整數集合的底層實現為數組，這個數組以有序、無重復的方式保存集合元素，在有需要時，程序會根據新添加元素的類型，改變這個數組的類型。 * 升級操作為整數集合帶來了操作上的靈活性，并且盡可能地節約了內存。 * 整數集合只支持升級操作，不支持降級操作。