每當我們要將一個新元素添加到整數集合里面, 并且新元素的類型比整數集合現有所有元素的類型都要長時, 整數集合需要先進行升級(upgrade), 然后才能將新元素添加到整數集合里面。
升級整數集合并添加新元素共分為三步進行:
1. 根據新元素的類型, 擴展整數集合底層數組的空間大小, 并為新元素分配空間。
2. 將底層數組現有的所有元素都轉換成與新元素相同的類型, 并將類型轉換后的元素放置到正確的位上, 而且在放置元素的過程中, 需要繼續維持底層數組的有序性質不變。
3. 將新元素添加到底層數組里面。
舉個例子, 假設現在有一個?`INTSET_ENC_INT16`?編碼的整數集合, 集合中包含三個?`int16_t`?類型的元素, 如圖 6-3 所示。

因為每個元素都占用?`16`?位空間, 所以整數集合底層數組的大小為?`3?*?16?=?48`?位, 圖 6-4 展示了整數集合的三個元素在這?`48`?位里的位置。

現在, 假設我們要將類型為?`int32_t`?的整數值?`65535`?添加到整數集合里面, 因為?`65535`?的類型?`int32_t`?比整數集合當前所有元素的類型都要長, 所以在將?`65535`?添加到整數集合之前, 程序需要先對整數集合進行升級。
升級首先要做的是, 根據新類型的長度, 以及集合元素的數量(包括要添加的新元素在內), 對底層數組進行空間重分配。
整數集合目前有三個元素, 再加上新元素?`65535`?, 整數集合需要分配四個元素的空間, 因為每個?`int32_t`?整數值需要占用?`32`?位空間, 所以在空間重分配之后, 底層數組的大小將是?`32?*?4?=?128`?位, 如圖 6-5 所示。

雖然程序對底層數組進行了空間重分配, 但數組原有的三個元素?`1`?、?`2`?、?`3`?仍然是?`int16_t`?類型, 這些元素還保存在數組的前?`48`?位里面, 所以程序接下來要做的就是將這三個元素轉換成?`int32_t`?類型, 并將轉換后的元素放置到正確的位上面, 而且在放置元素的過程中, 需要維持底層數組的有序性質不變。
首先, 因為元素?`3`?在?`1`?、?`2`?、?`3`?、?`65535`?四個元素中排名第三, 所以它將被移動到?`contents`?數組的索引?`2`?位置上, 也即是數組?`64`?位至?`95`?位的空間內, 如圖 6-6 所示。

接著, 因為元素?`2`?在?`1`?、?`2`?、?`3`?、?`65535`?四個元素中排名第二, 所以它將被移動到?`contents`?數組的索引?`1`?位置上, 也即是數組的?`32`位至?`63`?位的空間內, 如圖 6-7 所示。

之后, 因為元素?`1`?在?`1`?、?`2`?、?`3`?、?`65535`?四個元素中排名第一, 所以它將被移動到?`contents`?數組的索引?`0`?位置上, 也即是數組的?`0`?位至?`31`?位的空間內, 如圖 6-8 所示。

然后, 因為元素?`65535`?在?`1`?、?`2`?、?`3`?、?`65535`?四個元素中排名第四, 所以它將被添加到?`contents`?數組的索引?`3`?位置上, 也即是數組的`96`?位至?`127`?位的空間內, 如圖 6-9 所示。

最后, 程序將整數集合?`encoding`?屬性的值從?`INTSET_ENC_INT16`?改為?`INTSET_ENC_INT32`?, 并將?`length`?屬性的值從?`3`?改為?`4`?, 設置完成之后的整數集合如圖 6-10 所示。

因為每次向整數集合添加新元素都可能會引起升級, 而每次升級都需要對底層數組中已有的所有元素進行類型轉換, 所以向整數集合添加新元素的時間復雜度為??。
其他類型的升級操作, 比如從?`INTSET_ENC_INT16`?編碼升級為?`INTSET_ENC_INT64`?編碼, 或者從?`INTSET_ENC_INT32`?編碼升級為?`INTSET_ENC_INT64`?編碼, 升級的過程都和上面展示的升級過程類似。
升級之后新元素的擺放位置
因為引發升級的新元素的長度總是比整數集合現有所有元素的長度都大, 所以這個新元素的值要么就大于所有現有元素, 要么就小于所有現有元素:
* 在新元素小于所有現有元素的情況下, 新元素會被放置在底層數組的最開頭(索引?`0`?);
* 在新元素大于所有現有元素的情況下, 新元素會被放置在底層數組的最末尾(索引?`length-1`?)。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤