Thread: Hash table creation and insertion

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    3

    Hash table creation and insertion

    Hi,
    I am working on implementation of a hash table.

    In a given string I have to find the first word which is not repeated in the string.

    Now as a hash function I am simply using atoi(str).

    So for "total", I get following

    t 116
    o 111
    t 116
    a 97
    l 108

    I am able to do uptil this properly.
    Now I want to create hash table and store this in hash table which will have 3 columns.

    index........converted_int.........count

    1................ 116...................... 2
    2.................111.......................1
    3.................97.........................1
    4..................108......................1


    So after this things are stored in hash table , then I can search the count values in the order of the characters in the original string and see which first character is not reapeated (seeing the count = 1)
    I am almost able to do the conversion of given characters in string.

    Can someone tell me how can I create hash table for this and insert these values in it? I am struggling a lot.

  2. #2
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    You don't need/want to use atoi() on a single character. You'd simply take the value of the char variable:
    Code:
    #include <stdio.h>
    int main(void) 
    {
        char word[] = "total";
        int i;
        for (i = 0; i < sizeof word - 1; i++)
        {
            printf("%c %d\n", word[i], word[i]);
        }
        return 0;
    }
    My output:
    Code:
    t 116
    o 111
    t 116
    a 97
    l 108
    As for your "hash table", you are not really implementing a hash table, you just need an array to store all possible character values, so something like:
    Code:
    #include <limits.h>
    
    int count[CHAR_MAX + 1]; /* but see footnote */
    You can then iterate through the string like my for loop above, increasing count[value] each time. Then you can iterate through the string again, finding the first character where count[value] is still 1.

    Footnote:

    Most systems you encouter will likely have a CHAR_MAX of 127 and a CHAR_MIN of -128, which denotes that a char on that system can be between -128 and 127. These values don't matter, but the point is that CHAR_MIN can (and often will) be negative.

    Therefore you have to be careful you do not end up trying to access count[negative_number]. One simple approach is to check that it's >= 0 before assignging it to your count array and ignore characters that fall outside.

    A more thorough approach would be to declare your array instead as:
    Code:
    int count[CHAR_MAX - CHAR_MIN + 1];
    And then use an offset when you assign to make sure your result is always in range:
    Code:
    count[value - CHAR_MIN]++;
    instead of just:
    Code:
    count[value]++;
    Of course, another solution is just to explicitly use an unsigned char instead.
    Last edited by cwr; 01-23-2006 at 08:04 PM.

Popular pages Recent additions subscribe to a feed