Incidently, it is not the job of the Hashtable (in Java) to provide a
hash function. That is provided by the hashCode() method of the key.
Knuth's hash function is meant specifically for hashing based on memory
address -- something that a Hashtable could never know. It might be
useful, though for Object.hashCode() to use Knuth's algorithm.
-jaz
Lee Iverson wrote:
>
> In message <000201bdfbc6$428d6120$LocalHost@template> you write:
> > The hashtable knows this. It's not a direct mapping of hash code to value
> > ... it's hash code to a linked list of values with the same hash code.
> > Hashtables are normally implemented this way, actually, and in a normal
> > hashtable implementation you will have a lot of different hashcodes sharing
> > the same linked list.
>
> Fair enough, but how and where is the index into the hash table
> determined? If it's just a truncation (val%table_size) then you
> should see real problems with object locality causing hash table
> conflicts (i.e. linked lists with non-unit length). Knuth recommends
> a 32-bit unsigned multiply by 2654435769U (a very simple
> pseudo-randomizer) before the modulus to table size.
>
> -------------------------------------------------------------------------------
> Lee Iverson SRI International
> [EMAIL PROTECTED] 333 Ravenswood Ave., Menlo Park CA 94025
> http://www.ai.sri.com/~leei/ (650) 859-3307
