Hashing Routines

struct h_table *h_init(int size)

Initilize a hash table to size. This expects a prime number as the simple minded hashing function hashes the key modulo table size. I usually use 2^n-1 sizes since they're (always?) prime.

void h_destroy (struct h_table *h)

Release all storage from the given hash table.
Note that any payload you attach to h_nodes is your responsibility. H_destroy assumes nothing.

void * h_get (struct h_table *tb, register char *s)

given the table and key s, return the value in h_obj. This can be any value at all, but is normally a pointer to your data structure.

struct h_node * h_put (struct h_table *tb, register char *s, void * o)

Put the payload in o into the hash table accessible by key s. The payload can be anything at all, but is normally a pointer to your own data structure.

int h_del (struct h_table *tb, register char *s)

Remove the node associated with key s.

int hash (struct h_table *tb, register char *s)

The internal hashing function. Ignore the man behind the curtain.

void h_analyse (struct h_table * tb, int * sz, int * ptot, int * min, int * max, double * avg, int * nempty)

generate some statistics given the hash table. Pass pointers to the various fields to store the results. They are:
  • sz: number of buckets in the table
  • ptot: total number of nodes in the table
  • min: the smallest bucket
  • max: the largest bucket
  • avg: the average size of each bucket
  • nempty: the number of empty buckets

void h_printstats (char * name, struct h_table * tb, int first)

Print statistics given the above and some internally stored values. First controls printing out the title, and name is the name of your table.

The description of each field is the same as above, but hits is the total number of lookup requests, and depth is the average search depth once we've hash to the node (smaller is better).

Here is a run from a debugger with oodles of nodes.

      table  buckets total min   max  empty hits    depth average
      UST    8191    2437  0     7    6865  2527    1.762 0.298
      Struct 8191    6632  0     21   6787  26484   3.877 0.810
      Func   2047    1132  0     5    1240  1133    1.000 0.553
      
Generally decent results, but I'm sort of clueless why Struct is so concentrated in so few buckets. Even as unhappy as it looks, it's still much better than a binary tree or even a 2-3 tree whose average depth would be about 10 (8-13).


© (copyright) 1997 MTCC
Last modified: Fri Apr 25 20:24:23 PDT 1997