what is under HashMap -- how data are stored?
I am curious how HashMap store data.
I know it has keys and entries. is the reference stored in the hashmap, or it is the object itself stored, for both keys and values? say, if I have <k1, sameValue> and <k2, sameValue>, will hashmap store two reference to the same 'sameValue' or store 'sameValue' twice?
would it be a good idea to crease 'two-dimentional' hashmap in order to use combinational keys? or there are better ideas?
Thanks!
> I am curious how HashMap store data.
>
> I know it has keys and entries. is the reference
> stored in the hashmap, or it is the object itself
No object is ever stored in a variable or accessed directly in Java. Everything is done through references. When you "put an object" into a Map or Collection, you're not copying the object; you're just providing a reference to the object. This is true for both keys and values in maps.
You can look at the source code for HashMap. It's in the src.zip file that's included with the JDK download.
> stored, for both keys and values? say, if I have
> <k1, sameValue> and <k2, sameValue>, will hashmap
> store two reference to the same 'sameValue' or store
> 'sameValue' twice?
See above. Multiple references to the same object.
> would it be a good idea to crease 'two-dimentional'
> hashmap in order to use combinational keys? or there
> are better ideas?
No idea what you're talking about here.
jverda at 2007-7-14 21:09:45 >
Thanks for the answer! That was what I guessed, but too
lazy to confirm it in books.
let me rephrase the last question:
there are multi-dimentional arrays, like object[ ][ ]. thus two
indices are used to access data stored. if in an application
one need to use two keys to id a value, say the milage
between two cities, I would guess I could use:
HashMap< city1, HashMap<city2, milage> >
it sounds awkward. is there any better way to do the same?
so that I can give a pair of cities in any order(<city1, city2>
or <city2, city1>) it will return me the same value.
Thanks!
> > would it be a good idea to crease
> 'two-dimentional'
> > hashmap in order to use combinational keys? or
> there
> > are better ideas?
>
> No idea what you're talking about here.
Define a class that encapsulates a pair of cities. Define equals and hashCode s.t. two instances of this class are equal if they both contain the same two cities. Use this class for the key.
jverda at 2007-7-14 21:09:45 >
> if in an application one need to use two keys to id a value, say the
> milage between two cities, I would guess I could use:
> HashMap< city1, HashMap<city2, milage>
> it sounds awkward. is there any better way to do the same?
Yes, have a look at quad-trees. For a small number of cities a simple
dense upper/lower triangular matrix (if there are no one way streets)
or a full dense matrix is fine but when you want to scale up to one or
two entire continents full of cities and roads, quad-trees are the way
to go (plus a bunch of heuristics, shortest path caches etc. on top of that).
kind regards,
Jos
JosAHa at 2007-7-14 21:09:45 >
