哈希表 · Redis 設計與實現（第一版）

# 哈希表 [TOC=2,3] `REDIS_HASH` （哈希表）是 [HSET](http://redis.readthedocs.org/en/latest/hash/hset.html#hset "(in Redis 命令參考 v2.8)") 、 [HLEN](http://redis.readthedocs.org/en/latest/hash/hlen.html#hlen "(in Redis 命令參考 v2.8)") 等命令的操作對象，它使用 `REDIS_ENCODING_ZIPLIST` 和 `REDIS_ENCODING_HT` 兩種編碼方式： ![digraph redis_hash { node [shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_HASH [label="哈希表\nREDIS_HASH", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_ZIPLIST [label="壓縮列表\nREDIS_ENCODING_ZIPLIST", fillcolor = "#FADCAD"]; REDIS_ENCODING_HT [label="字典\nREDIS_ENCODING_HT", fillcolor = "#FADCAD"]; // edge REDIS_HASH -> REDIS_ENCODING_ZIPLIST; REDIS_HASH -> REDIS_ENCODING_HT; // datastruct 1 ziplist [label="ziplist"]; REDIS_ENCODING_ZIPLIST -> ziplist; // datastruct 2 dict [label="dict.h/dict"]; REDIS_ENCODING_HT -> dict;}](https://box.kancloud.cn/2015-09-13_55f4effc77b77.svg) ### 字典編碼的哈希表當哈希表使用字典編碼時，程序將哈希表的鍵（key）保存為字典的鍵，將哈希表的值（value）保存為字典的值。哈希表所使用的字典的鍵和值都是字符串對象。下圖展示了一個包含三個鍵值對的哈希表： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; dict [label = "<head>dict\n |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#A8E270"]; number [label = "<head>StringObject | 10086"]; book [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; message [label = "<head>StringObject | \"hello moto\""]; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head;}](https://box.kancloud.cn/2015-09-13_55f4effc870e1.svg) ### 壓縮列表編碼的哈希表當使用 `REDIS_ENCODING_ZIPLIST` 編碼哈希表時，程序通過將鍵和值一同推入壓縮列表，從而形成保存哈希表所需的鍵-值對結構： ~~~ +---------+------+------+------+------+------+------+------+------+---------+ | ZIPLIST | | | | | | | | | ZIPLIST | | ENTRY | key1 | val1 | key2 | val2 | ... | ... | keyN | valN | ENTRY | | HEAD | | | | | | | | | END | +---------+------+------+------+------+------+------+------+------+---------+ ~~~ 新添加的 key-value 對會被添加到壓縮列表的表尾。當進行查找/刪除或更新操作時，程序先定位到鍵的位置，然后再通過對鍵的位置來定位值的位置。 ### 編碼的選擇創建空白哈希表時，程序默認使用 `REDIS_ENCODING_ZIPLIST` 編碼，當以下任何一個條件被滿足時，程序將編碼從 `REDIS_ENCODING_ZIPLIST` 切換為 `REDIS_ENCODING_HT` ： - 哈希表中某個鍵或某個值的長度大于 `server.hash_max_ziplist_value` （默認值為 `64` ）。 - 壓縮列表中的節點數量大于 `server.hash_max_ziplist_entries` （默認值為 `512` ）。 ### 哈希命令的實現哈希類型命令的實現全都是對字典和壓縮列表操作函數的包裝，以及幾個在兩種編碼之間進行轉換的函數，沒有特別要講解的地方。