當要將一個新的鍵值對添加到字典里面時, 程序需要先根據鍵值對的鍵計算出哈希值和索引值, 然后再根據索引值, 將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。
Redis 計算哈希值和索引值的方法如下:
~~~
# 使用字典設置的哈希函數,計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 屬性和哈希值,計算出索引值
# 根據情況不同, ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;
~~~

舉個例子, 對于圖 4-4 所示的字典來說, 如果我們要將一個鍵值對?`k0`?和?`v0`?添加到字典里面, 那么程序會先使用語句:
~~~
hash = dict->type->hashFunction(k0);
~~~
計算鍵?`k0`?的哈希值。
假設計算得出的哈希值為?`8`?, 那么程序會繼續使用語句:
~~~
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;
~~~
計算出鍵?`k0`?的索引值?`0`?, 這表示包含鍵值對?`k0`?和?`v0`?的節點應該被放置到哈希表數組的索引?`0`?位置上, 如圖 4-5 所示。

當字典被用作數據庫的底層實現, 或者哈希鍵的底層實現時, Redis 使用 MurmurHash2 算法來計算鍵的哈希值。
MurmurHash 算法最初由 Austin Appleby 于 2008 年發明, 這種算法的優點在于, 即使輸入的鍵是有規律的, 算法仍能給出一個很好的隨機分布性, 并且算法的計算速度也非常快。
MurmurHash 算法目前的最新版本為 MurmurHash3 , 而 Redis 使用的是 MurmurHash2 , 關于 MurmurHash 算法的更多信息可以參考該算法的主頁:?[http://code.google.com/p/smhasher/](http://code.google.com/p/smhasher/)?。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤