hash table

[ankit894u]

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

[Danny_501]

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

[ankit894u]

#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

[Danny_501]

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

[ankit894u]

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

[Danny_501]

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;

[ankit894u]

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