lynch@batcomputer.tn.cornell.edu (Tim Lynch) (12/04/90)
In article <22533:Dec321:54:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <9012031446.AA24102@bisco.kodak.COM> bilbo@bisco.kodak.COM (Charles Tryon) writes: > >Knuth spends a section on hashing. The presentation is good and has all >the basics, but doesn't go into the latest hot-shot methods. > >---Dan Thanks for the reference. Can someone recommend a book that does go into all the latest "hot-shot" methods? Tim Lynch
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/05/90)
In article <1990Dec4.142017.12806@batcomputer.tn.cornell.edu> lynch@batcomputer.tn.cornell.edu (Tim Lynch) writes: > Thanks for the reference. Can someone recommend a book that does go into > all the latest "hot-shot" methods? Have there been any fundamentally new hashing methods in the last twenty years? The only one I know of is Pearson's. What are you really looking for? There are lots of string functions that are both fast and, in practice, better than random hashing. These days I start from h = 5381, and set h = h << 5 + h + c mod any power of 2 for each new character c. Apparently Chris Torek prefers a multiplier of 31: h << 5 - h + c. These are reliable and extremely fast. You can make them even faster if you want to hash an entire string at once: just precompute powers of 31 or 33, etc. ---Dan