quick hash table question

This is a discussion on quick hash table question within the C Programming forums, part of the General Programming Boards category; I have a 32 bit hashing algorithm, how do I address a smaller hash table? i.e. one that isn't (2^32) ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220

    quick hash table question

    I have a 32 bit hashing algorithm, how do I address a smaller hash table? i.e. one that isn't (2^32) * 4 bytes?

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Just because you're hashing 32-bit keys doesn't mean that the table needs to be able to hold every possible value. It seems like you're confusing the size of the table with the size of the hashed keys, can you be more specific about what your current setup is and how you want it to change?
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    Quote Originally Posted by Prelude
    Just because you're hashing 32-bit keys doesn't mean that the table needs to be able to hold every possible value. It seems like you're confusing the size of the table with the size of the hashed keys, can you be more specific about what your current setup is and how you want it to change?
    That's what I mean. How do I get it so my table doesn't hold every value possible? I don't want a 4gb or whatever table. Also my hash is 32 bit, my keys are arbitrary lengths.

    p.s. make your next tutorial has tables

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >How do I get it so my table doesn't hold every value possible?
    Presumably what you have now is a perfect hash table, where every possible value has a unique index. For huge ranges, that's not practical, and is the reason that hash tables exist. A hash function takes your key, then munches it up and gives you an index that can be fit into a smaller range without too many collisions. But since you're trying to fit keys from a larger range into buckets of a smaller range, you will have collisions at some point, and that's where you hear about strategies such as linear probing and separate chaining.

    In my opinion, the easiest solution is to have a small array of linked lists. When you have a collision, just add to the list. It's easy to implement, and when the hash function is good, the chains remain short enough to claim O(1) performance.

    >p.s. make your next tutorial has tables
    Okay. I was going to make hash tables either my next tutorial or my next next tutorial anyway.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    That's what I'm doing but my hash is 32 bits so it's too big for a practical hash array. How do I use a 32 bit hash on a smaller hash table? Should I just divide it or what?

    What I have now is like this
    Code:
    void *hashtable[2048] = { NULL };
    
    hashtable[hash("key")]
    but hash("key") might be much larger than 2048.
    Last edited by Brian; 07-30-2005 at 07:16 PM.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    If your hash function doesn't do it for you (which is a good thing), you can force the index into your range with the remainder operator:
    Code:
    void *hashtable[2048] = { NULL };
    
    hashtable[hash("key") % 2048];
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    May 2005
    Posts
    24
    how do I address a smaller hash table?
    the hash table can be any abitrary size (but the larger the table, the less chances for collisions to occur - if the table is too small you the won't get much performance out of it), so you calculate the actual index with GENERATED_KEY % MAX_ELEMENTS.

  8. #8
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    Quote Originally Posted by Prelude
    If your hash function doesn't do it for you (which is a good thing), you can force the index into your range with the remainder operator:
    Code:
    void *hashtable[2048] = { NULL };
    
    hashtable[hash("key") % 2048];

    ah yes thanks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. quick log lookup table
    By R.Stiltskin in forum C++ Programming
    Replies: 19
    Last Post: 12-04-2008, 12:39 PM
  2. hash table *clueless* help :)
    By willc0de4food in forum C Programming
    Replies: 2
    Last Post: 10-15-2005, 04:54 AM
  3. Hash Table Problem
    By Unregistered in forum C Programming
    Replies: 14
    Last Post: 05-21-2002, 05:34 PM
  4. Hash Table
    By ihsir in forum C++ Programming
    Replies: 0
    Last Post: 04-13-2002, 01:08 AM
  5. Quick question: exit();
    By Cheeze-It in forum C Programming
    Replies: 6
    Last Post: 08-15-2001, 06:46 PM

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