# 字典
>[info] 字典, 又稱符號表(symbol table)、關聯數組(associative array)或者映射(map), 是一種用于保存鍵值對(key-value pair)的抽象數據結構。
在字典中, 一個鍵(key)可以和一個值(value)進行關聯(或者說將鍵映射為值), 這些關聯的鍵和值就被稱為鍵值對。
字典中的每個鍵都是獨一無二的, 程序可以在字典中根據鍵查找與之關聯的值, 或者通過鍵來更新值, 又或者根據鍵來刪除整個鍵值對, 等等。
字典經常作為一種數據結構內置在很多高級編程語言里面, 但 Redis 所使用的 C 語言并沒有內置這種數據結構, 因此 Redis 構建了自己的字典實現。
字典在 Redis 中的應用相當廣泛, 比如 Redis 的數據庫就是使用字典來作為底層實現的, 對數據庫的增、刪、查、改操作也是構建在對字典的操作之上的。
舉個例子, 當我們執行命令:
~~~
redis> SET msg "hello world"
OK
~~~
在數據庫中創建一個鍵為?`"msg"`?, 值為?`"hello?world"`?的鍵值對時, 這個鍵值對就是保存在代表數據庫的字典里面的。
除了用來表示數據庫之外, 字典還是哈希鍵的底層實現之一: 當一個哈希鍵包含的鍵值對比較多, 又或者鍵值對中的元素都是比較長的字符串時, Redis 就會使用字典作為哈希鍵的底層實現。
舉個例子,?`website`?是一個包含?`10086`?個鍵值對的哈希鍵, 這個哈希鍵的鍵都是一些數據庫的名字, 而鍵的值就是數據庫的主頁網址:
~~~
redis> HLEN website
(integer) 10086
redis> HGETALL website
1) "Redis"
2) "Redis.io"
3) "MariaDB"
4) "MariaDB.org"
5) "MongoDB"
6) "MongoDB.org"
# ...
~~~
`website`?鍵的底層實現就是一個字典, 字典中包含了?`10086`?個鍵值對:
* 其中一個鍵值對的鍵為?`"Redis"`?, 值為?`"Redis.io"`?。
* 另一個鍵值對的鍵為?`"MariaDB"`?, 值為?`"MariaDB.org"`?;
* 還有一個鍵值對的鍵為?`"MongoDB"`?, 值為?`"MongoDB.org"`?;
諸如此類。
除了用來實現數據庫和哈希鍵之外, Redis 的不少功能也用到了字典, 在后續的章節中會不斷地看到字典在 Redis 中的各種不同應用。
本章接下來的內容將對 Redis 的字典實現進行詳細的介紹, 并列出字典的操作 API 。
本章不會對字典的基本定義和基礎算法進行介紹, 如果有需要的話, 可以參考以下這些資料:
* 維基百科的 Associative Array 詞條([http://en.wikipedia.org/wiki/Associative_array](http://en.wikipedia.org/wiki/Associative_array))和 Hash Table 詞條([http://en.wikipedia.org/wiki/Hash_table](http://en.wikipedia.org/wiki/Hash_table))。
* [《算法:C 語言實現(第 1 ~ 4 部分)》](http://book.douban.com/subject/4065258/)一書的第 14 章。
* [《算法導論(第三版)》](http://book.douban.com/subject/3904676/)?一書的第 11 章。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤