Java Hashtables

[J.Eddy]

When hashtables are sufficently long and are saved in virtual memory
how exectaly are then saved and retrieved? Is the array of keys stored
first with the offset of each object? And if known how does this
compare to the database retrieval mechanism (such as index files with
btree)?

 

[John C. Bollinger]

When hashtables are sufficently long and are saved in virtual memory
how exectaly are then saved and retrieved? Is the array of keys stored
first with the offset of each object? And if known how does this
compare to the database retrieval mechanism (such as index files with
btree)?

These are implementation details, therefore it is impossible to answer
the question without reference to a particular version of a particular
provider's JVM. It is unlikely that a method like the one you describe
is used by any implementation, however; typically if part of a process'
memory space is paged out, it must be paged back in to be used -- it is
not used directly from virtual memory. In any case, the layout in
virtual memory is normally the same as the layout in physical memory.
If a single object is too large to fit in physical memory at once then
you will probably see a lot of thrashing of the virtual memory system
when it is used.

Your question does suggest a possible misconception, however. Do note
that neither Hashtables nor any other kind of Java Collections contain
other objects -- they contain references to objects. This is true of
arrays as well. Perhaps you are getting confused about the difference
between memory being paged out and objects being serialized. The latter
does not accompany the former. When an object is serialized, all the
objects to which it holds references are serialized as well. The layout
of the resulting serialized representation is well-defined, but not
designed to be used in that form -- it is expected to be deserialized
first, which gets you back to the in-memory representation.


I hope that helps.

John Bollinger
(e-mail address removed)

 

[dhek bhun kho]

Hello J.E.


You need to look at the OS implementation of the virtual memory manager.
At least, if possible...

I don't think so, look at the output of and try to reverse engineer it:

<code>
$ javap java.util.HashMap
</code>

First of all I only see an array of HashMap.Entry[] objects. I do not see
an auxiliary structure to store the the keys. It seems very unlikely that
they have a b-tree. What kind of index is the most efficient for a
specific application is very specific to well... the application. If the
collection is fixed in size, a hash index should outperform a b-tree. But
you would need to test it.

These are implementation details, therefore it is impossible to answer
the question without reference to a particular version of a particular
provider's JVM. It is unlikely that a method like the one you describe

(Reference: SunVM)

One thing that is for certain is that you can only specify the minimum and
maximum sizes of memory available to the JVM. While the JVM is a Virtual
Machine by itself, it does not have its own mechanism for swapping out
memory that is infrequently accessed. Which would be a good and easy way
to minimize the memory footprint of the JVM.

The only way to get the JVM to swap itself out to virtual memory is when
-Xmx sets the maximum size to such a high level that the OS itself will
start swapping. This is an experimental observation, and I do not have any
publications on it. If you want to test it out yourself, code something
stupid like this:

<code>
public class MemoryBlasterXP
{
static LinkedList list=new LinkedList();
public static void main(String[] args)
{
for (; list.add(new Integer(1));
}
}
</code>

Run it with: java -Xms16M -Xmx1G MemoryBlasterXP. Note that this will only
work if the total amount of memory (RAM+swapfile) is greater that 1G. Also
note that your OS may not be able to hand such a large amount. Also note
that on Linux (Solaris too probably) the system administrator may have set
limits on the maximum amount of memory for a process. (ulimit -a to check
it out)

 

[Roedy Green]

First of all I only see an array of HashMap.Entry[] objects.

The Hashtable contains references to private Entry objects. The Entry
objects contain a reference to the key and the object and a cache of
the computed hash on the key, and a next pointer to deal with
collisions, keys hashing mod table length to the same slot.

So a Hashtable is basically an array of references. The Entry, key
and value objects can be scattered over all of virtual RAM.