本文參考 嗨客網 Redis面試題
Redis整數集合
Redis 中的整數集合(intset)并不是一個基礎的資料結構，而是 Redis 自己設計的一種存儲結構，是集合鍵的底層實作之一，當一個集合隻包含整數值元素，并且這個集合的元素數量不多時, Redis 就會使用整數集合作為集合鍵的底層實作。
整數集合實作
整數集合(intset)是 Redis 用于儲存整數值的集合抽象資料結構，它可以儲存類型為 int16_t、int32_t 或者 int64_t 的整數值，并且保證集合中不會出現重複元素。結構定義如下：
//每個intset結構表示一個整數集合
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合中包含的元素數量
uint32_t length;
//儲存元素的數組
int8_t contents[];
} intset;
contents 數組是整數集合的底層實作，整數集合的每個元素都是 contents 數組的個數組項(item)，各個項在數組中按值的大小從小到大有序地排列，并且數組中不包含任何重複項。
length 屬性記錄了數組的長度。
intset 結構将 contents 屬性聲明為 int8_t 類型的數組，但實際上 contents 數組并不儲存任何 int8_t 類型的值, contents 數組的真正類型取決于 encoding 屬性的值。encoding 屬性的值為 INTSET_ENC_INT16 則數組就是 uint16_t 類型，數組中的每一個元素都是 int16_t 類型的整數值(-32768——32767)，encoding 屬性的值為 INTSET_ENC_INT32 則數組就是 uint32_t 類型，數組中的每一個元素都是 int16_t 類型的整數值(-2147483648——2147483647)。
結構如下圖所示：
如上圖，為一 int16_t 類型的整數集合，我們可以看到數組中存儲了 5 個 int16_t 類型的整數，它們按照從小到大的順序依次排列。這個時候我們思考一個問題。如果這個時候存入一個 int32_t 類型的整數會怎麼樣？記憶體溢出？這個時候就要提到整數集合的更新。
整數集合的更新
更新過程
正如上面所提到的問題，每當我們要将一個新元素添加到整數集合裡面，并且新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行更新，然後才能将新元素添加到整數集合裡面。更新整數集合并添加新元素主要分三步來進行。
- 根據新元素的類型，擴充整數集合底層數組的空間大小，并為新元素配置設定空間。
- 将底層數組現有的所有元素都轉換成與新元素相同的類型，并将類型轉換後的元素放置到正确的位上，而且在放置元素的過程中，需要繼續維持底層數組的有序性質不變。
- 将新元素添加到底層數組裡面。
整數集合更新的優點
提升靈活性
因為 C 語言 是靜态類型語言，為了避免類型錯誤，我們通常不會将兩種不同類型的值放在同一個資料結構裡面。
例如，我們一般隻使用 int16_t 類型的數組來儲存 int16_t 類型的值，隻使用 int32_t 類型的數組來儲存 int32_t 類型的值，諸如此類。但是，因為整數集合可以通過自動更新底層數組來适應新元素，是以我們可以随意地将 int16_t、int32_t 或者 int64_t 類型的整數添加到集合中，而不必擔心出現類型錯誤，這種做法非常靈活。
節約記憶體
要讓一個數組可以同時儲存 int16_t、int32_t、int64_t 三種類型的值，最簡單的做法就是直接使用 int64_t 類型的數組作為整數集合的底層實作。不過這樣一來，即使添加到整數集合裡面的都是 int16_t 類型或者 int32_t 類型的值，數組都需要使用 int64_t 類型的空間去儲存它們，進而出現浪費記憶體的情況。
而整數集合現在的做法既可以讓集合能同時儲存三種不同類型的值，又可以確定更新操作隻會在有需要的時候進行，這可以盡量節省記憶體。如果我們一直隻向整數集合添加 int16_t 類型的值，那麼整數集合的底層實作就會一直是 int16_t 類型的數組，隻有在我們要将 int32_t 類型或者 int64_t 類型的值添加到集合時，程式才會對數組進行更新。
降級
整數集合不支援降級操作，一旦對數組進行了更新，編碼就會一直保持更新後的狀态。也就是說一旦我們向一個 int16_t 的整數集合内添加了一個 int32_t 的元素後，整數集合将更新到 int32_t 類型。即使後續的操作中我們删除了這個元素，整數集合還是會保持 int32_t 類型的狀态。
整數集合常用操作時間複雜度
| 操作 | 時間複雜度 |
|---|---|
| 建立一個新的整數集合 | O(1) |
| 添加指定元素到集合 | O(N) |
| 移除指定元素 | O(N) |
| 判斷指定元素是否在集合中 | O(logN) |
| 随機傳回一個元素 | O(1) |
| 取出在指定索引上的元素 | O(1) |
| 傳回集合包含的元素個數 | O(1) |
| 傳回集合占用的記憶體位元組數 | O(1) |
總結
- 整數集合是 Redis 自己設計的一種存儲結構，集合鍵的底層實作之一。
- 整數集合的底層實作為數組，這個數組以有序、無重複的方式儲存集合元素，在有需要時，程式會根據新添加元素的類型，改變這個數組的類型。
- 更新操作為整數集合帶來了操作上的靈活性，并且盡可能地節約了記憶體。
- 整數集合隻支援更新操作，不支援降級操作。
更多
原文連結：連結
其他：目錄
更多文章，可以關注下方公衆号：