Subject: Re: hashtable w/o keys stored...
From: Erik Naggum <>
Date: 1999/01/18
Newsgroups: comp.lang.lisp
Message-ID: <>

* "Marc Battyani" <>
| It's because to compute a hash value you have to process all the
| characters of your string.
| All this depends on the statistical repartition of your keys.   You can
| imagine a data set with 100 characters keys on where the first 5 are
| usually enough to differentiate them.  In that case It's likely that
| hashtables will be slower.

  in all likelihood, a hashing function is able to take advantage of the
  same property of the input, and but then somewhat more for collisions.

  the real difference, as I see it, is that tries will be able to take
  advantage of _any_ smallest set of differences, so if you have a bunch of
  people names starting with "Smith", the trie will effectively just move
  past the first 5 and use the next 5 characters, instead.  a hash function
  would have to be excessively intelligent to adapt the same way.

  SIGTHTBABW: a signal sent from Unix to its programmers at random
  intervals to make them remember that There Has To Be A Better Way.