Package Overview

The Hash package contains sub-packages of functions for managing hash tables with binary or string keys. Both sub-packages build upon the basic idea of a simple hash table. A hash table consists of two pieces: the data store and the hashing function. The data store is an array of n cells. Each cell has an index that lies in the range 0 to n-1. The hashing function is a mathematical operation performed on the key that returns an integer between 0 and n-1. When a client inserts a new (key,value) pair into the hash table, the hashing function determines the cell used to store the value. The hashing function also can be used to retrieve the value associated with a given key.

Because there is a finite address space, it is possible that two different keys will map to the same cell (a collision). In such cases, the Hash package adds the new value to a linked list in the target cell. A larger hash table will have fewer collisions, but will require more memory to accommodate the table as a whole. The number of unique (key,value) pairs you can insert into a hash table is limited only by available workstation memory.

If a hash table must store values for duplicate keys, we recommend using manually maintained lists for each duplicate key. This produces a data structure such as the one shown in Figure 1. Each hash table cell contains either a single (key,value) pair or an automatically maintained linked list of unique (key,value) pairs, in which some of the values can be manually maintained lists of multiple values for the same key. The workflow to implement this chaining method is described with prg_bin_hash_table_item_insert() and prg_string_hash_table_item_insert().

WARNING: For efficiency reasons, the functions in the Hash package have not been made MT-safe. Thus, in parallel simulations, access to shared hash tables must be externally serialized.

Figure 1: Hash Table Structure Example

Hash Table Structure Example