How to store a hash table in a file?

Question

How can I store a hash table with separate chaining in a file on disk?

Generating the data stored in the hash table at runtime is expensive, it would be faster to just load the HT from disk...if only I can figure out how to do it.

Edit: The lookups are done with the HT loaded in memory. I need to find a way to store the hashtable (in memory) to a file in some binary format. So that next time when the program runs it can just load the HT off disk into RAM.

I am using C++.

Answer 1

What language are you using? The common method is to do some sort binary serialization.

Ok, I see you have edited to add the language. For C++ there a few options. I believe the Boost serialization mechanism is pretty good. In addition, the page for Boost's serialization library also describes alternatives. Here is the link:

http://www.boost.org/doc/libs/1_37_0/libs/serialization/doc/index.html

Answer 2

Assuming C/C++: Use array indexes and fixed size structs instead of pointers and variable length allocations. You should be able to directly write() the data structures to file for later read()ing.

For anything higher-level: A lot of higher language APIs have serialization facilities. Java and Qt/C++ both have methods that sprint immediately to mind, so I know others do as well.

Answer 3

Perhaps DBM could be of use to you.

Answer 4

You could just write the entire data structure directly to disk by using serialization (e.g. in Java). However, you might be forced to read the entire object back into memory in order to access its elements. If this is not practical, then you could consider using a random access file to store the elements of the hash table. Instead of using a pointer to represent the next element in the chain, you would just use the byte position in the file.

Answer 5

If your hash table implementation is any good, then just store the hash and each object's data - putting an object into the table shouldn't be expensive given the hash, and not serialising the table or chain directly lets you vary the exact implementation between save and load.

Answer 6

Ditch the pointers for indices.

This is a bit similar to constructing an on-disk DAWG, which I did a while back. What made that so very sweet was that it could be loaded directly with mmap instead reading the file. If the hash-space is manageable, say 2¹⁶ or 2²⁴ entries, then I think I would do something like this:

• Keep a list of free indices. (if the table is empty, each chain-index would point at the next index.)
• When chaining is needed use the free space in the table.
• If you need to put something in an index that's occupied by a squatter (overflow from elsewhere) :
  • record the index (let's call it N)
  • swap the new element and the squatter
  • put the squatter in a new free index, (F).
  • follow the chain on the squatter's hash index, to replace N with F.
• If you completely run out of free indices, you probably need a bigger table, but you can cope a little longer by using mremap to create extra room after the table.

This should allow you to mmap and use the table directly, without modification. (scary fast if in the OS cache!) but you have to work with indices instead of pointers. It's pretty spooky to have megabytes available in syscall-round-trip-time, and still have it take up less than that in physical memory, because of paging.

Answer 7

Try using STLPLUS, it have API for persistence.