4、整數集合

整數集合（intset）是 Redis 用于保存整數值的集合抽象數據結構， 可以保存?int16_t?、?int32_t?、?int64_t?的整數值， 并且保證集合中不會出現重復元素。

實現較為簡單：

typedef struct intset {// 編碼方式uint32_t encoding;// 集合包含的元素數量uint32_t length;// 保存元素的數組int8_t contents[];
} intset;

各個項在數組中從小到大有序地排列， 并且數組中不包含任何重復項。

雖然?intset?結構將?contents?屬性聲明為?int8_t?類型的數組， 但實際上?contents?數組并不保存任何?int8_t?類型的值 ——?contents?數組的真正類型取決于?encoding?屬性的值：

如果?encoding?屬性的值為?INTSET_ENC_INT16?， 那么?contents?就是一個?int16_t?類型的數組， 數組里的每個項都是一個?int16_t?類型的整數值 （最小值為?-32,768?，最大值為?32,767?）。

如果?encoding?屬性的值為?INTSET_ENC_INT32?， 那么?contents?就是一個?int32_t?類型的數組， 數組里的每個項都是一個?int32_t?類型的整數值 （最小值為?-2,147,483,648?，最大值為?2,147,483,647?）。

如果?encoding?屬性的值為?INTSET_ENC_INT64?， 那么?contents?就是一個?int64_t?類型的數組， 數組里的每個項都是一個?int64_t?類型的整數值 （最小值為?-9,223,372,036,854,775,808?，最大值為?9,223,372,036,854,775,807?）。

? ? 升級

c語言是靜態類型語言，不允許不同類型保存在一個數組。這樣第一，靈活性較差，第二，有時會用掉不必要的內存

比如用long long儲存1

為了提高整數集合的靈活性和節約內存，我們引入升級策略。

當我們要將一個新元素添加到集合里， 并且新元素類型比集合現有元素的類型都要長時， 集合需要先進行升級。

分為三步進行：

1. 根據新元素的類型， 擴展整數集合底層數組的空間大小， 并為新元素分配空間。
2. 將底層數組現有的所有元素都轉換成與新元素相同的類型， 并將類型轉換后的元素放置到正確的位上
3. 將新元素添加到底層數組里面。

因為每次添加新元素都可能會引起升級， 每次升級都要對已有元素類型轉換， 所以添加新元素的時間復雜度為?O(N)?。

因為引發升級的新元素比原數據都長，所以要么他是最大的，要么他是最小的。我們把它放在開頭或結尾即可。

?

? ? 降級

略略略，不管你們信不信，整數集合不支持降級操作。。我也不知道為啥

5、壓縮列表

?

壓縮列表是列表鍵和哈希鍵的底層實現之一。

當一個列表鍵只包含少量列表項，并且列表項都是小整數或者短字符串，redis就會用壓縮列表做列表鍵底層實現。

壓縮列表是 Redis 為了節約內存而開發的， 由一系列特殊編碼的連續內存塊組成的順序型（sequential）數據結構。

一個壓縮列表可以包含任意多個節點（entry）， 每個節點可以保存一個字節數組或者一個整數值。

具體實現：

具體說一下entry：

由三個部分組成：

1、previous_entry_length:記錄上一個節點的長度，這樣我們就可以從最后一路遍歷到開頭。

2、encoding：記錄了content所保存的數據類型和長度。（具體編碼不寫了，不重要）

3、content：保存節點值，可以是字節數組或整數。（具體怎么壓縮的等我搞明白再補）

? ? 連鎖更新

前面說過， 每個節點的?previous_entry_length?屬性都記錄了前一個節點的長度：

• 如果前一節點的長度<?254?KB， 那么?previous_entry_length?需要用?1?字節長的空間
• 如果前一節點的長度>=254?KB， 那么?previous_entry_length?需要用?5?字節長的空間

現在， 考慮這樣一種情況： 在一個壓縮列表中， 有多個連續的、長度介于?250?字節到?253?字節之間的節點 ，這時， 如果我們將一個長度大于等于?254?字節的新節點?new?設置為壓縮列表的表頭節點。。。。

然后腦補一下，就會導致連鎖擴大每個節點的空間對吧？e(i)因為e(i-1)的擴大而擴大，i+1也是如此，以此類推。。。

?

刪除節點同樣會導致連鎖更新。

這個事情只是想說明一個問題：插入刪除操作的最壞時間復雜度其實是o(n*n)，因為每更新一個節點都要o(n)。

但是，也不用太過擔心，因為這種特殊情況并不多見，這些命令的平均復雜度依舊是o(n)。