I wrote a custom hash table for a project I'm working on. The core functionality was pretty simple rolling table:

  1. In each table there is a memory section for HashItemReference(integer SecondHash, integer ItemN) which is the actual table part and a list of HashItem(integer Value, string Key)
  2. Each HashItemReference would contain a second hash of the original key and a number to refer to the hash item
  3. When looking for an item, it would land on the first hash position as usual and then go sequentially, checking if the second hash checks out then check the actual hash item. (The table lives on a spinning disk, this was necessary to minimize jumping around and keeping it sequential)
  4. If the actual key(variable length string) checks out then return the number associated with this key.

This approach works well enough all though it does have one hypothetical problem - If the average size of the keys was unknown(which in this case it isnt), it would be difficult to make the memory reserve for hash table and the list of items fill up at the same time, leading to either wasted space(which in case of hash tables directly translates to wasted performance) or more resizing(even worse).

I don't have the time to test things right now but nearing the end, I got another idea, I wonder if anybody has built something like that and can comment on how it compares to the solution above.

The idea:

  1. Instead of storing the hash items in a separate list, cut them to chunks and store sequentially in the actual table.
  2. This would need a header to indicate continuation or new item so something like 1B (New or Old) + 7B of data (sequentially first name and then value).
  3. Since there is no way to stitch together fragmented chunks they would have to be strictly sequential so when inserting into the table, an empty sequence long enough would have to be used.
  4. The header byte could also contain more information, for example, how many chunks to skip. It wouldn't know how far off the desired block will be but it knows its own length and I could skip at least that (or a maximum of 128) before checking another chunk.

This approach would completely eliminate the issue with the previous approach but I'm a bit skeptical about sticking unfragmentable chains of blocks into a table ruled by a function whose whole purpose is to fragment as much as possible.

So.. thoughts?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.