@
Comdex 哈哈，主要是我太懒了，感觉说话（表达）比写代码还要累。。。
实现细节还蛮多的，先说说哈希表的部分，普通的哈希表有一个致命的缺陷：当 numKeys/numBuckets 达到某个阀值（ load factor ）的时候，需要 rehash，这个操作会瞬间耗费大量的 cpu （而且哈希表构建在磁盘上的话，还要算上 io ）。有没有办法把这个 rehash 的过程切分成一小步一小步，分摊到每次插入的操作上？这个就是<线性哈希>算法解决的问题。虽然 rehash 的过程被分摊了，但是 bucket 数组的空间还是需要连续的（不然没办法根据 hashcode 定位了），一般会采用“翻倍”的策略，让最大可用 bucket 的数量保持在 2^N。如果考虑存储海量的数据，bucket 数组空间翻倍（分配新的空间，拷贝旧数据到新空间，释放旧的空间）也是一个耗 cpu 和 io 的点。为了解决这个问题我把 bucket 数组切成固定长度的段（ segment，64kb ），段与段之间不需要空间上的连续，然后额外维护一张段表（需要空间上连续）指向这些散落的段。这样就把 bucket 数组空间翻倍就弱化为段表空间翻倍，大大降低了影响。