出自：http://www.jb51.cc/article/p-fnveggxy-op.html
多姿多彩的哈希表
自从通过数据结构课程学习哈希表以来，对于哈希表的实现一直都是固定的课本上的理论，使用链表作为冲突消解策略，分配一个数组作为哈希表的基本结构，基本上实现哈希表的方法就是这样，但是一般因为找不到好的哈希函数而放弃使用哈希表。由于使用的少，对于哈希表的具体实现方式就没有花太多心思，就是使用哈希表基本上就是直接把库里的哈希表结构拿来使用，
最近学习了 berkely DB 和 sqlite3 的源代码，其它收获不说，单单哈希表的使用与实现就让我长了见识，至于 berkely DB 中对哈希表的使用和实现，适合于对磁盘文件信息的组织，在《 Berkeley DB 1.8.6 源代码学习》中已经总结，本文主要将 sqlite3 中已经看到的对哈希表的几种使用和组织方式总结一下，以备不时只需， sqlite3 中对哈希表的使用和组织方式适用于在内存中使用；
1 、经典实现
在对 sqlite3_pcache 接口的缺省实现 PCache1 结构中使用了哈希表来组织和管理缓冲区中的页面，主要在 pcache1.c 中出现，基本的实现方式就是同理论方式一样，使用一个数组组织哈希表，冲突消解策略使用的是链表；
哈希表 apHash 是一个 PgHdr1 类型指针的数组，使用页面编号作为键值，哈希函数是键值除以数组的长度；
如果需要增加哈希表的尺寸（数组的长度），那么需要将表中的元素重新插入，不同于在 berkely DB 中只用重新插入对应的桶中的部分项，但是由于是在内存中使用，不用考虑磁盘的读写，这样处理简单可行；
2 、伸缩型哈希表
这里所谓的伸缩性的哈希表其实就是在数据量较小的时候使用双向链表存储，当数据量大的时候该用哈希表存储；这在一些类库中具有对应的数据结构供直接使用， sqlite3 中使用了其中的一种实现；
这种哈希表的使用在 sqlite3 中较为广泛，作为一个单独的模块来实现， hash.h 和 hash.c 文件用于实现这一哈希表；
哈希表结构为 Hash ：
使用四个成员变量存储：
htsize ：无符号短整型，当使用哈希表存储时，哈希表中桶的数量；
count ：无符号短整型，哈希表中入口项的个数（记录的个数）；
first ： HashElem 类型，哈希元素指针，指向入口项双向链表的表头；
ht ： _ht 结构指针，哈希表存储结构，当使用哈希表存储时，将表现为一个桶的数组；含有两个成员变量，其中 count 成员变量记录本桶中记录的数量， chain 成员变量指向桶内记录链表的表头，哈希表使用的冲突消解策略是链表；
关于 Hash 的使用，当存储的记录数量较少时，将 htsize 赋值为 0 ， ht 赋值为空，所有记录实际保存在以 first 为表头的双向链表中， count 是记录的数量；
当记录数量达到一定的程度后，使用 ht 配合哈希访问， htsize 记录了 ht 桶的数量，即 ht 数组的长度。需要注意的是此时 first 链表仍然保存了哈希表中所有的记录， ht 数组仅仅相当于索引的作用，即 ht 中每个桶都有自己的链表，这些链表链接在一起组成了 first 链表， ht 中 chain 成员指向本桶链表的表头在 first 中的位置， count 成员则记录了链表的长度，即确定表尾的位置；
从而，上述方式可以有效的达到哈希表伸缩转换的目的；
哈希元素结构 HashElem ：
具有 5 个成员变量；
next ：下一条记录；
prev ：上一条记录；
data ：数据；
pKey ：键；
nKey ：键的长度；
使用的哈希函数为 strHash ；
sqlite3HashInit ：哈希表的初始化函数，将各个成员变量初始化为 0 ；
sqlite3HashClear ：将哈希表中所有的入口项删除，就是将 ht 的内存释放，将 first 链表中所有的元素释放；将各个成员变量置 0 ；
sqlite3HashInsert 函数：向哈希表中插入元素；
函数参数：
pH ： Hash 结构指针，待操作哈希表；
pKey ：字符指针，键值；
nKey ：整型，键值长度；
data ： void 指针，数据值；
返回值：如果哈希表中不存在相同键值的入口项，则插入，然后返回 NULL ；如果存在相同的入口项，则替换，同时返回原数据值；
伪代码：
如果 pH 的 htsize 成员变量不为 0 ，即使用哈希表存放数据项，那么使用 strHash 函数计算桶号 h ；如果 pH 的 htsize 成员变量为 0 ，那么 h=0 ；
根据 h 和键值在哈希表中找键值为 pKey 的入口项，如果存在，那么使用 data 替换原数据值，返回原数据值；
如果不存在，根据 pKey 和 data 组建一个入口项元素 pNew ；准备插入哈希表；
首先哈希表是否需要扩容，如果需要，先将哈希表扩容，同时重新计算 h 的值；
将 pNew 插入哈希表需要查看哈希表当前的状态，是链表存放还是哈希表存放；
如果 pH 的 htsize 等于 0 ，则为链表存放，将 pNew 插入 first 链表表头即可；
如果 pH 的 htsize 不等于 0 ，则使用哈希表存放，将链表插入到对应桶链表的表头即可；需要注意的是桶链表和 first 链表的关系；首先找到桶链表的表头，如果桶中当前没有元素，那么将对应桶的链表头指向 pNew ，然后将 pNew 插入到 first 链表的表头,将对应桶含有的元素数量增加；如果对应桶中已经有元素，即桶的链表头不为空，那么将 pNew 插入到桶的链表头即可，根据刚刚插入第一个元素时看到的桶链表和 first 链表的关系可知，此时 pNew 也在 first 链表中；
sqlite3HashFind 函数：在哈希表中查找指定的入口项；
函数参数：
pH ： Hash 结构指针，待操作哈希表；
pKey ：字符指针，键值；
nKey ：整型，键值长度；
返回值：数据值或 NULL ；
伪代码：
根据 pKey 计算哈希值，得到桶号 h ；如果 pH->ht 为空，即使用链表实现，那么 h=0 ；
如果 pH->ht 为空，那么遍历 first 链表，找到键值与 pKey 相同的入口项；
如果如果 pH->ht 不为空，找到对应的桶链表表头，遍历桶链表，找到键值与 pKey 相同的入口项；注意：桶链表是 first 链表的一部分，即不是所有的桶链表的表尾部都是以空结束，所以使用桶的 count 来控制桶链表的遍历；
至于哈希表的扩容，需要所有的元素重新插入；
3 、关键字哈希表
所谓关键字哈希表是 sqlite3 中在对 sql 语句作语义分析时使用，其基本功能就是对一个给定的关键词，找出其对应的 ID ；
由于以前在编译原理的课程设计中做过语义分析器，所以对关键词的处理还算有些心得，当时也基本上按照书本上的描述去实现，在 sqlite3 中，发现对 sql 语句语义分析中关键词处理这一部分比较有意思，虽然不一定是效率最高的，但是个人觉得其对哈希表的使用颇有见地；
对于一个给定的关键词 key ，找到对应的 ID ，一般来讲使用哈希表应该不出上面两种实现方式，找个好的哈希函数，然后存放，如果出现冲突，基本上用链表消解；但是在语义分析中有其特殊之处，即关键词是有限的，对于那些非关键词，一般只有一个统一的 ID ，即用户定义的变量名；
sqlite3 中对关键字哈希表的实现在 keywordhash.h 中，这个文件是由程序自动生成，但是其处理哈希表的手法却值得我学习；
关键字哈希表的基本思想是：将所有的关键字组成一个关键字词典，则每一个关键字在词典中的索引就是一个起始偏移和一个关键字的长度，如：对于 REINDEX 、 INDEXED 、 INDEX 、 DESC 等四个关键字，可以组成的字典为“ REINDEXEDESC ”，四个关键字的索引分别为
（ 0 ， 7 ）
（ 2 ， 7 ）
（ 2 ， 5 ）
（ 8 ， 4 ）
前一个量为偏移，后一个量为关键字长度；如果在上面的向量中加入表示 ID 的量，将这一向量与关键字本身关联，就得到关键字哈希表的哈希方式；即
通过哈希函数计算关键字的哈希值，通过哈希值得到对应的桶号，通过桶号和关键字的偏移及长度找到关键字的 ID ，从而完成根据关键字找到 ID 的过程；
关键字哈希表的效率不一定是最高的，但是肯定是内存空间和效率的性价比最好的，对于 sqlite3 这类嵌入式数据库来说，内存还是比较宝贵的，而且也提供了一种哈希表的实现方式；
根据上面的描述，关键字哈希表的实现有 6 个数组共同完成：
zText ： 540 个字符的字符数组，关键字全文字典；收录所有的关键字在其中，按照哈希表的规则可以检索对应的关键字；
aHash ： 127 个字节的字节数组，哈希表的桶数组；
aNext ： 121 个字节的字节数组，冲突消解策略使用的备用数组；
aLen ： 121 个字节的字节数组，关键字的长度；
aOffset ： 121 个字节的无符号短整型数组，关键字在全文字典中的偏移；
aCode ： 121 个字节的字节数组，关键字对应的 ID ；
上述数组之间的关联就是， aNext 是 aHash 的冲突消解策略， aHash 和 aNext 中存放的是关键字的相关信息的索引，所谓关键字的相关信息就是关键字在全文字典中的偏移、长度及关键字 ID 分别在 aOffset 数组、 aLen 数组、 aCode 数组中的索引；
其基本流程就是：
输入： z （待决关键字）， n （待决关键字长度）
首先通过哈希函数计算桶号，即在 aHash 中的索引 h ；
取 aHash[h] 的值转化成索引 i （ C 语言数组从 0 计数，所以需要减去 1 ）；
i 就是关键字的相关信息在 aLen 、 aOffset 、 aCode 中的索引；如果 aLen[i] 存放的关键字长度与 n 相等且在全文字典中从 aOffset[i] 开始的 aLen[i] 个字符组成的字符串与输入关键字 z 相同，那么表示 aCode[i] 中存放的就是 z 的 ID ；
哈希表的哈希函数必然会有冲突，即多个关键字的桶号均为 h 时，上述判断必然会有失败的情况，此时 aNext 的作用就是冲突消解策略，对于关键字 z ，如果在 aHash 中的桶号 h 已经被占据，那么将其索引 i 存放到 aNext 中，其位置就是前一个冲突项的索引（键值）；即第一个发现冲突的关键字存放在 aNext[aHash[h]-1] 中，其中 aHash[h]-1 即前一个冲突项的索引，第一个发现冲突项的索引就是 i1=aNext[aHash[h]-1]-1 （ C 语言数组从 0 计数，所以需要减去 1 ），第二个冲突项的索引存放就是 aNext[i1] ，依次类推；由于关键字的索引不可能重叠（即 aCode 中不会在同一处存放两个不同关键字的 ID ），所以 aNext 中不会出现冲突的情况（个人猜测，待求证）；
哈希表的概念虽然容易懂，但是发现用好哈希表却非一件容易的事，只能多学习了。
原文链接：https://www.f2er.com/sqlite/201256.html