Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Hash Tables

SecaSeca Member Posts: 3
Can anyone explain to me or give me an example of hashing code?

Comments

  • GiantGiant Member Posts: 225
    Hi.

    First of all you should make you questions more specific. Tell us what you know, and where your problems lie, cause your question is so general that pages if not books could be written on it, but here goes anyway.

    Hashing is a method of storing data. Linked lists are great, but it might get unefficient to search the list if it becomes to long, so hashs can be used. These also have disadvantages in that, without writing complicated procedured, they are fixed size etc...

    I will give a little example of creating a linked list to store a telephone book hashed on the persons phone number.

    First Create the structure to store the information
    [code]
    struct Info
    {
    int iPhoneNumber;
    char *lpszName;
    char *lpszAddress;
    };
    [/code]

    Now create the has table. A hash table is basically an array of pointers to the data that you want to store. Its how you hast into the table which makes it good.

    [code]
    Info* infoHashTable = new Info[HASH_TABLE_SIZE];
    for( int i=0;iiPhoneNumber % HASH_TABLE_SIZE;

    //Check to see if this place in the hash table is empty
    if( infoHashTable[iHashKey] == NULL )
    {
    //Insert the structure here
    infoHashTable[iHashKey] = infoPtr;

    return;
    }

    //Otherwise, if the position is not full move forward until we
    //do find an empty position
    int iSavedKey = iHashKey;
    iHashKey++;

    //At max we cah transvers the whole HashTable, so check for this at
    //each itteration
    while( iHashKey != iSavedKey )
    {
    //First check to see if the key has overflowed the bounds of the
    //Hash Table. If it has we have to go back to the start
    if( iHashKey == HASH_TABLE_SIZE )
    {
    iHashKey = 0;
    }

    //Check the new position
    if( infoHashTable[iHashKey] == NULL )
    {
    //Insert the structure here
    infoHashTable[iHashKey] = infoPtr;

    return;
    }

    //Still Not found, move to the next Position
    iHashKey++;
    }

    //if we get here, the HashTable is 100% full, so you can do what
    //you want
    }
    [/code]

    I hope that that describes the basics of a hash table. From this you should easially be able to write a search function etc....

    PS. I didnt compile this code, so dont know if there are any errors.

    Enjoy

    Ciaran McCormack
    www.ciaranmccormack.tk

    "Only two things are infinite, the universe and human stupidity, and I'm not sure about the former." --Albert Einstein

  • SecaSeca Member Posts: 3
    Sorry for the brief/general information. I will follow what you have told me and with any other problems, i will post it and will be more specific about it. Thanks alot.

    : Hi.
    :
    : First of all you should make you questions more specific. Tell us what you know, and where your problems lie, cause your question is so general that pages if not books could be written on it, but here goes anyway.
    :
    : Hashing is a method of storing data. Linked lists are great, but it might get unefficient to search the list if it becomes to long, so hashs can be used. These also have disadvantages in that, without writing complicated procedured, they are fixed size etc...
    :
    : I will give a little example of creating a linked list to store a telephone book hashed on the persons phone number.
    :
    : First Create the structure to store the information
    : [code]
    : struct Info
    : {
    : int iPhoneNumber;
    : char *lpszName;
    : char *lpszAddress;
    : };
    : [/code]
    :
    : Now create the has table. A hash table is basically an array of pointers to the data that you want to store. Its how you hast into the table which makes it good.
    :
    : [code]
    : Info* infoHashTable = new Info[HASH_TABLE_SIZE];
    : for( int i=0;iiPhoneNumber % HASH_TABLE_SIZE;
    :
    : //Check to see if this place in the hash table is empty
    : if( infoHashTable[iHashKey] == NULL )
    : {
    : //Insert the structure here
    : infoHashTable[iHashKey] = infoPtr;
    :
    : return;
    : }
    :
    : //Otherwise, if the position is not full move forward until we
    : //do find an empty position
    : int iSavedKey = iHashKey;
    : iHashKey++;
    :
    : //At max we cah transvers the whole HashTable, so check for this at
    : //each itteration
    : while( iHashKey != iSavedKey )
    : {
    : //First check to see if the key has overflowed the bounds of the
    : //Hash Table. If it has we have to go back to the start
    : if( iHashKey == HASH_TABLE_SIZE )
    : {
    : iHashKey = 0;
    : }
    :
    : //Check the new position
    : if( infoHashTable[iHashKey] == NULL )
    : {
    : //Insert the structure here
    : infoHashTable[iHashKey] = infoPtr;
    :
    : return;
    : }
    :
    : //Still Not found, move to the next Position
    : iHashKey++;
    : }
    :
    : //if we get here, the HashTable is 100% full, so you can do what
    : //you want
    : }
    : [/code]
    :
    : I hope that that describes the basics of a hash table. From this you should easially be able to write a search function etc....
    :
    : PS. I didnt compile this code, so dont know if there are any errors.
    :
    : Enjoy
    :
    : Ciaran McCormack
    : www.ciaranmccormack.tk
    :
    : "Only two things are infinite, the universe and human stupidity, and I'm not sure about the former." --Albert Einstein
    :
    :

  • Chris BrownChris Brown USAMember Posts: 4,496 ✭✭

    _ | http://forcoder.org | free ebooks and video tutorials about | Python Perl Swift R C++ Visual Basic Visual Basic .NET Assembly Java MATLAB C Go PL/SQL JavaScript Delphi C# Ruby Scratch PHP Objective-C Lua ML D Lisp Awk Clojure Kotlin Scheme Rust Julia COBOL Prolog Transact-SQL Erlang LabVIEW Alice Crystal F# Dart Hack SAS FoxPro Ada Logo ABAP Scala Apex Bash VBScript Fortran | ____________

Sign In or Register to comment.