I
Ian Pilcher
Background:
I'm working on a Java program, and I need to associate some additional
data with a large number of objects. I do not have the freedom to
modify or wrap the existing object classes. Additionally, I don't want
to interfere with the garbage collection of the objects.
I've come to the conclusion that I need a "WeakIdentityHashMap," a data
structure which combines the features of an IdentityHashMap and a
WeakHashMap. After a couple of attempts to build such a thing on top of
one of the existing classes, I don't think that enough of the internals
are exposed, and I'm going to have to create my own hash table.
The question:
Sun's documentation states that they use a linear-probe hash table for
the IdentityHashMap; the GNU Classpath does the same thing. As far as I
can tell, the other hash table-based collections use chaining.
It seems to me that a linear-probe hash table is a bad idea if mappings
are going to be removed from the table very often. When searching for a
given key, the search must continue until the key itself is found or a
slot which has NEVER been occupied is found. (Finding a slot which is
CURRENTLY empty is not enough, since it may have been occupied when the
key being sought was inserted into the map.)
Anyone see a flaw in my reasoning?
Thanks!
I'm working on a Java program, and I need to associate some additional
data with a large number of objects. I do not have the freedom to
modify or wrap the existing object classes. Additionally, I don't want
to interfere with the garbage collection of the objects.
I've come to the conclusion that I need a "WeakIdentityHashMap," a data
structure which combines the features of an IdentityHashMap and a
WeakHashMap. After a couple of attempts to build such a thing on top of
one of the existing classes, I don't think that enough of the internals
are exposed, and I'm going to have to create my own hash table.
The question:
Sun's documentation states that they use a linear-probe hash table for
the IdentityHashMap; the GNU Classpath does the same thing. As far as I
can tell, the other hash table-based collections use chaining.
It seems to me that a linear-probe hash table is a bad idea if mappings
are going to be removed from the table very often. When searching for a
given key, the search must continue until the key itself is found or a
slot which has NEVER been occupied is found. (Finding a slot which is
CURRENTLY empty is not enough, since it may have been occupied when the
key being sought was inserted into the map.)
Anyone see a flaw in my reasoning?
Thanks!