[Tutor] Hashing

alan.gauld@bt.com alan.gauld@bt.com
Sat, 11 Aug 2001 19:33:55 +0100

> >>> hash((-1,))
> 1660579479
> >>> hash((-2,))
> 1660579479
> aren't these values supposed to be unique?

No hashing produces a spread of values over a range. When two 
or more items et the same hash value they go into a list and 
the lookup accesses the hash, if its single value returns it, 
if not it "does something" with the list. What itv does depends 
on the designer of the hash!

A good(ie readable) source of info on this is Kernighan & Pike's 
recent programming book - sorry forgotten the title for now...
Something like the Practice  of Programming.

The idea is that the total time looking up the hash then 
searching the list is shorter than traversing a single 
long list.

Alan G

PS I've just noticed that Danny has (as uisual) given a 
more complete answer. I'll send this anyway coz of the book