Hash Tables

Hash tables are a simple and effective method to implement dictionaries. Average time to search for an element is O(1) while worst-case time is O(n). Cormen [2001] and Knuth [1998] both contain excellent discussions on hashing.

Theory

A hash table is simply an array that is addressed via a hash function. For example in Figure 3-1 hashTable is an array with 8 elements. Each element is a pointer to a linked list of numeric data. The hash function for this example simply divides the data key by 8 and uses the remainder as an index into the table. This yields a number from 0 to 7. Since the range of indices for hashTable is 0 to 7 we are guaranteed that the index is valid.


Figure 3-1: A Hash Table

To insert a new item in the table we hash the key to determine which list the item goes on and then insert the item at the beginning of the list. For example to insert 11 we divide 11 by 8 giving a remainder of 3. Thus 11 goes on the list starting at hashTable[3]. To find a number we hash the number and chain down the correct list to see if it is in the table. To delete a number we find the number and remove the node from the linked list.

Entries in the hash table are dynamically allocated and entered on a linked list associated with each hash table entry. This technique is known as chaining. An alternative method where all entries are stored in the hash table itself is known as open addressing and may be found in the references.

If the hash function is uniform or equally distributes the data keys among the hash table indices then hashing effectively subdivides the list to be searched. Worst-case behavior occurs when all keys hash to the same index. Then we simply have a single linked list that must be sequentially searched. Consequently it is important to choose a good hash function. Several methods may be used to hash key values. To illustrate the techniques I will assume unsigned char is 8-bits unsigned short int is 16-bits and unsigned long int is 32-bits.

Assuming n data items the hash table size should be large enough to accommodate a reasonable number of entries. As seen in Table 3-1 a small table size substantially increases the average time to find a key. A hash table may be viewed as a collection of linked lists. As the table becomes larger the number of lists increases and the average number of nodes on each list decreases. If the table size is 1 then the table is really a single linked list of length n. Assuming a perfect hash function a table size of 2 has two lists of length n/2. If the table size is 100 then we have 100 lists of length n/100. This considerably reduces the length of the list to be searched. There is considerable leeway in the choice of table size.

Table 3-1: HASH_TABLE_SIZE vs. Average Search Time (Ás) 4096 entries
size time size time
1 869 128 9
2 432 256 6
4 214 512 4
8 106 1024 4
16 54 2048 3
32 28 4096 3
64 15 8192 3

Implementation in C

An ANSI-C implementation of a hash table is included. Typedefs recType keyType and comparison operator compEQ should be altered to reflect the data stored in the table. The hashTableSize must be determined and the hashTable allocated. The division method was used in the hash function. Function insert allocates a new node and inserts it in the table. Function delete deletes and frees a node from the table. Function find searches the table for a particular value.

Implementation in Visual Basic

The hash table algorithm has been implemented as objects using a module for the algorithm and a class for the nodes. It has also been implemented as a class using arrays. The array implementation is recommended.