Calculating the upper bounds on a hash table.

This is a discussion on Calculating the upper bounds on a hash table. within the C Programming forums, part of the General Programming Boards category; I have no clue how this expression gets derived. Say I'm given a hash table. Now I decided to double ...

  1. #1
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195

    Calculating the upper bounds on a hash table.

    I have no clue how this expression gets derived.

    Say I'm given a hash table. Now I decided to double the hash table and rehash everything. How does the total number of hashes for a table with m+1 elements become

    1 + 2*m/2 + 3*m/4 + 4*m/8 + 5*m/16 + 6*m/32 +....

  2. #2
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    Okay, I'm glad that I actually sat down and thought about it at work since on one seems to know.

    Okay, I have a hash table with one 1 element and is size one. I add another element, but double the size of the hash. This becomes a hash with 2 elements and a size of 2. Now I ad one more element and double the hash again, this becomes a hash with 3 elements and size of 4. Each time I double the hash key, I add to the previous element. I'm assuming the reason why that we multiply by a factor of m each time we add an element is because the average linked list length on a hash key is tends to be 2 to 3.

    Ie for 2 elements, there could be 4 to 6 entries, for 3 elements 6 to 8.

    So with that, the expression becomes

    1 + 2*m/2 + 3*m/4 + 4*m/8 + 5*m/16 + 6*m/32 +....

    or 3m+1. Ie, the hash increases in linear time everytime the hash gets doubled.

    Okay, so I guess Mr. Theo de raadt from the OpenBSD project was correct in his assertion that having an algorithm that doubles the hash table (vs geometric increases) is generally a bad idea.

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