|
I have been using HASH Tables for many applications.
1. Keyword lookup for command line processing
2. Generic name lookup tables of names, etc.
3. Substitution for binary tree name lookup that do not require a minimum guaranteed lookup time
I like HASH tables because they are easy to implement,
but the key question is what HASH function does one use.
Here is one I use:
unsigned int HASH_Value( char *name )
{
unsigned long int hashval;
int i;
hashval = 0;
for( i = 0; i < HASH_MAX_NAME_SIZE; i++ )
{
if( name[i] == '\0' ) break;
hashval += name[i] * i + 1;
}
return( (unsigned int)(hashval)%HASH_MAX_TABLE_SIZE );
/* traditional hash function
for( hashval = 0; *name != '\0'; name++ ) hashval = *name + 31 * hashval;
return ( hashval % HASH_MAX_TABLE_SIZE );
*/
}
It works for me, what works for you?
Please ignore any typos. Just looking for discussion on the topic.
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
The important point is that there is no universal "best" hash function. What makes a "good" hash (i.e. minimal collisions, not too costly to compute) depends very much on the nature of the data you are hashing. A good hash for peoples' full names may not do too well on their SSNs or phone numbers for example. And of course, the size of your hash table has a huge influence on performance. There are lots of good discussions (and some not so good) to be found if you search things like "best hash function".
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Thanx for quick response.
This is a good start.
Agreed:
"No universal "best" hash function"
"Minimize collisions"
"lots of discussions on "best hash function", etc
"What is nature of the data to be hashed?", etc
However, I suspect that
google uses proprietary hashing techniques
caching searches for future searches, "who knows",
collision mitigation,
daisy chaining (nested hash tables, etc. my terminology)
I suspect this subject maybe a lot deeper than the search for the standard "best hash function".
hence my proposal for a discussion. It may come to nothing, but it's out there.
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
After searching for a good hash for strings, I settled on the following:
uint32_t string_hash(const char* s)
{
uint64_t hash = 0;
auto size = strlen(s);
for(size_t i = 0; i < size; ++i)
{
hash = s[i] + (hash << 16) + (hash << 6) - hash;
}
return hash;
}And then you truncate the result to be a valid index into your hash table.
|
|
|
|
|
Worked the best using random generated names. Generated 100 hash values with only 2 collisions. not bad. I'll call it the GREG UTAS HASH
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
It's not mine! I found it somewhere on the net but don't recall where.
EDIT: Sorry for just saying "After searching...". Now I see how it can be misinterpreted.
|
|
|
|
|
I am giving you credit for funding it. I have 3 variations of hash functions and it's the best so far. One day I will post them, but too much going on here. Our weather here has gone frigid (for us) going into the teens.
Trying to protect plants and such.
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
I say: use libraries.
Unless, maybe, the domain is embedded with required extremely small footprint.
"If we don't change direction, we'll end up where we're going"
|
|
|
|
|
megaadam wrote: Unless, maybe, the domain is embedded with required extremely small footprint.
Welcome to my world.
GCS/GE d--(d) s-/+ a C+++ U+++ P-- L+@ E-- W+++ N+ o+ K- w+++ O? M-- V? PS+ PE Y+ PGP t+ 5? X R+++ tv-- b+(+++) DI+++ D++ G e++ h--- r+++ y+++* Weapons extension: ma- k++ F+2 X
The shortest horror story: On Error Resume Next
|
|
|
|
|
Use code tags.
jmaida wrote: what works for you?
Two of your examples use strings as the key. However the first would appear to be a fixed set. You could attempt to optimize based on that set. I have done so in the past to achieve zero collisions.
However micro optimizations based on guessing is a waste of time. Optimize based on profiling the application using realistic data. (My example above for zero collisions was in fact a waste of time.)
If I was using C or C++ I would use an existing library.
Your code example is mixing the hash value with the hash table which works for very limited cases but in general the two should be distinct (thus the library.)
Recalculating the hash every single time might not be ideal. But avoiding that means using a more complex structure.
jmaida wrote: Substitution for binary tree name lookup that do not require a minimum guaranteed lookup time
I do not understand that statement. Hash table and binary tree are distinct data structures. You can replace one with the other but there are considerations for both which your statement does not make clear to me. I do know that I replaced a complex tree (not a normal binary tree) with a hash table and gained about a 30% speed improvement so perhaps you are referring to something like that.
|
|
|
|
|
What I meant to say is
If one does not required minimum lookup time (it's my understanding though may be wrong, that a balanced binary tree can provide a minimum lookup time), then hashing is an inexpensive alternative.
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
|
Had not seen these link, so thanx, Quite interesting.
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
do not use C++
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
BernardIE5317 wrote: do not utilize any of these?
Just noticed the following in the list of what it supports. (There are some others.)
I can only hope no one is using those.
hash support for std::chrono::weekday
hash support for std::chrono::leap_second
|
|
|
|
|
🎵 Sweet Home Alabama 🎵[^]
What do you get when you cross a joke with a rhetorical question?
The metaphorical solid rear-end expulsions have impacted the metaphorical motorized bladed rotating air movement mechanism.
Do questions with multiple question marks annoy you???
|
|
|
|
|
Maybe this software developer hasn't even tried his software on any of the "I'm my own grandpa"-structures.
You'll find numerous variations of this story/song, e.g. Ray Stevens - "I'm My Own Grandpa"[^]. Wikipedia identifies Dwight Latham and Moe Jaffe as the ones responsible for the lyrics, but you can find the same story in numerous variations and on different tunes, usually referred to as a 'folk song'. So Latham and Jaffe didn't make it up from nothing; they just wrote down a song/story that was floating around.
25-30 years ago, I was checking out the genealogy programs available at that time. Several of them wouldn't even accept cousin marriage, and certainly not Abraham and Sarah (they had the same father, so they were half-siblings).
Some people are very eager to condemn reality, because they don't like it. Personally, I want the software I create to be able to handle reality, even in cases were I don't like it.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
Weather channel says it's currently -37C, feels like -45. The local airport shows a temp of -44C with a wind chill of -54. Not a day for T-shirt and shorts ...
"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown
|
|
|
|
|
Wow. 45F here right now. (Phila. area) That's supposed to be the high for the day as a polar front is roaring it's way across the state with 50+MPH winds. Ice and snow expected to arrive within the hour.
|
|
|
|
|
52F in N. FL.
"Ten men in the country could buy the world and ten million can’t buy enough to eat." Will Rogers
PartsBin an Electronics Part Organizer - Release Version 1.3.0 JaxCoder.com
Latest Article: SimpleWizardUpdate
|
|
|
|
|
We have only -25°C in some regions 
|
|
|
|
|
-37C, feels like -45.
please elaborate on
feels like
it is either -37 or -45 IMHO
|
|
|
|
|
Wind chill will cause a low temperature to feel lower. The feels like -45 is based on a temperature of -45 with no wind.
|
|
|
|
|
Salvatore Terress wrote: it is either -37 or -45 IMHO
IMHO it is not.
120F in Las Vegas is very different than 120F (or even 105F) in Tampa Bay.
And I would much rather be in -5F with a 20 mph wind in the mountains of Colorado than I would be for the same in NYC.
|
|
|
|
|
56F here in Phoenix, just finished a hike.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
