隨著操作的不斷執行, 哈希表保存的鍵值對會逐漸地增多或者減少, 為了讓哈希表的負載因子(load factor)維持在一個合理的范圍之內, 當哈希表保存的鍵值對數量太多或者太少時, 程序需要對哈希表的大小進行相應的擴展或者收縮。
擴展和收縮哈希表的工作可以通過執行 rehash (重新散列)操作來完成, Redis 對字典的哈希表執行 rehash 的步驟如下:
1. 為字典的?`ht[1]`?哈希表分配空間, 這個哈希表的空間大小取決于要執行的操作, 以及?`ht[0]`?當前包含的鍵值對數量 (也即是`ht[0].used`?屬性的值):
* 如果執行的是擴展操作, 那么?`ht[1]`?的大小為第一個大于等于?`ht[0].used?*?2`?的??(`2`?的?`n`?次方冪);
* 如果執行的是收縮操作, 那么?`ht[1]`?的大小為第一個大于等于?`ht[0].used`?的??。
2. 將保存在?`ht[0]`?中的所有鍵值對 rehash 到?`ht[1]`?上面: rehash 指的是重新計算鍵的哈希值和索引值, 然后將鍵值對放置到?`ht[1]`?哈希表的指定位置上。
3. 當?`ht[0]`?包含的所有鍵值對都遷移到了?`ht[1]`?之后 (`ht[0]`?變為空表), 釋放?`ht[0]`?, 將?`ht[1]`?設置為?`ht[0]`?, 并在?`ht[1]`?新創建一個空白哈希表, 為下一次 rehash 做準備。
舉個例子, 假設程序要對圖 4-8 所示字典的?`ht[0]`?進行擴展操作, 那么程序將執行以下步驟:
1. `ht[0].used`?當前的值為?`4`?,?`4?*?2?=?8`?, 而?`8`?()恰好是第一個大于等于?`4`?的?`2`?的?`n`?次方, 所以程序會將?`ht[1]`?哈希表的大小設置為?`8`?。 圖 4-9 展示了?`ht[1]`?在分配空間之后, 字典的樣子。
2. 將?`ht[0]`?包含的四個鍵值對都 rehash 到?`ht[1]`?, 如圖 4-10 所示。
3. 釋放?`ht[0]`?,并將?`ht[1]`?設置為?`ht[0]`?,然后為?`ht[1]`?分配一個空白哈希表,如圖 4-11 所示。
至此, 對哈希表的擴展操作執行完畢, 程序成功將哈希表的大小從原來的?`4`?改為了現在的?`8`?。




## 哈希表的擴展與收縮
當以下條件中的任意一個被滿足時, 程序會自動開始對哈希表執行擴展操作:
1. 服務器目前沒有在執行?BGSAVE?命令或者?BGREWRITEAOF?命令, 并且哈希表的負載因子大于等于?`1`?;
2. 服務器目前正在執行?BGSAVE?命令或者?BGREWRITEAOF?命令, 并且哈希表的負載因子大于等于?`5`?;
其中哈希表的負載因子可以通過公式:
~~~
# 負載因子 = 哈希表已保存節點數量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
~~~
計算得出。
比如說, 對于一個大小為?`4`?, 包含?`4`?個鍵值對的哈希表來說, 這個哈希表的負載因子為:
~~~
load_factor = 4 / 4 = 1
~~~
又比如說, 對于一個大小為?`512`?, 包含?`256`?個鍵值對的哈希表來說, 這個哈希表的負載因子為:
~~~
load_factor = 256 / 512 = 0.5
~~~
根據?BGSAVE?命令或?BGREWRITEAOF?命令是否正在執行, 服務器執行擴展操作所需的負載因子并不相同, 這是因為在執行?BGSAVE?命令或BGREWRITEAOF?命令的過程中, Redis 需要創建當前服務器進程的子進程, 而大多數操作系統都采用寫時復制([copy-on-write](http://en.wikipedia.org/wiki/Copy-on-write))技術來優化子進程的使用效率, 所以在子進程存在期間, 服務器會提高執行擴展操作所需的負載因子, 從而盡可能地避免在子進程存在期間進行哈希表擴展操作, 這可以避免不必要的內存寫入操作, 最大限度地節約內存。
另一方面, 當哈希表的負載因子小于?`0.1`?時, 程序自動開始對哈希表執行收縮操作。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤