Re: Hashed stringlist or binary searchtree or ????

From: Jens Gruschel (nospam_at_pegtop.net)
Date: 10/09/03 

Date: Thu, 9 Oct 2003 14:35:52 +0200

> If you have got a good hash function (that is, one that is fast and
produces
> a good distribution over the target values for the strings you want to
> store) this will always be much faster than a binary tree. But the hash
> function is the key so chose it wisely.

"Much faster"? Well "much" is very relative. It's faster, yes (except for
some special cases), but using trees is fast enough for most problems. Of
course you can measure the time for 1 million searches in 1 billion items,
but I doubt you will notice a difference in speed for every-day
applications. Even sorted lists and binary searching is quite fast - log2(1
billion) is about 30, and 30 comparisons take... well.. how many GHz have
you got?

I agree that probably nothing else is as fast as a hash table (and I use
them often), but for some problems other solutions are better, it really
depends. Hash tables for example need a capacity of about twice the items
you want to store to work efficient (and it shoud be a prime number). Most
implementations take care of this, so that's not a problem (and good
implementations only need a few bytes for empty items). But if you know how
hash tables / trees / lists etc work internally (and I really think every
programmer should know it), it's much easier for you to decide what to
choose. And as Thomas said, there are even different ways to build a hash
code, and different ways for probing (linear, quadratic etc), so some hash
tables might be better for your problem than others.

Jens

Relevant Pages

  • Re: Some comments on "super fast hash"
    ... SFH seems reasonably good and certainly is fast. ... > a hash, and SFH does not. ... The latest versions of each hash function which leverages this ... it must behave worse on other key sets. ...
    (comp.programming)
  • Re: hash table idea good or no good?
    ... 15 accesses for 25% and so on. ... implementations, like the hashmap from STL or CBFalconers ... Of course you need to use the same hash function for such a test. ...
    (comp.programming)
  • Some comments on "super fast hash"
    ... I've implemented a hash function here: ... SFH seems reasonably good and certainly is fast. ... quality of the hash function is not affected by the difference as far ... it must behave worse on other key sets. ...
    (comp.programming)
  • Re: Maximum String size in Java?
    ... >> compilation on any new target platform that does not already have ... Do you have a version of SFH posted with changes to use this file ... If they intend to use a hash ... benefit of 31/33 will sway me into using more than one hash function. ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... chain style and reprobe style are basically a wash. ... will be a smaller chance of encountering deleted entries before it. ... Once you sufficiently optimize a hash table, ... by computing of the hash function). ...
    (comp.programming)