两种可变长度的HashTable插入示例

HashTable 是什么？

1. HashTable 用来存储多个键值对；可以插入键值对，可以通过键来查询其对应的值；
2. HashTable 有一个hash函数，用来计算键的hash值，可以通过hash值在 是时间复杂度下找到一个位置（bucket）与该hash值对应，bucket存储指向一个block的指针，block里面有很多键值对；
3. 因此对于键值对的插入请求，可以通过hash函数计算键的hash值，再根据hash值获取到磁盘上的一个位置（block的位置），就可以将键值对存储到该block上；对于查询请求，可以通过hash函数计算被查询键的hash值，根据通过hash值找到的block获取到该键对应值；
4. 对于键的删除请求，同理计算键的hash值对应的位置，直接删除掉该键值对（或者打上一个删除标记）；

存在的问题以及解决方案

存在的问题

1. 在插入键值对的情况下，发现键的hash值对应的位置上已经存储了键值对，此时该如何处理？
2. HashTable显然存在大小，如果插入的键值对过多，存不下怎么办？

问题1的解决方案

1. 因为一个block通常可以存储很多键值对，如果hash值对应的bucket指向的block是空的，那么直接插入进该block就好；
2. 如果该block已经满了，可以通过overflow block的方式，把新插入的键值对放到一个新的overflow block上，再把这个block链接到其键hash值对应的block上；

问题2的解决方案

1. double
   目标是保证HashTable中不出现overflow blocks
   方案：

   • 计算hash值时，仅考虑该值的前 位（ 初始值可以预设，随着HashTable插入数据的增加而增加）；
   • 因此，HashTable的大小为 ；
   • 插入时，根据hash值的前 位，找对应的bucket，如果该bucket指向的block已经满了，将所有的bucket复制一遍，与之对应的 与原来相比，也增加了 ；
   • 假设 bucket 是 bucket 的复制，那么 和 指向的是同一个block；假设新插入的键值对对应的上述block，则需要把该block分裂成两个，使得 和 指向不同的 block；

2. increase one