From ... From: Erik Naggum Subject: Re: hashtable w/o keys stored... Date: 1999/01/18 Message-ID: <3125682171162255@naggum.no>#1/1 X-Deja-AN: 434139953 References: <77g8fd$jfd@pravda.cc.gatech.edu> <77gh61$k3n@pravda.cc.gatech.edu> <7F6861BC8A65CC8B.F0645AE687214FDC.64E9F9773E5A7701@library-proxy.airnews.net> mail-copies-to: never Organization: Naggum Software; +47 8800 8879; http://www.naggum.no Newsgroups: comp.lang.lisp * "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. #: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.