Hash Table

This is a discussion on Hash Table within the C++ Programming forums, part of the General Programming Boards category; When two different items have the same hash and we want to insert them in the hash table (that is ...

  1. #1
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231

    Hash Table

    When two different items have the same hash and we want to insert them in the hash table (that is an char[][] here), we have a collision. We have to insert that item in the nearest empty slot (the book says). Now think we have a word "sia" that has a hash== 23 and we have also another word "track" that has the same hash code. The array[23] is filled with "sia" and array[24] is empty. So "track" will be placed there.
    Now what if we get a word for example "chance" with the hash equal to 24? It will replace "track"! Is this behavior usual in this kind of hash tables?
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    It won't replace "track", there will be a collision and it will be placed in the next empty slot.

    Another option to handle collisions is to keep a linked list at each slot, so values that elements to the same value are added to the list.

  3. #3
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    Another option to handle collisions is to keep a linked list at each slot, so values that elements to the same value are added to the list.
    Then it will be something like:
    Code:
     |
     |
     >---
     >-
     |
     >--
    Where | is empty slot. and >-- is a filled slot and a chain of linked list.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Sure. Obviously, this can result in major slowdown if the hash function isn't good or if the table is too small, because it turns into a linear lookup. But otherwise it is usually sufficient.
    Last edited by Daved; 08-29-2006 at 04:32 PM.

  5. #5
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    Thanks, I'll think about it more.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 09:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 06:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 09:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21