🔒 Locked

Hash Tables ?

Started by silvermace Jun 11, 2002 at 8:24 PM 21 replies 550+ views

Original Post

Jun 11, 2002 at 8:24 PM

I know there is a vast amount of knowledge here, so How do hash tables work, and what are they used for, i''ve often seen them in MPEG decoders, JPEG etc, so im guessing for fast look up tables or something??? Does anyone know any tutorials etc.?? Any help thanx. //silvermace

LessBread

Jun 11, 2002 at 9:12 PM

Um, a hash table ''hashes'' a string into a value that is then used as an index into a list where the string is then stored. There are plenty of tuts and examples on the www. This is one topic that google should be able to help out with.

KalvinB

Jun 12, 2002 at 5:59 AM

Basically a "hash" (as I use it anyway) is a mathematical representation of a string.

  
int ToHash(char * str)
{
	int temp=0;
	char * ar = (char*)&temp
	for (int j=0; j<strlen(str); j++)
		ar[j%4] = ar[j%4] ^ *str++;
	return temp;
}

Then, instead of doing a strcmp you hash the search string with the same fuction and look through the table for the matching int. When you find it, you then do a strcmp to verify incase two different strings somehow get the same hash value.

I just just a struct that stores the original string and it''s hash value.

It''s incredibly fast and easy to use.

Ben

IcarusIndie.com [ The Rabbit Hole | The Labyrinth | DevZone | Gang Wars | The Wall | Hosting ]

silvermace

Jun 12, 2002 at 6:04 AM

thanx, that helps a bit, but i dont quite understand

eg. this is an example
i want "Hello World"
can i contruct this using a hash table and a string "Helo Wrd"?

thanx KalvinB, /* clears up alot */

Atavist

Jun 12, 2002 at 12:30 PM

Hash tables: the illigitimate child of an array and linked-list.

Has the pros of both and the cons of both in lesser degrees.
For those times when a linked-list is too slow and an array is too large.

Arild Fines

Jun 12, 2002 at 3:50 PM

quote:

PS: Yes, a binary search tree would be even faster, but that''s not the point of this thread. Sometimes hash tables make more sense, some times they don''t.

Hmm... technically a hash-table lookup should be close to constant time, depending on the load factor and the collision resolution method chosen. Why would a BST(which is usually around O(log n), IIRC) be faster?

quote:
Original post by Atavist
Hash tables: the illigitimate child of an array and linked-list.

Not sure I see that comparison, since neither of those can be used to implement an efficient dictionary.

Atavist

Jun 12, 2002 at 4:04 PM

quote:
Not sure I see that comparison, since neither of those can be used to implement an efficient dictionary.

Perhaps you do but don''t realize it.
For those times an array is too large and a linked-list is too slow.
Seems to me that an efficient dictionary is obviously one of those times.

A hash table like an array has fast random access (in the theoretical optimal model) and like a linked-list doesn''t waste memory for non existant entries (again assuming an evenly distributed hash)

Kylotan

Jun 12, 2002 at 8:04 PM

quote:
Original post by Arild Fines
Not sure I see that comparison, since neither of those can be used to implement an efficient dictionary.

DerekSaw

Jun 12, 2002 at 8:08 PM

Basically, one of the idea of hashing is something like you are having 10,000 of ping-pong balls, but you only have 1,000 of baskets to store them. So when you are searching for a particular ball, you just only need to search just one basket that have it (the dictionary example mentioned above).

The other is: (copy-paste

)
Hashing is something like you are having unknown large number of ping-pong balls, but you only have limited number of small boxes (that could only store a single ball) to store them.... hoping that no two balls need the same box, or technically we say, the box uniquely identifies the ball. (e.g. MD5)

just my 2cents

silvermace

Jun 13, 2002 at 12:00 AM

omg. i go to school for 6hrs and i get 7 responses, thanx to EVERYONE, man they really are worth learning, hash tables sound sooo qool !!!!

its great to see the enthusiasm in these forums man!

thanx 2 all
..:: SiLv3rMaC3 ::..

DrPizza

Jun 13, 2002 at 12:49 AM

quote:
Not sure I see that comparison, since neither of those can be used to implement an efficient dictionary

Cconsider a number -> name lookup where the numbers are 32-bit integers. Arrays aren''t sparse, so will require an array that encompasses the entire range, but give O(1) lookups. A linked list only allocates storage for the elements you store, but has O(n) lookups. A hash-map has (approximately) the memory usage characteristics of the linked list, but (approximately) the performance characteristics of the array.

ragonastick

Jun 13, 2002 at 12:56 AM

quote:
Hashing can be used to uniquely identify documents in a small amount of space (eg: an MD5 hash will calculate a 16 byte value that is unique for any chunk of data of any size).

It can''t be unique for any chunk of data of any size. If it was, then it would be the worlds best compression

With hash tables, one of the issues you have to deal with is collisions - when multiple items share the same hash. There are a variety of methods used to fix that, and I''d say the www is best for finding them.

Trying is the first step towards failure.

silvermace

Jun 13, 2002 at 12:58 AM

thanx again all
im learning heaps !

daerid

Jun 13, 2002 at 1:03 AM

quote:
Original post by ragonastick
It can''t be unique for any chunk of data of any size. If it was, then it would be the worlds best compression

not necessarily true.

you go and try reverse engineering an MD5 sum of a 600+ mb .bin file.

MD5 is just one-way, that''s all.

codecs have to be 2 way, or they''re useless as such.

ragonastick

Jun 13, 2002 at 2:11 AM

quote:
Well, statistically speaking it's unique enough that the chances of coming up with two different documents that resolve to the same hash value are atronomical (in normal, every day use).

Statistically speaking, as soon as the data is longer than 16 bytes, there must be some overlap.

quote:

you go and try reverse engineering an MD5 sum of a 600+ mb .bin file.

MD5 is just one-way, that's all.

codecs have to be 2 way, or they're useless as such.

You can brute force it, and if it did work, then I will still stand by my claim that it is the worlds best compression. Sure the decompression time would be long, but the fact that it would be possible to compress gigabytes of data into 16 bits.... anyway, I'm sure you can see why it wouldn't work. Basic information theory.

Also, in a discreet, deterministic situation (ie a computer), everything can be reversed, even if that means brute force.

quote:

(in normal, every day use).

Oh, I missed that. I will say that it really depends on what you are hashing, your game might have 2^(8*16) + 1 different things in it which need hashing, and you are guaranteed to have collisions there. (for interests sake, 2^(8*16) = 3.4*10^38), so yes, it is a lot - but I am also guessing that in all the permutations up to 2^(8*16), there will be some collisions anyway.

Assuming that you will not get collisions is foolish, it isn't that hard to bullet proof, and in many applications, you will have 2 identical items. Hashing these items for the purpose of storing them in a hash table will cause a collision - and this can be everyday use.

Edit: I forgot to make clear that I do realise that 2^(8*16) is a really big number and for most things, the only time you get a collision is with identical data, but - it is important that you don't assume that a collision can't happen.

Trying is the first step towards failure.

[edited by - ragonastick on June 13, 2002 3:14:11 AM]

silvermace

Jun 13, 2002 at 2:34 AM

lets keep this rolling guys ...

wolverine

Jun 13, 2002 at 2:51 AM

quote:
Original post by Anonymous Poster
A hash table would only be faster if it''s a near perfect hash (few or no collisions). This is certainly possible if you have more buckets than data elements, but that''s probably not practical in a large dictionary lookup like my example.

If you need to search for one string in a list of a million, a binary search will result in anywhere from 1 to something like 20 string comparisons at most.

The same dictionary stored in a hash table with 1,000 buckets and a decent hash function will result in sets of 1,000 strings which need to be searched linearly, meaning anywhere from 1 to 1,000 string comparisons with an average of 500.

At best they''re the same speed, at worst the hash table is 50 times slower (in this example). The larger the number of buckets, the faster the hash table gets, but that usually also means more overhead.

Mark

Yes, but in a binary search, you would have to have the elements ordered. The insertion in a Hash Table is =~ O(1). Besides, some variations of hash tables use trees instead of lists, making the search lighter.

ragonastick

Jun 13, 2002 at 3:00 AM

quote:

Also, in a discreet, deterministic situation (ie a computer), everything can be reversed, even if that means brute force

Oh, I should probably also clarify this. By "reverse", I mean, find an inverse. Just like other inverse functions, there might be multiple solutuons

eg:

f(x) = 1

Inverse is

g(1) = x (for all x)
g(!1) = undefined

So I am saying that f(x) is reversable: f(2) = 1. f(1) = x, which includes 2.

For the compression to work, there must be an inverse function which doesn''t have multiple solutions. And I am saying that hashing does have multiple solutions.

quote:

lets keep this rolling guys ...

I wasn''t sure if this was sarcastic or not

, but I''ve made my point now. I don''t think it needs much more elaboration.

silvermace

Jun 13, 2002 at 6:23 AM

no, its not sarcastic!
i mean it, this discussion is really interesting

// silvermace
5W17ch check out the hello world stuff on my site...

Topic Locked

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