 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| An Introduction to Hash Tables with Chaining |
|
 |
rdfodra Member since: 3/17/2004 From: Brazil |
|||
 Posted - 3/17/2004 11:29:39 AM |
||||
| Don't implement hash tables, use std::hashmap instead (requires C++) http://www.sgi.com/tech/stl/ Ricardo, Brazil. |
||||
|
||||
|
Unwise owl Member since: 12/30/2001 From: Sweden, United States of Europe |
|||
 Posted - 3/17/2004 11:43:32 AM |
||||
I still think it might be good to implement one for learning purposes (it is always good to know what goes on behind the scenes). Therefore I much appreciated this article, as I haven't really bothered to read up on hash tables before. I am off to do something like this now.  |
||||
|
||||
 |
krez GDNet+ Member since: 10/10/2001 From: NJ - The Garbage State |
|||
 Posted - 3/18/2004 6:56:18 PM |
||||
| not all implementations of STL include hashmap. besides, it is a good learning excercise. in addition, it is possible that by rolling your own and playing with the hashing algorithm (as in this article) you can get better distribution than a generic hashmap. |
||||
|
||||
|
kapouille Member since: 3/19/2004 From: United Kingdom |
|||
|
Posted - 3/19/2004 12:58:27 PM |
||||
| I bet using std::hash in conjunction with a gperf generated hash function would deliver a fairly solid performance when you know the characteristics of the data you're working on. Otherwise using a generic hash function seems sensible. It's true on the other hand that std::hash is not part of the standard and varies from implementation to implementation. |
||||
|
||||
|
evillive2 Member since: 12/13/2002 From: Chicago, IL, United States |
|||
|
Posted - 3/23/2004 5:16:49 PM |
||||
| I have used hash tables before reading this article mainly from my experiences with old text based MUDs but never thought of using one that indexed values based on strings. I am still working out the explaination in the middle of that article about the table size and the multiplier and the significance of them being prime etc. but all in all I found the article to be very helpful. I could use a little help though on how the algorithm actually adds weight to the order of the string? Anyone? Anyway, thanks for the ideas Evillive2  E-Mail |
||||
|
||||
|
Vexorian Member since: 10/7/2005 From: Ciudad la paz, Bolivia |
|||
|
Posted - 10/17/2005 8:21:42 PM |
||||
| This article was very useful |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 12/12/2005 10:53:08 PM |
||||
| One of the most important issues raised in the article is the need to select a prime number such that it is "far away from a power of 2". The author failed to elaborate on this. To be more specific, prime numbers should be selected as close to the average of the two nearest powers of 2. For example: 2^4 = 16 2^5 = 32 The average of those two numbers is 24 ((16 + 32) / 2 = 24). The nearest prime numbers are 23 and 29. Since 23 is the closest value to the average, you would pick that one. 23 is a good hash table size for storage of a reasonable number of values (roughly 150 values is a good guesstimate of the limit before performance quickly degrades). |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 12/12/2005 11:08:45 PM |
||||
Quote: Why is that? There are many reasons I could think of too implement your own hash tables. For instance, does std::hash_map support quadratic probing? Can you implement a closed-hash-table with std::hash_map? Do you know the default behavior of std::hash_map? Can you build perfect hash-tables with std::hash_map? Nope, because it's not officially standard, and every compiler may have a different implementation of it. |
||||
|
||||
|
Roboguy Member since: 8/21/2004 From: Leawood, KS, United States |
|||
|
Posted - 12/12/2005 11:13:29 PM |
||||
Quote: First, it's a good learning experience. Second, std::hash_map is not standard. |
||||
|
||||
|
Shiv_Godi Member since: 1/9/2007 From: Bangalore |
|||
|
Posted - 1/10/2007 12:28:33 AM |
||||
| The code snippet in Enter function seems to be incomplete. Does this form a complete linked list, with pointer to the head being pointed by table[index]. /* put the new node at the head of the list at table [index] */ node->next = table [index]; table [index] = node; |
||||
|
||||
|
lonesock Member since: 2/12/2004 |
|||
|
Posted - 1/10/2007 12:50:32 AM |
||||
Quote: The whole prime number sized table is one way to do it. Using a good hash function can let you use power-of-two sized tables, where the modulus function becomes very quick "x & size_minus_one", and simple quadratic probing can probe the entire table of size N in exactly N tries. Google's hash map implementation uses this method, and is extremely quick (for the dense_hash_map). I use the power-of-two method myself, and it is very quick and simple to implement. lonesock Piranha are people too. www.lonesock.net SOIL: Simple OpenGL Image Library "The Core" iRiff "The Mummy" iRiff |
||||
|
||||
|
GuildBuilder Member since: 4/5/2008 From: Fort Collins, CO, United States |
|||
|
Posted - 4/29/2008 1:01:02 AM |
||||
| I implemented a hash table today, and it implements it with a hash table of link lists to handle values that hash to the same hash value. (Therefore the same hash index) That's english versus the term buckets or chaining. Hash Table |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
