一个空的哈希表。
使用链地址法解决冲突的哈希表。
普通状态下（未在进行 rehash）的字典。
包含了键值对的字典。
字典的 rehash 过程。
字典的渐进式 rehash 过程。
第 3 章：链表
第 5 章：跳跃表
![digraph {
label = "\n 图 4-1 一个空的哈希表";
rankdir = LR;
//
node [shape = record];
dictht [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 0"];
table [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
//
node [shape = plaintext, label = "NULL"];
null0;
null1;
null2;
null3;
//
dictht:table -> table:head;
table:0 -> null0;
table:1 -> null1;
table:2 -> null2;
table:3 -> null3;
}](_images/graphviz-ae0df49eac72231c8a5ddc4f3287ae70a76d9d09.png)
![digraph {
label = "\n 图 4-2 连接在一起的键 k1 和键 k0";
rankdir = LR;
//
node [shape = record];
dictht [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 2"];
table [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
dictEntry0 [label = " <head> dictEntry | { k0 | v0 }"];
dictEntry1 [label = " <head> dictEntry | { k1 | v1 }"];
//
node [shape = plaintext, label = "NULL"];
null0;
null1;
null2;
null3;
//
dictht:table -> table:head;
table:0 -> null0;
table:1 -> null1;
table:2 -> dictEntry1;
dictEntry1 -> dictEntry0 -> null2 [label = "next"];
table:3 -> null3;
}](_images/graphviz-0edd4770efcdbded629eae54f22d059c235fb567.png)
![digraph {
label = "\n 图 4-3 普通状态下的字典";
rankdir = LR;
//
node [shape = record];
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 2"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 0 | <sizemask> sizemask \n 0 | <used> used \n 0"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = "NULL", shape = plaintext];
dictEntry0 [label = " <head> dictEntry | { k0 | v0 }"];
dictEntry1 [label = " <head> dictEntry | { k1 | v1 }"];
//
node [shape = plaintext, label = "NULL"];
null0;
null1;
null2;
null3;
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1;
table0:0 -> null0;
table0:1 -> dictEntry0:head -> null1;
table0:2 -> null2;
table0:3 -> dictEntry1:head -> null3;
}](_images/graphviz-14ae3cb52b4e18b8396b40a115e7f8cc983fd5fa.png)
![digraph {
label = "\n 图 4-5 添加键值对 k0 和 v0 之后的字典";
rankdir = LR;
//
node [shape = record];
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 1"];
dictht1 [label = "...", shape = plaintext];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
//table1 [label = "NULL", shape = plaintext];
dictEntry [label = " <head> dictEntry | { k0 | v0 } "];
//
node [shape = plaintext, label = "NULL"];
null0;
null1;
null2;
null3;
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
//dictht1:table -> table1;
table0:0 -> dictEntry:head -> null0;
table0:1 -> null1;
table0:2 -> null2;
table0:3 -> null3;
}](_images/graphviz-d9dd0ae59c128e2e8fb60d38d09acd1cb98ebc06.png)
![digraph {
label = "\n 图 4-8 执行 rehash 之前的字典";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 4"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 0 | <sizemask> sizemask \n 0 | <used> used \n 0"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = "NULL", shape = plaintext];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
null0;
null1;
null2;
null3;
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1;
table0:0 -> kv2:head -> null0;
table0:1 -> kv0:head -> null1;
table0:2 -> kv3:head -> null2;
table0:3 -> kv1:head -> null3;
}](_images/graphviz-9564b109c5809606b86e19ef6033258df20dfead.png)
![digraph {
label = "\n 图 4-9 为字典的 ht[1] 哈希表分配空间";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 4"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 0"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | <0> 0 | <1> 1 | <2> 2 | ... | <7> 7 "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> kv2:head -> null0;
table0:1 -> kv0:head -> null1;
table0:2 -> kv3:head -> null2;
table0:3 -> kv1:head -> null3;
table1:0 -> null10;
table1:1 -> null11;
table1:2 -> null12;
table1:7 -> null17;
}](_images/graphviz-cba8bf03b2ad8ac0217b5d5caa099c116ea05cba.png)
![digraph {
label = "\n 图 4-10 ht[0] 的所有键值对都已经被迁移到 ht[1]";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 0"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 4"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | ... | <1> 1 | ... | <4> 4 | <5> 5 | ... | <7> 7 "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> null0;
table0:1 -> null1;
table0:2 -> null2;
table0:3 -> null3;
table1:1 -> kv3:head -> null11;
table1:4 -> kv2:head -> null14;
table1:5 -> kv0:head -> null15;
table1:7 -> kv1:head -> null17;
}](_images/graphviz-5ce299510d3ac3acd190412be77614e7d3f12334.png)
![digraph {
label = "\n 图 4-11 完成 rehash 之后的字典";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 4"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 0 | <sizemask> sizemask \n 0 | <used> used \n 0"];
table0 [label = " <head> dictEntry*[8] | ... | <1> 1 | ... | <4> 4 | <5> 5 | ... | <7> 7 "];
table1 [label = "NULL", shape = plaintext];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1;
table0:1 -> kv3:head -> null11;
table0:4 -> kv2:head -> null14;
table0:5 -> kv0:head -> null15;
table0:7 -> kv1:head -> null17;
}](_images/graphviz-2130a61bace2dea3deba4fcb5046c7a33ec96c54.png)
![digraph {
label = "\n 图 4-12 准备开始 rehash";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 4"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 0"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | <0> 0 | <1> 1 | <2> 2 | ... | <7> 7 "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> kv2:head -> null0;
table0:1 -> kv0:head -> null1;
table0:2 -> kv3:head -> null2;
table0:3 -> kv1:head -> null3;
table1:0 -> null10;
table1:1 -> null11;
table1:2 -> null12;
table1:7 -> null17;
}](_images/graphviz-39bf8a3d82841c1d470d88d66589fc5c0fff5691.png)
![digraph {
label = "\n 图 4-13 rehash 索引 0 上的键值对";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n 0 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 3"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 1"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | ... | <4> 4 | ... "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> null0;
table0:1 -> kv0:head -> null1;
table0:2 -> kv3:head -> null2;
table0:3 -> kv1:head -> null3;
table1:4 -> kv2:head -> null14
}](_images/graphviz-e54115292a81336617d5776e0abd28eb3689a17b.png)
![digraph {
label = "\n 图 4-14 rehash 索引 1 上的键值对";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n 1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 2"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 2"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | ... | <4> 4 | <5> 5 | ... "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> null0;
table0:1 -> null1;
table0:2 -> kv3:head -> null2;
table0:3 -> kv1:head -> null3;
table1:4 -> kv2:head -> null14
table1:5 -> kv0:head -> null15;
}](_images/graphviz-09466a45aa36ee3abaea68f2e265ee5689ca2d12.png)
![digraph {
label = "\n 图 4-15 rehash 索引 2 上的键值对";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n 2 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 1"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 3"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | ... | <1> 1 | ... | <4> 4 | <5> 5 | ... "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> null0;
table0:1 -> null1;
table0:2 -> null2;
table0:3 -> kv1:head -> null3;
table1:1 -> kv3:head -> null11;
table1:4 -> kv2:head -> null14
table1:5 -> kv0:head -> null15;
}](_images/graphviz-a6695b4a44a99d49d2d5bba9cf2f00e5db86833e.png)
![digraph {
label = "\n 图 4-16 rehash 索引 3 上的键值对";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n 3 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 4 | <sizemask> sizemask \n 3 | <used> used \n 0"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 4"];
table0 [label = " <head> dictEntry*[4] | <0> 0 | <1> 1 | <2> 2 | <3> 3 "];
table1 [label = " <head> dictEntry*[8] | ... | <1> 1 | ... | <4> 4 | <5> 5 | ... | <7> 7 "];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1:head;
table0:0 -> null0;
table0:1 -> null1;
table0:2 -> null2;
table0:3 -> null3;
table1:1 -> kv3:head -> null11;
table1:4 -> kv2:head -> null14
table1:5 -> kv0:head -> null15;
table1:7 -> kv1:head -> null17;
}](_images/graphviz-132aa58f22ede311d57e394d1fb39da456c03678.png)
![digraph {
label = "\n 图 4-17 rehash 执行完毕";
rankdir = LR;
node [shape = record];
// 字典
dict [label = " <head> dict | type | privdata | <ht> ht | rehashidx \n -1 "];
// 哈希表
dictht0 [label = " <head> dictht | <table> table | <size> size \n 8 | <sizemask> sizemask \n 7 | <used> used \n 4"];
dictht1 [label = " <head> dictht | <table> table | <size> size \n 0 | <sizemask> sizemask \n 0 | <used> used \n 0"];
table0 [label = " <head> dictEntry*[8] | ... | <1> 1 | ... | <4> 4 | <5> 5 | ... | <7> 7 "];
table1 [label = "NULL", shape = plaintext];
// 哈希表节点
kv0 [label = " <head> dictEntry | { k0 | v0 } "];
kv1 [label = " <head> dictEntry | { k1 | v1 } "];
kv2 [label = " <head> dictEntry | { k2 | v2 } "];
kv3 [label = " <head> dictEntry | { k3 | v3 } "];
//
node [shape = plaintext, label = "NULL"];
//
dict:ht -> dictht0:head [label = "ht[0]"];
dict:ht -> dictht1:head [label = "ht[1]"];
dictht0:table -> table0:head;
dictht1:table -> table1;
table0:1 -> kv3:head -> null11;
table0:4 -> kv2:head -> null14;
table0:5 -> kv0:head -> null15;
table0:7 -> kv1:head -> null17;
}](_images/graphviz-63a1d9dfe98aa1925621514df30eae201d5ed723.png)