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?
Printable View
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?
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.Quote:
Originally Posted by Prelude
p.s. make your next tutorial has tables :)
>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.
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
but hash("key") might be much larger than 2048.Code:void *hashtable[2048] = { NULL };
hashtable[hash("key")]
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];
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.Quote:
how do I address a smaller hash table?
Quote:
Originally Posted by Prelude
ah yes thanks.