On Fri, 13 Nov 1998, Leon Breedt wrote:
> i've been hearing a lot about hash tables used in conjunction with linked
> lists...can anyone give me a good description of how one is implemented?
> i know the reason for them (speed).
Hash tables are, from the point of view of interface, arrays indexed by
arbitary strings. Since it would too much space for a simplistic
implementation, they are implemented as indexed by a *hash function* of
the string. That function takes a string, and outputs a small number.
The difficulty begins with clashes: two string mapped to the same number.
In that case, a popular solution is to use "buckets": put in any cell
a linked list of (key, value) pairs.
--
Name ::= "Moshe Zadka", [For explanation of syntax, see]
page::="http://www.ma.huji.ac.il/~moshez"| [http:/www.w3.org/TR/xml-980210]
"http://www.geocities/TheTropics/Island/2932"
E-Mail::= "[EMAIL PROTECTED]"|"[EMAIL PROTECTED]"|"[EMAIL PROTECTED]"
