5. Package for work with hash tables

The most compilers use search structures. Here the package `hashtab' which implements expandable hash tables is suggested. This abstract data implements features analogous to ones of public domain functions `hsearch', `hcreate' and `hdestroy'. The goal of the abstract data creation is to implement additional needed features. The abstract data permits to work simultaneously with several expandable hash tables. Besides insertion and search of elements the elements from the hash tables can be also removed. The table element can be only a pointer. The size of hash tables is not fixed. The hash table will be expanded when its occupancy will become big.

The abstract data implementation is based on generalized Algorithm D from Knuth's book "The art of computer programming". Hash table is expanded by creation of new hash table and transferring elements from the old table to the new table.

The package uses package `allocate'. The interface part of the abstract data is file `hashtab.h'. The implementation part is file `hashtab.cpp'. The interface contains the following objects:

Type `hash_table_entry_t'

is described as `void *' and represents hash table element type. Empty entries have value `NULL'.

Type `hash_table_t'

describes hash table itself. The type is simply synonym of `class hash_table *'.

Class `hash_table'

The class contains the following functions:

Public constructor `hash_table'

           `hash_table
              (size_t size,
               unsigned (*hash_function)
                                  (hash_table_entry_t el_ptr),
               int (*eq_function) (hash_table_entry_t el1_ptr,
                                   hash_table_entry_t el2_ptr))'
           

creates hash table with length slightly longer than value of function parameter `size'. Created hash table is initiated as empty (all the hash table entries are NULL). The hash table will use functions `hash_function', `eq_function' given as the function parameters to evaluate table element hash value and function to test on equality of two table elements.

Public destructor ` hash_table'

           `~hash_table (void)'
           

deletes given hash table and frees memory allocated for it.

Public function `empty'

           `void empty  (void)'
           

makes the hash table empty. If you need to remove all table elements, it is better to use this function than several times function `remove_element_from_entry'. This function does not change size of the table or clear statistics about collisions.

Public function `find_entry'

           `hash_table_entry_t *find_entry
                                (hash_table_entry_t element,
                                 int reserve)'
           

searches for hash table entry which contains element equal to value of the function parameter `element' or empty entry in which `element' can be placed (if the element does not exist in the table). The function parameter `reserve' is to be nonzero if the element is to be placed in the table. The element should be inserted into the table entry before another call of `find_hash_table_entry'. The table is expanded if occupancy (taking into account also deleted elements) is more than 75%. The occupancy of the table after the expansion will be about 50%.

Public function `remove_element_from_entry'

           `void remove_element_from_entry
                    (hash_table_entry_t element)'
           

removes element from hash table_entry whose value is given as the function parameter. Hash table entry for given value should be not empty (or deleted). The hash table entry value will be marked as deleted after the function call.

Public function `size'

           `size_t size (void)'
           

returns current size of given hash table.

Public function `elements_number'

           `size_t elements_number (void)'
           

returns current number of elements in given hash table.

Public function `collisions'

           `int collisions (void)'
           

returns number of of percents of fixed collisions during all work with given hash table.

Static public function `all_collisions'

           `int all_collisions (void)'
           

returns number of of percents of fixed collisions during all work with all hash tables.