Re: Hashtable ordering
Lew wrote:
On Aug 27, 1:54 pm, Lothar Kimmeringer <news200...@kimmeringer.de>
wrote:
Mike Schilling wrote:
Lothar Kimmeringer wrote:
Frank Cisco wrote:
What determines the ordering of an unsorted hashtable?
AFAIR the hashcode of the key modulo the size of the internal
array, the Map.Entry-instances are stored in.
And, within a hash chain, the order in which the key was added.
That's the implementation of HashMap. Possible that they changed
the internal logic of Hashtable as well when introducing HashMap,
but I'm not 100% sure (and too lazy to check now ;-)
That's the implementation of Hashtable, too.
Was there a reason to think otherwise?
In the current implementation of HashMap, entries are added to
hash chains in reverse order of their arrival -- that is, the most
recent entry is at the beginning of its chain, and the entries
further along the chain grow progressively older.
... but even that much is misleading, because the HashMap can
expand. The first time it expands, the entries in each old chain
are visited in order (that is, in reverse order of their insertion),
and are inserted in the expanded table's chains -- each insertion
at the front of the new chain, thus reversing the order of the old
chain (actually, of that subset of the old chain that lands in the
new chain's bucket). So now the chains run from older to newer,
instead of from newer to older.
... and then some still newer items get added, at the fronts of
their chains, so you've got the very newest entries at the front of
the chain, then older entries, eventually the oldest entry, and then
the entries start getting newer again -- a sort of V-shaped age
distribution. And then the HashMap expands again, all the chains
get reversed, new items go on the front and change it from V-shaped
to N-shaped, and then the map expands and the chains reverse and new
items form a W-shape, and ...
In short, the answer to the question you asked is "Yes."
--
Eric.Sosman@sun.com