Hash algorithm

Can i have Some simple , effective ,easy to implement hash algorithm

Can you use Google?

Simplest

Code:

---

unsigned int simplest_hash(const char *str)
{
    return 0;
}

---

Most effective

gperf - GNU Project - Free Software Foundation (FSF)

Quote:

---

Originally Posted by bernt

Most effective

---

Under pretty restricted circumstances yeah, but thanks for that -- interesting.

More generally, "no collisions" is not a worthwhile goal for a general purpose hash table algorithm. The idea is very simple:

Code:

---

int hash (char *str, int tsz) {
    int i, r=0, len = strlen(str);
    for (i=0; i<len; i++) r += str[i];
    return r%tsz;
}

---

"tsz" is the table size. You can "double hash" by using (eg) a top level table in the form of a 100 element array, each of which is a further array of 12. If you then make the inner level an array of (eg) red-black binary trees, you end up with the most high performance kind of general purpose, random access data structure currently conceivable (if anyone has run across something better please tell!)

FNV-1a and CRC are two of my favourites that fit your criteria.

Quote:

---

Originally Posted by MK27

If you then make the inner level an array of (eg) red-black binary trees, you end up with the most high performance kind of general purpose, random access data structure currently conceivable (if anyone has run across something better please tell!)

---

I've considered that before, but I think making the hash entries to be trees is overkill. You might think about doing this if you are very space-constrained. Suppose you only had room for 256 entries in the hash table. That's equivalent to an extra tree depth of 8, in other words, you could do everything with a single tree and 8 additional comparisons. Unless comparisons are very costly, that's really not much overhead. You probably do more work computing the hash in the first place.

But if you know of an instance where the hybrid hash/tree thingie was a good tradeoff, I'd be interested to hear what that is.