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.c'. The interface contains the following external definitions:

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. All work with hash table should be executed only through functions mentioned below.

Function `create_hash_table'

        `hash_table_t create_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 and returns 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.

Function `delete_hash_table'

        `void delete_hash_table (hash_table_t htab)'
        

frees memory allocated for hash table given as parameter `htab'. Naturally the hash table must already exist.

Function `empty_hash_table'

        `void empty_hash_table  (hash_table_t htab)'
        

makes hash table given as parameter `htab' empty. Naturally the hash table must already exist. If you need to remove all table elements, it is better to use this function than several times function `remove_element_from_hash_table_entry'. This function does not change size of the table or clear statistics about collisions.

Function `find_hash_table_entry'

        `hash_table_entry_t *find_hash_table_entry
                             (hash_table_t htab,
                              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%.

Function `remove_element_from_hash_table_entry'

        `void remove_element_from_hash_table_entry
              (hash_table_t htab, 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.

Function `hash_table_size'

        `size_t hash_table_size (hash_table_t htab)'
        

returns current size of given hash table.

Function `hash_table_elements_number'

        `size_t hash_table_elements_number (hash_table_t htab)'
        

returns current number of elements in given hash table.

Function `hash_table_collisions'

        `int hash_table_collisions (hash_table_t htab)'
        

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

Function `all_hash_table_collisions'

        `int all_hash_table_collisions (void)'
        

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