动态哈希表
哈希表就是通过对键值使用哈希函数计算得到入口点，从而可以插入或获取需要的值。对于计算得到相同入口点的情况，可以使用冲突消解策略来解决，一般使用附加链表的方式；
哈希表在初始化时固定了入口点的个数，如果随着哈希表的使用，不断有数据进入，哈希表膨胀到一定的程度，需要扩展哈希表，该如何设计一个动态的、可扩展的哈希表呢？
一般来讲需要解决两个问题：
1
、扩展后得到的新入口项如何通过哈希函数访问到？
2
、哈希函数新的入口项资源分配问题？
关于哈希函数的问题：
berkerlyDB
的解决方案是通过编码；
假设哈希函数返回的值时一个
32
位数
H
。如果哈希表只有
2
个入口项，则只需要使用
H
的第
0
位就可以区分，即只需
1
位就可以达到记录入口项编号。如果有
3
个入口项，则使用
H
的第
0
和第
1
为就可以区分，即使用
2
位，但是
2
位数据有四种组合
—00
、
01
、
10
、
11
。这就需要使用屏蔽技术，
3
个入口项，则最大入口项的编号为
2
（
0x10
，从
0
计数），当
H
的低
2
位的值大于最大入口项编号，再去除低
2
位的最高位，即只使用第
0
位来区分。这样达到区分的目的。
从上面可以看出，可以通过调节
H
的有效位数来到达哈希函数扩展的问题。
假设当前有
N
个入口项，
N
大于等于
2
的
B
次方，小于
2
的
B+1
次方。则使用
H
的低
B+1
位和低
B
位可以有效的达到区分的目的。首先，使用低
B+1
位来判断入口项，如果不能区分（对于
B
小于
2
的
B+1
次方的情形，如果
H
的低
B+1
位大于
B
小于
2
的
B+1
次方时），则使用低
B
位区分。当入口项的个数扩展至
N+1
时，如果
N+1
仍然处于
2
的
B
次方与
B+1
次方之间，则上述区分方法仍然有效，当
N+1
超过
2
的
B+1
次方式，将
B
递增
1
位就解决问题了。通过这样编码的手段就可以在不用更改哈希函数的情况下有效的达到调节哈希表扩展的问题。
其实从上述方法可以看出，如果输入数据在哈希函数上均匀分布，则当入口项的个数不是
2
的幂的话，有一部分数据通过高位掩码（即获取
H
低
B+1
位的方式）不能找到入口项，在通过低位掩码找到，这之间就是将这类数据从哈希表入口项的搞半段转移到了第半段，这样入口项低半段的这部分将比其他部分具有更高的概率存储数据，这些入口项将比其他入口项具有更多的记录，当哈希表扩展时，就是在高半段增加一个入口项，将那些本来应该存储到这一入口项的记录从对应的低半段转移过来，从而平衡负载。
例如：当哈希表只有
3
个入口项时，
H
低
2
位为
01
，
11
的情况都存储在第
1
入口项，
00
存储在第
0
入口项，
10
存储在第
2
入口项，则第
1
入口项有较重的负载，哈希表扩展
1
个入口项后，有了第
3
（
0x11
）入口项，这样讲以前
H
低
2
位为
11
的记录从第
1
入口项转移到第
3
入口项，这样四个入口项在概率上具有平等的机会存储入口项。即具有相同低位的入口项在哈希表压缩时可以归并到一起，扩展时，可以安全的分裂开，从而有效的解决动态哈希表的哈希函数问题。
关于哈希函数新的入口项资源分配的问题，涉及到资源的充分利用和解决资源分配冲突。
哈希表中一般有四种类型的数据页：元数据页，入口项页，入口项链表页，大数据存储页。
元数据页：存放哈希表自身信息的页，位置和大小固定，存放在文件的开始部分，即第
0
页，占据页面的数量依赖于页面的大小。元数据页之后的页面均用于存放其它三种类型的页面；
入口项页：即通过哈希函数计算键值，得到入口项，用于存放实际的数据，使用链表来解决冲突消解，则入口项页其实就是入口项链表的首页，这类页面只能通过哈希函数计算键值的访问；
入口项链表页：即使用链表作为冲突消解，存放数据的非首页页面；这类页面的访问基本上是通过链表遍历；
大数据存储页：对于具有较大的键值和数据值的记录，需要额外的页面单独存放，入口项中保存存放页面的编号；对于尺寸大的记录，可能需要使用页面链表的存放。这类页面的访问就是通过上两类页面中保存的页面编号来访问；
当哈希表扩展时，新入口项页的分配就需要解决与入口项页和大数据存储页的冲突问题。
如果直接将哈希函数的结算的结果作为页面的编号，入口项页和大数据存储页的分配将十分麻烦。由于入口项页与大数据存储页都是额外的页面，下文统称为溢出页。
假设初始入口项的个数是
N
，则扩展后的页面编号都是
N+x
，那么在未扩展之前，溢出页面如何分配呢？由于文件是按照页面连续存储的，如果直接在
N
之后分配，则必然在扩展时与扩展的新入口项冲突。如果规定在
N
之后
M
页面处开始分配，则不过是延缓这一冲突的过程，而且
N
到
N+M
的页面自初始化之后就一直占用资源作为预留空间，如其这样不如一开始就直接将
N+M
初始化。
由上判断直接将哈希函数计算得到的值作为入口项页面编号是欠妥当的。可以使用另一种策略，溢出页面的分配直接在
N
之后，当哈希表需要扩展时，记录此时已经分配出去作为溢出页面的最大编号
NO
，在
NO
之后预留
S1
个页面作为入口项扩展只用，后续溢出页面的分配将从
NO+S1
开始。哈希表每次扩展添加
X
个入口项，
X
处于
0
到
S1
之间，且可以整除
S
，多次扩展之后，预留的
S
空间消耗完后，
在次为扩展分配
S2
个页面，
S2
同样不必被
X
整除。
S2
的处就是当前溢出页面编号的最大值，假设在此期间分配了
O2
个溢出页面，则溢出页最大编号就是
NO+S1+O2
。如此往复，就不会出现冲突，也不会出现过多的资源闲置，直至硬盘资源耗尽（鉴于特定语言数据类型的数据访问限制，页面编号有极限值，如使用短整形做页面编号，则最多只能有
2
的
16
方
-1
页），从而充分利用了资源。
那么这种方案如何寻址呢？将每次预留空间的分配编号，使用数组保存每次预留空间的起始页面号，初始化哈希表可以看做第
0
次预留空间。这样，通过哈希函数得到入口项号
E
时，如果
E
处于
N+S1+…+Si
和
N+S1+…+Si+S(i+1)
之间时，表示
E
在第
i
次预留的页面处，页面编号等于第
i
次预留空间的起始页面号加上
E-
（
N+S1+…+Si
）；得到了入口项页，就可以根据入口项页访问溢出页了。
berkerly DB
哈希表
数据结构
枚举
ACTION
：定义了
6
中操作：
HASH_GET:
表示从哈西表中取值的操作；
HASH_PUT:
表示更新哈西表中的值的操作；
HASH_PUTNEW:
表示向哈希表中插入值的操作；
HASH_DELETE:
表示从哈希表中删除值的操作；
HASH_FIRST:
获取
0
号桶的第一条记录；
HASH_NEXT:
获取下一条记录；
游标
cursor
：用于定位哈希表中的记录，有
9
个成员变量：
queue
：游标队列，用于顺序遍历哈希表；
get
：搜寻哈希表中第一个大数据，用于顺序遍历哈希表；
delete
：未定义；
bucket
：游标所在的桶号；
pgno
：游标所在的页面编号；
ndx
：游标在桶内的记录序号；
pgndx
：游标在本页内的序号；
pagep
：游标指向的页面；
internal
：
哈希表元信息（哈希表头，
HASHHDR
）：用于记录哈希表的元数据，
16
个成员变量：
magic
：
32
位数，魔数；
version
：
32
位数，哈希表版本号；
lorder
：
32
位数，计算机字节顺序；
bsize
：
32
位数，页面尺寸；
bshift
：
32
位数，页面尺寸的
2
的幂，即
bsize
＝
1<<bshift
；
ovfl_point
：
32
位数，最大的分裂点，溢出页面分配的地方；
last_freed
：
32
位数，可以转换为编号最小的空闲页面，其实这一成员变量并不是指向编号最小的空闲页面，只是能够保证在此之前的页面都已经使用，搜索空闲页面在
last_freed
到
ovfl_point
之间，如果没有，在需要利用
over_point
分配新的溢出页面，同时调整
last_freed
的值；
max_bucket
：
32
位数，表内最大的桶号；
high_mask
：
32
位数，高位掩码；
low_mask
：
32
位数，低位掩码；
ffactor
：
32
位数，填充因子，记录每桶可以存储的记录数量，超过此值，则建议扩展哈西表，分裂桶；
nkeys
：
32
位数，哈希表中的记录数量；
hdrpages
：
32
位数，本结构占用的页面数量；
h_charkey
：
32
位数，使用本表的哈希函数计算
CHARKEY
得到的值，用于再次打开哈西表时验证使用的哈希函数是否正确；
spares
：
32
位数的数组，共
NCACHED
项，用于页面标号寻址，每项对应一个分裂点，用于记录本分裂点操作中分配溢出页的个数，这样，便于根据桶号找到对应的页面编号；
bitmaps
：
16
位数的数组，共
NCACHED
项，用于记录位图页的溢出页编号；
哈希表：哈西表结构常驻内存，用于记录哈西表的基本信息，
17
个成员变量：
curs_queue
：游标队列的队列；
hdr
：
HASHHDR
类型，保存哈希表元数据；
hash
：函数指针，指向哈希函数；
flags
：
32
位数，记录哈希表的访问方式：只读，只写，可读写；
fp
：
32
位树，数据库文件描述符；
fname
：字符指针，临时文件名；
bigdata_buf
：大记录数据部分缓冲区指针；
bigdata_len
：
bigdata_buf
缓冲区的长度；防止访问越界；
bigkey_buf
：大记录键值部分缓冲区的指针；
bigkey_len
：
bigkey_buf
缓冲区的长度；
split_buf
：无符号
16
位数指针，桶分裂时，用于保存旧桶中的信息；
seq_cursor
：游标指针，用于顺序访问哈西表时使用；
errno
：
32
位数，用于记录错误编号；
new_file
：
32
位数，用于标识
fd
是否是新建表；
save_file
：
32
位数，用于标识，退出时是否将更新写回文件；
mapp
：
32
位数指针数组，共
NCACHED
项，用于在程序运行时，保存位图页的地址，与
bitmapps
记录的位图页一一对应；
nmaps
：
32
位数，保存哈希表位图页的个数，即
mapp
有效项的个数；
mp
：
MPOOL
类型指针，哈希表缓冲池；
查找记录信息（
ITEM_INFO
）：用于查找记录是传入和传出信息；共
10
个成员变量；
pgno
：页面编号；
bucket
：桶号；
ndx
：记录在桶内序号，从
0
计数；
pgndx
：记录在页面内序号，从
0
计数；
status
：查找结果－－成功、失败、没有多余项等；
seek_size
：插入操作时，用于传入需要的空闲空间大小；
seek_found_page
：插入操作时，非
0
值表示找到可以插入指定记录的页，如果为
0
，则表示
pgno
的值有效；
key_off
：键的索引值；
data_off
：值的索引值；
caused_expand
：标记是否需要扩展哈西表；
哈希表概述：
数据库文件页面组织：数据库页分为元数据页和数据页；元数据页分为头部信息页和位图页；数据页分为桶页和溢出页；数据页一般分为两部分：页头部和数据部分；
其中头部信息页保存哈希表头部信息，即
HASHHDR
结构变量，整个哈西表只有一份，保存在文件的起始的若干页，从第
0
号页面开始，占据的页数视页面大小而定；头部信息页的结构是：页头部是一个
32
位数据保存本页存储的头部信息的长度，数据部分用于保存数据信息；其他类型页面紧跟在头部信息页之后；注意：头部信息页不与其它页面共享一个页面，即如果保存头部信息的最后一个页面没有完全使用，则剩余部分空闲；
位图页：位图页的位置视分配的页面编号而定，一个哈希表可以有多个位图页，其溢出编号依次保存在哈希表头的
bitmaps
数组中；当哈希表在运行时，位图页会从硬盘读入到内存，从此直至哈西表关闭，所有的位图页一直常驻内存；位图页的结构与其他类型不同，位图页以位为基础，
BITS_PER_MAP
位为一个基本组成单元－－
MAP
；一个位图页的
MAP
数就是页面中总的位数－－
2
的
bshift+BYTE_SHIFT
次幂，除以
BITS_PER_MAP
；位图页中的每一位将用于表示对应的溢出页面是否可用，
0
表示可用，
1
表示不可用；将某一位在位图页中的序号（从
1
开始）作为低
bshift+BYTE_SHIFT
位，将位图页的序号（即保存在
bitmapps
数组中的序号，从
0
开始）作为剩余的高位，组成一个
32
位的数，这一个数据是哈希表内唯一的，可以转换为页面编号，这就是位图页的作用；位图页的除此访问通过
bitmaps
数组中保存的溢出页编号，配合
spares
数组中对应项来访问，之后就一直常驻内存，通过
htab
结构的
mapp
来访问；
桶页：桶页就是保存桶中记录的页面链表的首页，桶页通过桶号配合
spares
数组作一定的映射来访问；
溢出页：溢出页是一个宽泛的类型，就是不能通过预先设置的方式访问的页面都是溢出页，除去头部信息页（指定从
0
页开始的若干页）和桶页（通过哈西函数计算），其它的页面都是溢出页，包括位图页、桶链表的非首页、大记录存储页；由于桶链表的非首页和大记录存储页都可以通过桶页来访问，而位图页却没有其它的访问途径，所以需要使用
bitmaps
来存储其溢出编号；溢出页使用溢出编号标识，溢出编号是一个
16
位的数，高
5
位为分裂点（
berkerly Db
注释中的称呼，
split
point
，即前文中的预留点）编号，低
11
位为基于本分裂点第一页的偏移；
数据库中的普通记录（非大数据记录）存放在桶链表页中（首页和非首页），这类页面的头部包括
6
个部分：
左兄弟页面编号：第
0
－
3
字节，
32
位数，保存左兄弟页面的页面编号，实际由于桶链表使用的是单链表，所以此项存放的是本页页面编号；
右兄弟页面编号：第
4
－
7
字节，
32
位数，保存右兄弟页面的页面编号，链表的最后一页本项为
NULL
；
本页存储的记录数：第
8
－
9
字节，
16
位数，保存本页存储的记录数量。
页面类型：第
10
字节，
8
位数，保存本页页面类型；
padding
：第
11
字节，
8
位数，填充字节，使字节对齐；
空闲空间首地址：第
12
－
13
字节，页面的数据部分从两端向中间填充，靠近头部的一端（低地址端）为索引端，索引有键值索引和数据值索引，分别保存键值和数据值存储的首地址（相对页面基地址），均使用
32
位数保存，所以一条记录的索引占用
8
字节（
64
位）；数据部分的另一端（高地址端）为数据端，存放数据部分（包括键值和数据值，其中键值在前－－高地址，数据值在后－－低地址）；由于一条记录索引部分的尺寸是固定的（
8
字节），而页面头部存储有本页记录数，所以当需要存储新的记录时，可以定位新记录索引的地址分配起始处，而记录的数据部分尺寸不是固定的，不能有效的通过计算来确定空闲空间高地址端的位置，页面头部这一项的功能就是记录空闲空间的高地址；
桶链表页的数据部分的格式如上所述，所以存储一条记录需要的空间是记录的尺寸加上索引的尺寸（
8
字节）；页面的空闲空间就是空闲空间首地址减去最后一条记录的索引结束部分的地址；
关于大数据记录；在桶链表页中，记录的索引部分，其键值索引保存大数据记录标志，数据值索引部分保存存储大数据记录的页面链表的首页页面编号；所以一条大数据记录在桶链表页中占用的空间为索引的尺寸（
8
字节）；
大数据存储页的格式同桶链表页相同，不同的是页面只有一条记录，即一个索引，键值索引存放本页中存放键值的长度，数据值索引存放本页中存放数据值的长度；在大数据记录存储链表中，先存放键值，再存放数据值，所以可能开始若干页只有键值，组后若干页只有数据值，中间某一页既有键值也有数据值，对于既有键值又有数据值的页，需要注意的时不同于桶链表页，这一页中键值存放在低地址部分，数据值存放在高地址部分；
关于普通记录存储的补充说明，当获取记录时，对键值和数据值的获取需要知道二者的长度，但是页面中并没有对二者长度作存储，需要根据记录的存储格式来计算二者的长度，数据值的长度容易计算，数据值和键值连接存储，数据值存储在低地址部分，键值存储在高地址部分，所以键值起始地址就是数据值的结束地址后一项，所以数据值的长度等于键值的索引减去数据值的索引；键值的长度计算比较麻烦，根据存储格式知道键值的结束地址就是另一条记录数据值的起始地址或页面的终端（对于页面内第一条记录而言），那么是哪一条记录呢？一般来讲就是前一条记录，但是大数据记录并不占用桶链表页数据端空间，所以应该是记录序号小于本记录的最后一条普通记录，其数据值索引就是本记录键值的结束地址；
页面编号分配：
根据前文中动态页面编号的分配方案，
berkerly Db
的页面编号分配方案类似，只是每次预留的页面数量的方案需要作一定的说明；
berkerly Db
中哈希表每次扩展只扩展一个桶号，所以才会出现需要高位掩码和地位掩码共同操作完成桶号确定的方案（如果每次扩展都使得最大桶号等于
2
的幂－
1
，则就不需要使用低位掩码了，此时就不会出现高位掩码不能定位的现象）；即
X
＝
1
；对于分裂（
spilt
）在程序中有两种解释，一种是哈希表扩展时，将旧桶中的数据按照新的掩码重新分配到新桶和旧桶的过程称之为分裂（
split
）；另外，为桶首页预留的页面消耗完，需要开始新的一轮预留，程序中也称为分裂（确切的说是将第
S
次预留成为分裂点
S
），有分裂点的概念，设分裂点为
Sx
，即第
Sx
为桶页预留页面，则第
Sx
次为哈希表桶页预留的页面数量程序设定为
2
的
Sx
次幂，譬如：
Sx
等于
3
，则为桶首页预留
8
个页面；需要注意的是，在新表创建时可以指定新表的桶的数量
N
（实际上是通过可以存储的记录数转换得来的），哈希表会将这一数量扩展到大于
N
的最小的
2
的幂，譬如，
N