Prof. Dr. Franz Schweiggert -- Sektion Angewandte
Informationsverarbeitung -- November 6, 1997

Ingo Melzer Assignment 4

[c]

Systemnahe Software I

Allgemeine Informatik III (WS 97/98)

Part 1 and 2 are due on November 25, 1997.

A lot of database applications only need the dictionary operations
*insert, search,* and *delete*. Often hashing is used by
those applications and their tables are therefore called hash tables.
If you want to store an element with key *k* into your
hash table of size *m*, you simple store it at *h(k)*. In
other words, the hash function *h* is used to compute the slot
from the key *k*, or *h* maps the universe *U* of
keys into the slots of a hash table . The hash function
we are going to use is .
The fly in the ointment of this beautiful idea is that two keys may hash
to the same slot (*h* is usually not an injective function) - a
collision. One of the easiest solutions is called ``collision resolution
by chaining''. All elements that hash to the same slot are simply put
into a linked list:

Start implementing such a hash table. You should provide to following functions:

`insert(p,m,k), printTable(p,m)` and `delete_all(p,m)`, where
*p* is a pointer to a hash table of size *m*, and *k*
the element to use. `print` should print your hash table,
`delete_all` should delete the whole table and free memory
allocated earlier. Insert the following elements into a hash table of
size 9: 5, 28, 19, 15, 20, 33, 12, 17, 10.

Add the following functions to your solution of part 1:
`delete_one(p,m,k), search(p,m,k), rehash(p,m1,m2)` and
`utilization(p,m)`. The last function should print out the
average length of a chain as well as the longest chain.
`rehash` should transform a table of size *m1* into one of
size *m2*. Make sure that no element gets lost and free unused
memory.

Here are parts of a possible solution:

#define FALSE 0 #define TRUE 1 typedef int BOOL; typedef struct node *nodePtr; struct node { int key; /* Add your stuff here */ nodePtr next; } nodeList; typedef struct { nodePtr p; } hashtable; /* Add some lines here */ void printTable(hashtable *p, int m) { /* Add some lines here */ } void delete_all(hashtable *p, int m) { /* Add some lines here */ } void insert(hashtable *p, int m, int k) { /* Add some lines here */ } BOOL delete_one(hashtable *p, int m, int k) { /* Add some lines here */ } /* And even more lines here :-) */