CHashPage
CHashPage is a fixed size (24KB typically, but it depends on LBUF_SIZE) consisting of three parts:
- A header,
- Variable-sized hash directory,
- Variable-sized heap.
Open, double hashing occurs from the directory into the page's heap. To improve search speed, a minimal number of empty directory entries (1/7th of the available entries) are guaranteed. If a CHashPage falls below this treshold, it re-hashes and defragments itself leaving additional empty space in the directory. Almost all searches are accomplished in exactly one probe into the CHashPage's directory.
One problem typical of open hashing schemes that entries clump and form runs. To avoid this problem, there are also a table of 16 deltas in the header which are relatively prime to the directory size. In this way, there are 16 unique trips one can take around the directory. The lower four bits of a hash key are used to determine which of these 16 are used.
The benefit of this mini-DBM approach is that you get locality (everything is in 24KB) and avoid deferencing pointers. You get a pre-image of what to write to the disk (in case of SIGSEGV). Each page stands alone. To fetch a page requires one disk hit.
CHashPage is used by CHashTable and CHashFile.