Skip to main content
GameDev.net gamedev.net
🔒 Locked

Question on hash tables

Started by cronodragon Jan 1, 2007 at 7:03 PM 13 replies 2.5k views
Original Post
cronodragon
cronodragon
I was looking for information on hash tables, and found quite a lot in Wikipedia and some books... but, I'm not very confident on the solutions everyone propose. I implemented a solution that works fine, but I don't want to keep the doubt, because I could be missing something that might make my algorithm faster. First, I'll explain that I need a table that is indexed with string keys... indeed I made a base class that accepts any type of key using generic pointers, but the main usage of inherited tables is with string keys. Also, the tables are nodes of a multinode tree. My doubt is about the hashing algorithm. As I understood it, the idea is representing the string key with a data type that is smaller and faster to index, like an integer. But, I don't think it will always work perfectly. There must be some cases where strings will share the same hash code, and I don't want to allow this to happen. On the other hand, having a static array for all the possible hash codes seems to be a big waste of memory. In example, an array of 65536 elements (let's say pointers) would mean 65536 * (4 bytes) is too much, and returning to the other doubt, I don't think 16 bits is enough to encode every key... but what's enough? 32 bits, 64 bits??? The only reliable way I can think of is a data type long enought to store a compressed version of the string. Now what I did is based on the QuickSort algorithm. I just sort every inserted key halving the list each time to find the right place. And to extract the information I do the same. Since the list is always sorted it isn't too slow to find something... althought there is a delay that I would like to reduce as possible. Any advice on this will be greatly appreciated. Byt the way, HAPPY NEW YEAR! :D
Sneftel
Sneftel
The hash function you're describing, where there are no collisions, is known as a "perfect hash function". Unfortunately, in most situations no such function can easily be used. So hash tables are designed to be resilient against a reasonable number of hash collisions. With a properly-designed hash table the occasional collision is not a problem.

Additionally, having a 32-bit hash value does not mean your hash table must have 2^32 buckets. You can have as few buckets as you like; if you had, say, only two buckets, you could assign half of the hash values to the first bucket and the other half to the second bucket. This allows the hashtable to vary independently of the hash function.

What you have designed does not sound like a hash table. It's hard to tell from your description, but it seems like it's just binary search over a sorted array.
cronodragon
cronodragon
Quote:
Original post by Sneftel
The hash function you're describing, where there are no collisions, is known as a "perfect hash function". Unfortunately, in most situations no such function can easily be used. So hash tables are designed to be resilient against a reasonable number of hash collisions. With a properly-designed hash table the occasional collision is not a problem.


I don't understand why is it "perfect", without collisions... I can't believe that. Would like someone to explain why.

Quote:
Original post by SneftelWhat you have designed does not sound like a hash table. It's hard to tell from your description, but it seems like it's just binary search over a sorted array.


But it's not a hast table because it doesn't use a hash algorithm? In the end the sorted list and the hash table solve the same problem, although they address it in different ways, isn't it?
LessBread
LessBread
Bob Jenkin's hashing pages are among the best general reference on the subject (imo) Hash Function FAQ
"I thought what I'd do was, I'd pretend I was one of those deaf-mutes." - the Laughing Man
cronodragon
cronodragon
Quote:
Original post by LessBread
Bob Jenkin's hashing pages are among the best general reference on the subject (imo) Hash Function FAQ


I'll check it now. Thanks!
Sneftel
Sneftel
Quote:
Original post by cronodragon
Quote:
Original post by Sneftel
The hash function you're describing, where there are no collisions, is known as a "perfect hash function". Unfortunately, in most situations no such function can easily be used. So hash tables are designed to be resilient against a reasonable number of hash collisions. With a properly-designed hash table the occasional collision is not a problem.

I don't understand why is it "perfect", without collisions... I can't believe that. Would like someone to explain why.

Because a hash function, by definition, loses information. There is no way to represent all possible ten-byte strings, for instance, by a perfect hash function with less than ten bytes.



Quote:
Quote:
Original post by SneftelWhat you have designed does not sound like a hash table. It's hard to tell from your description, but it seems like it's just binary search over a sorted array.

But it's not a hast table because it doesn't use a hash algorithm? In the end the sorted list and the hash table solve the same problem, although they address it in different ways, isn't it?
Yes, but that doesn't make it a hash table. There are plenty of data structures which allow you to look things up. Yours is one of them, but it isn't the hash table one.
DouglasThompson
DouglasThompson
Quote:
There must be some cases where strings will share the same hash code, and I don't want to allow this to happen.


These cases are called collisions, and they'll happen unless you have that "perfect hash function", which probably isn't worth chasing after. A GOOD hash function, yes, but not a "perfect" one...

Quote:
On the other hand, having a static array for all the possible hash codes seems to be a big waste of memory.


Hash functions ARE a big 'waste' of memory, if you want good performance--you're going to have to have a table that's maybe two times bigger than the number of actual keys...

I don't think the performance hit of a collision is as bad as you think it is. If you were using a binary sort on a sorted array, you'd get pretty close to log(n) probes on average. So with 65k items, it'd take almost 16 probes on average. If you used a hash table with, say, 3 collisions (note: you'll usually hash to your value with 0 or 1 collisions), it'll take 3 or 4 probes. What's faster then? A hash function with a few collisions, or a binary search on a sorted array? Also remember, you gotta keep the array sorted for the binary search to work. Not fast at all.

I'm not sure if this addresses your question or not... I think LessBread's link is a good one, though... good luck!

Also, If you need to list your elements in order for some reason, hashing may not be a good solution.

Also, to clarify "good performance"--as tables fill up, the number of collisions starts to rise much more sharply, depending on how you probe your table (linearly, randomly etc)... a table that's 50% empty will generally have 0..2 collisions or something like that. As the table fills more, the collisions rise much more sharply. I'm heading out the door atm, but I'll try to find sources for this and more info when I get back.
Scuppy
Scuppy
Arent you just looking for a compression algorithm?
iMalc
iMalc
Quote:
Original post by Sneftel
Quote:
Quote:
Original post by Sneftel
What you have designed does not sound like a hash table. It's hard to tell from your description, but it seems like it's just binary search over a sorted array.

But it's not a hast table because it doesn't use a hash algorithm? In the end the sorted list and the hash table solve the same problem, although they address it in different ways, isn't it?
Yes, but that doesn't make it a hash table. There are plenty of data structures which allow you to look things up. Yours is one of them, but it isn't the hash table one.
Indeed what cronodragon has not implemented is not a hash table.
Hashing does not involve sorting, or binary searches.

I second the link LessBread posted. It is very good. I especially like the point about hash functions that rely on modulus with a prime number at the end being bad. It also metions CRC being a good choice and I totally agree with that, as it has served me very very well numerous times.

Have you considered using std::tr1::unordered_map?[google]
cronodragon
cronodragon
Thanks for the comments. Now I understand better the concept of hash table.

I decided to enhance my sorted table using the ideas from hash tables. I'm thinking on using an algorithm like CRC, as suggested, as a first index to find the string key in the array. That must accelerate the initial search of the key. Each CRC will have a sorted list of the actual string keys that collide with it, and an usual search will be used here to find the needed one. From what I read in the tutorials, CRC is good because it changes completely when a bit changes, distributing the collisions better. I don't know the maths behind that, but I think that having a good distribution would mean, I'll be dividing the steps need to find the string key by the size of the CRC value. Let's say a 8 bit code, would divide the search steps by 256... that's my guess.
Sneftel
Sneftel
Why would you have an array sorted by hash value instead of a hash table? What do you think it would gain you over the use of hash tables?
Vorpy
Vorpy
The problem with sorted arrays is the O(n) cost of inserting an element; all the elements after the inserted one need to be shifted over. If all the insertions are done first, to build the, uh, lookup array, then it might be ok since the lookups will be O(log(n)).

The std::map container gives O(log(n)) insertions, lookups, and deletions (probably implemented with a balanced binary tree algorithm). It also keeps the elements sorted.

A hash table (assuming a good hashing algorithm is used) has O(1) insertions, lookups, and deletions. It achieves this by using buckets and not keeping the elements sorted (not even by their hash code). Chained hashing, where colliding elements are all kept in a list attached to their bucket, doesn't even use sorting within the bucket because the number of collisions is expected to be low (within a constant factor related to the size of the table and the number of entries stored in it). If the table gets too full it can be enlarged to reduce the number of collisions. Resizing is an O(n) operation, but by enlarging the table by a multiple of its current size (doubling is probably a good idea) the cost of insertions is still an amortized O(1). Inserting n elements will incur a resizing cost of O(n), giving an average resizing cost per insertion of O(1).
Kylotan
Kylotan
Quote:
Original post by cronodragon
I decided to enhance my sorted table using the ideas from hash tables. I'm thinking on using an algorithm like CRC, as suggested, as a first index to find the string key in the array. That must accelerate the initial search of the key.


The idea of a hash table is that the hash function quickly gives you a way of distributing the values within the structure. CRCs however are not quick - they are optimised for minimal collisions, but not for quick calculation. If calculating the hash value is an expensive operation, then you're wasting time you could have just spent searching normally.

A quicker hash function might be to add the first few characters together, divide by some prime number, and use the remainder. You may even get away with just hashing on the first letter of the string, if your strings are quite varied. There are probably some better ideas if you Google for them, but keep it simple, if fast lookup is what you're after.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.