An in-memory Hash Table

Here is my C code for a module for hash table lookup:

Makefile standard.h
recycle.h recycle.c
lookupa.h lookupa.c
hashtab.h hashtab.c
unique.c sample input

hashtab.h and hashtab.c form the hash table module. The files before those are the support files that I always use. The file after it (unique.c) is an example of how to use the hash table. (The program UNIQUE takes a file in STDIN and dumps the unique lines (duplicates removed) to STDOUT. It also shuffles the unique lines pseudorandomly. The sample input provided doesn't have any duplicate lines, so the output should be the same size as the input, but the lines will be shuffled.)

Be warned, hashtab hasn't been tested much. I played with UNIQUE some to test it, and it seems to work, but that's about it.

The hash table has a fixed hash function, and its size is a power of two. It doubles in size when it needs to, and when it doubles, it doubles all at once. It never shrinks. Input keys and data are pointed to, not copied. Keys are unique. Collisions are handled by chaining. Functions are:

The most unusual thing about this module is that it maintains a current position. This means you can't have a dangling pointer into it. If you position on something, then delete it, the position automatically moves on to some other item. On the other hand, it also means it's hard to do nested loops over all the items in the table, because there is only one position at a time.


Hash Functions and Block Ciphers
Perfect hashing
Table of Contents