Using a hash table with eleven locations and the hashing function h(i) = i%11, show the hash table that results when the following integers are inserted in the order given: 26, 42, 5, 44, 92, 59, 40, 36, 12, 60, 80. The collisions are resolved using chaining.

int h(int i)
{ return i % 11;}

i knw tht hash table caan be implemented as an intger arrat table in which each array element can be intialized a dummy value such as -1.

i dont knw how to start writing the code m totally blank right now...push me need help pls it wil be a gr8 favor..thank u so much..i dont want u guys to do my homework but pls write something from where i can start off

Recommended Answers

All 6 Replies

To implement a hash table with your own hash function, you must make your own classes. Like HashNode.cpp and HashTable.cpp..

Without getting to technical - HashTable is a dynamic array of HashNode's. And HashNode is a link list of values. HashNode contains a key, a value and a pointer to the next node in the link list (hope thats not to confusing). The link list is for chaining purposes.

read this to get a better understanding:
http://en.wikipedia.org/wiki/Hash_table

Chaining:
http://en.wikipedia.org/wiki/Hash_table#Separate_chaining

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

//1.We begin with our linked lists (for separate chaining):


    typedef struct _list_t_ {
        char *string;
        struct _list_t_ *next;
    } list_t;

//2. Now we need a hash table structure.


    typedef struct _hash_table_t_ {
        int size;       /* the size of the table */
        list_t **table; /* the table elements */
    } hash_table_t;


//1. Creation. We need to be able to create a hash table, something like:


    hash_table_t *my_hash_table;
    int size_of_table = 11;
    my_hash_table = create_hash_table(size_of_table);

//The creation function might look something like this:


    hash_table_t *create_hash_table(int size)
    {
        hash_table_t *new_table;
        
        if (size<1) return NULL; /* invalid size for table */

        /* Attempt to allocate memory for the table structure */
        if ((new_table = malloc(sizeof(hash_value_t))) == NULL) {
            return NULL;
        }
        
        /* Attempt to allocate memory for the table itself */
        if ((new_table->table = malloc(sizeof(list_t *) * size)) == NULL) {
            return NULL;
        }

        /* Initialize the elements of the table */
        for(i=0; i<size; i++) new_table->table[i] = NULL;

        /* Set the table's size */
        new_table->size = size;

        return new_table;
    }
//2. Our hash function. We'll go with a relatively simple one.


    unsigned int hash(hash_table_t *hashtable, char *str)
    {
        unsigned int hashval;
        
        /* we start our hash out at 0 */
        hashval = 0;

        /* for each character, we multiply the old hash by 31 and add the current * character.  Remember that shifting a number left is equivalent to * multiplying it by 2 raised to the number of places shifted.  So we * are in effect multiplying hashval by 32 and then subtracting hashval. * Why do we do this?  Because shifting and subtraction are much more * efficient operations than multiplication.
         */
        for(; *str != '\0'; str++) hashval = *str + (hashval << 5) - hashval;

        /* we then return the hash value mod the hashtable size so that it will
         * fit into the necessary range
         */
        return hashval % hashtable->size;
    }

//3. String lookup. Doing a string lookup is as simple as hashing the string, going to the correct index in the array, and then doing a linear search on the linked list that resides there.


    list_t *lookup_string(hash_table_t *hashtable, char *str)
    {
        list_t *list;
        unsigned int hashval = hash(hashtable, str);

        /* Go to the correct list based on the hash value and see if str is
         * in the list.  If it is, return return a pointer to the list element.
         * If it isn't, the item isn't in the table, so return NULL.
         */
        for(list = hashtable->table[hashval]; list != NULL; list = list->next) {
            if (strcmp(str, list->str) == 0) return list;
        }
        return NULL;
    }

//4. Inserting a string. Inserting a string is almost the same as looking up a string. Hash the string. Go to the correct place in the array. Insert the new string at the beginning.


    int add_string(hash_table_t *hashtable, char *str)
    {
        list_t *new_list;
        list_t *current_list;
        unsigned int hashval = hash(hashtable, str);

        /* Attempt to allocate memory for list */
        if ((new_list = malloc(sizeof(list_t))) == NULL) return 1;

        /* Does item already exist? */
        current_list = lookup_string(hashtable, str);
            /* item already exists, don't insert it again. */
        if (current_list != NULL) return 2;
        /* Insert into list */
        new_list->str = strdup(str);
        new_list->next = hashtable->table[hashval];
        hashtable->table[hashval] = new_list;

        return 0;
    }

this is wht i could manage to write can someone pls help me out

Where did you get this code from? Have you tested it?

If you want to use this code, you need to modify the Hash function:

#
unsigned int hash(hash_table_t *hashtable, char *str)

to suit your question

h(i) = i%11

i got it by working wid one of my friend...hey can u pls edit in my code itself...pls its a request

No i shouldn't, that would be doing your homework for you. If your wrote this code yourself then you should know how to modify the hash function.

hint:
this line needs to be midified:

for(; *str != '\0'; str++) hashval = *str + (hashval << 5) - hashval;

hey frankly speaking its not totally done by me ...my friend helped me can u help me change the hash function and yes i was getting like 14 errors when i run the program...pls

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.