Subject: Re: hashtable w/o keys stored... From: Erik Naggum <erik@naggum.no> Date: 1999/01/18 Newsgroups: comp.lang.lisp Message-ID: <3125682171162255@naggum.no> * "Marc Battyani" <Marc_Battyani@csi.com> | 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. #:Erik -- SIGTHTBABW: a signal sent from Unix to its programmers at random intervals to make them remember that There Has To Be A Better Way.