hash database (hdb32) multitool
hdb(5)                                hdb                               hdb(5)

       hdb - hash database (hdb32) file format

       An  hdb file is implemented as a partitioned hash table.  It provides a
       set of mappings for record ``keys'' to record  ``values'',  where  keys
       and records are any arbitrary strings of bytes.

       An  hdb  file  is implemented as a ``write-once, read-many'' datastore.
       It is generally used by applications  requiring  fast  read  access  to
       ``constant''  data,  and  is modeled after the cdb(5) constant database

       A hdb file is comprised of six sections:

           I M P C R H


       I: identifier
              A file type identifier of 16 bytes.  The  identifier  for  files
              conforming to this specification is ``hdb32/1.0\0\0\0\0\0\0\0''.

       M: metadata
              File metadata of 8 bytes consisting  of:  4  bytes  nrecs  total
              records  in database; and 4 bytes offset to start of record sec-
              tion R.

       P: hash subtable pointers
              An array of 8 pointer elements providing a ``table of contents''
              for  the 8 hash subtables in section H.  Each element P[ntab] is
              eight bytes: 4 bytes number of slots in hash  subtable  ntab;  4
              bytes  offset  to  start  of hash subtable ntab.  A subtable may
              have zero slots.

       C: descriptive comment
              An optional comment of any length, normally used to describe the

       R: records
              The  sequential  collection  of  nrecs  records in the database.
              Storage for each record R[nrec] is a concatenation of:  3  bytes
              key  length; 3 bytes value length; record key; and record value.

       H: hash tables
              An array of 8 hash subtables.  Each  subtable  H[ntab]  is  com-
              prised  of  P[ntab].tslots  slots.   Each slot is eight bytes: 4
              bytes hash value; 4 bytes offset to associated record in section
              R.  An offset value of 0 indicates an empty slot, and no associ-
              ated record exists.

       Hash values are calculated for any given byte string key of length klen
       according to the following algorithm:

           hdb32_hash(unsigned char *key, uint32_t klen)
             uint32_t  h = 0;

               h = h ^ *key;
               h = h * 37;
               ++key; --klen;

             return h;

       The subtable ntab for a given key is calculated from the relation:

           ntab = (hash % 8).

       The  subtable offset and number of subtable slots is read from P[ntab].
       The target slot for a given key in a subtable is computed from:

           target = ((HMIX(hash) >> 3) % tslots)

       where tslots is the number of  slots  in  the  subtable  as  read  from
       P[ntab], and HMIX(hash) is a bit operation defined as:

           (hash >> 13) ^ hash

       A record is located according to an open-addressing hash scheme as fol-
       lows.  First compute the hash value, subtable, and target slot for  the
       record  key.  Begin probing in subtable H[ntab], starting with the tar-
       get slot, then the next slot, and so forth, while checking at each step
       in section R for a matching key.  Continue until either the record with
       matching key is found, or until an empty slot is encountered.

       All offset and hash values  are  stored  as  32-bit  unsigned  integers
       packed  into a portable, little-endian form, 4 bytes per value.  Length
       values for keys and values are  stored  as  24-bit  unsigned  integers,
       packed into a portable, little-endian form, 3 bytes per value.  A hdb32
       file may not exceed (2^32 - 1) bytes (4 gigabytes).  Lengths  of  indi-
       vidual  keys and values may not exceed (2^24 - 1) bytes (16 megabytes).

       This specification is qualified as the ``hdb32''  version  of  the  hdb
       file  format.   It defines the standard hdb specification for a maximum
       file size based on 32-bit unsigned integers.  As the general hdb format
       may be adjusted to suit other integer types in the future, those speci-
       fications should be qualified accordingly.

       The hdb32 hash function is simple, reasonably fast,  and  readily  fac-
       tored  into  basic  machine instructions.  Otherwise it is pathetically
       unremarkable, particularly given the man-months wasted on  testing  and
       devising numerous other alternatives and parameters.

       The  function itself is mostly just the standard textbook hash, select-
       ing its mix multiplier (37) from among the usual suspects (31, 33, 37).
       It  differs  only  slightly from the K&R form by inverting the order of
       mix and combine operations.  Even with this reordering, the hash result
       is still strongly patterned by the last byte of the key.

       For  example, consider the following keys and hdb32 hash values from an
       airport codes database:

           ABJ  0x0030fbad
           ABK  0x0030fb88
           ABL  0x0030fc8b
           ABM  0x0030fc66

       As can be seen here, the hash value for each of these keys differs gen-
       erally  in  only  the final byte, and according to the last byte of the
       key.  No  avalanche  is  at  play,  no  randomness  whatsoever  in  the
       sequenced progression of bit patterns.

       Yet  despite  a lack of aesthetic and theoretical appeal, this function
       does appear to provide adequate performance within the  hdb32  context.
       The  3 bits used for subtable partitioning may provide for some disper-
       sion of aggregate clusters, and the postmix applied before slot  selec-
       tion distributes some of the better-mixed bits in the higher bytes down
       into the lower bits.  Empirical observations  suggest  that  the  hdb32
       hash/subtable  strategy  provides  for  consistent statistical behavior
       over widely varying types of record input.

       It should not be supposed that the use of multiple subtables  generally
       and universally improves hash distribution/performance when compared to
       use of a single table.  (Nor has my own testing  revealed  some  magic,
       prime  number  of subtables that would consistently outperform either a
       single table or power-of-2 multiple.)  In fact,  given  the  same  hash
       function,  a single hash table will generally have equivalent or better
       statistical properties on the same dataset when  compared  to  multiple

       The  primary  benefit  of using multiple subtables is actually found in
       the conservation of memory during hdb file generation.  By using 8 sub-
       tables, the hdb-make(1) operation uses a much smaller memory allocation
       than would otherwise be required for a single large table.

       The load factor of each hash subtable is not defined by the  specifica-
       tion.   The  reference implementation uses a load factor of 0.50.  That
       is, each subtable is set with twice as many slots as  elements  in  the
       subtable, and half the slots will be empty.

       By  convention,  hdb32 files are named with an ``.hdb'' extension.  (It
       is suggested that an ``.hdbx'' extension be used to differentiate files
       following some future hdb64 specification.)

       The  hdb  file format specification was first published with the hdb(1)
       reference implementation in December 2010.

       Wayne Marshall, http://b0llix.net/hdb/


hdb-0.03                         January 2013                           hdb(5)