字典

字典

字典， 又稱符號表（symbol table）、關(guān)聯(lián)數(shù)組（associative array）或者映射（map）， 是一種用于保存鍵值對（key-value pair）的抽象數(shù)據(jù)結(jié)構(gòu)。

在字典中， 一個鍵（key）可以和一個值（value）進行關(guān)聯(lián)（或者說將鍵映射為值）， 這些關(guān)聯(lián)的鍵和值就被稱為鍵值對。

字典中的每個鍵都是獨一無二的， 程序可以在字典中根據(jù)鍵查找與之關(guān)聯(lián)的值， 或者通過鍵來更新值， 又或者根據(jù)鍵來刪除整個鍵值對， 等等。

字典經(jīng)常作為一種數(shù)據(jù)結(jié)構(gòu)內(nèi)置在很多高級編程語言里面， 但 Redis 所使用的 C 語言并沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)， 因此 Redis 構(gòu)建了自己的字典實現(xiàn)。

字典在 Redis 中的應(yīng)用相當廣泛， 比如 Redis 的數(shù)據(jù)庫就是使用字典來作為底層實現(xiàn)的， 對數(shù)據(jù)庫的增、刪、查、改操作也是構(gòu)建在對字典的操作之上的。

舉個例子， 當我們執(zhí)行命令：

redis> SET msg "hello world"
OK

在數(shù)據(jù)庫中創(chuàng)建一個鍵為?"msg"?， 值為?"hello?world"?的鍵值對時， 這個鍵值對就是保存在代表數(shù)據(jù)庫的字典里面的。

除了用來表示數(shù)據(jù)庫之外， 字典還是哈希鍵的底層實現(xiàn)之一： 當一個哈希鍵包含的鍵值對比較多， 又或者鍵值對中的元素都是比較長的字符串時， Redis 就會使用字典作為哈希鍵的底層實現(xiàn)。

舉個例子，?website?是一個包含?10086?個鍵值對的哈希鍵， 這個哈希鍵的鍵都是一些數(shù)據(jù)庫的名字， 而鍵的值就是數(shù)據(jù)庫的主頁網(wǎng)址：

redis> HLEN website
(integer) 10086

redis> HGETALL website
1) "Redis"
2) "Redis.io"
3) "MariaDB"
4) "MariaDB.org"
5) "MongoDB"
6) "MongoDB.org"
# ...

website?鍵的底層實現(xiàn)就是一個字典， 字典中包含了?10086?個鍵值對：

• 其中一個鍵值對的鍵為?"Redis"?， 值為?"Redis.io"?。
• 另一個鍵值對的鍵為?"MariaDB"?， 值為?"MariaDB.org"?；
• 還有一個鍵值對的鍵為?"MongoDB"?， 值為?"MongoDB.org"?；

諸如此類。

除了用來實現(xiàn)數(shù)據(jù)庫和哈希鍵之外， Redis 的不少功能也用到了字典， 在后續(xù)的章節(jié)中會不斷地看到字典在 Redis 中的各種不同應(yīng)用。

本章接下來的內(nèi)容將對 Redis 的字典實現(xiàn)進行詳細的介紹， 并列出字典的操作 API 。

本章不會對字典的基本定義和基礎(chǔ)算法進行介紹， 如果有需要的話， 可以參考以下這些資料：

• 維基百科的 Associative Array 詞條（http://en.wikipedia.org/wiki/Associative_array）和 Hash Table 詞條（http://en.wikipedia.org/wiki/Hash_table）。
• 《算法：C 語言實現(xiàn)（第 1 ～ 4 部分）》一書的第 14 章。
• 《算法導(dǎo)論（第三版）》?一書的第 11 章。