Shrinking HashMaps (was Re: Proposal: Better HashMap.resize() when memory is tight)

[Peter Arrenbrecht]

Hi Martin

As per your hint, I've taken some time to think about shrinking
hashmaps. As you said, it is hard to find a general solution. I do, in
fact, believe that we should not even try. I'm asking myself: What are
the scenarios where people remove entries on a big scale from large
hashmaps? I for one always end up throwing the maps away, not removing
things from them. So since I suspect these scenarios to be rare, I
also suspect we won't find a large enough subset with compatible
requirements to warrant aiming for a general solution.

Instead, I propose to allow people to implement shrinking hashmaps
themselves on top of HashMap. This could be done by directly extending
HashMap, or by adding a new descendant, java.util.ShrinkableHashMap. I
have attempted the latter (in order to better show the changes) to see
what would be required.

The attached classes are just a sketch to invite further discussion.
There is ShrinkableHashMap, which would go into java.util so it can
properly access HashMap, and there are two demo user classes that
implement specific shrinking strategies. (Note: The whole thing is
untested and the demos are contrived. I'd like some feedback before I
take this further.)

Key points of ShrinkableHashMap:

	* Expose methods to adjust the capacity (several variants).
	* Expose methods to query the current capacity and load factor.
	* Expose override point to be notified when the capacity changes.
	* Expose override point to be notified when the size is reduced
(requires change to HashMap).
	* Use the fallback on tightResize() when super.resize() fails.

I chose to use tightResize() here because shrinking hashmaps is
something people might want to do especially when memory is low, so if
we can do it without needing additional memory, we should.

Since we're talking strategies here, another approach might be to use
explicit strategy interfaces so people could supply implementations
thereof to (Shrinkable)HashMap. I haven't explored this yet.

As you can see, this change would open up a fair bit of HashMap's
heretofore non-public interface. You would know better whether this is
warranted, i.e. whether there is sufficient demand for being able to
shrink hashmaps.

Is this a direction to follow, do you think? If not, what would you suggest?

-Peter


ps. Here's the necessary change to HashMap (required to properly
support removals through the key and entry sets):

@@ -591,7 +591,7 @@ public class HashMap<K,V>
                     table[i] = next;
                 else
                     prev.next = next;
-                e.recordRemoval(this);
+                removed(e);
                 return e;
             }
             prev = e;
@@ -624,7 +624,7 @@ public class HashMap<K,V>
                     table[i] = next;
                 else
                     prev.next = next;
-                e.recordRemoval(this);
+                removed(e);
                 return e;
             }
             prev = e;
@@ -632,6 +632,13 @@ public class HashMap<K,V>
         }

         return e;
+    }
+
+    /**
+     * Gives both map and entry descendants a chance to react to
entry removals.
+     */
+    void removed(Entry<K,V> e) {
+    	e.recordRemoval(this);
     }



On Nov 21, 2007 10:59 PM, Peter Arrenbrecht <peter.arrenbrecht at gmail.com> wrote:
> On Nov 21, 2007 9:58 PM, Peter Arrenbrecht <peter.arrenbrecht at gmail.com> wrote:
> > Hi Martin
> >
> > > I would prefer to see engineering work go into something
> > > like auto-reduction of the table array when many elements
> > > have been removed, but that's a hard problem.
> >
> > Would you care to elaborate? At first glance, this seems not
> > especially hard to me, in particular since tightResize() would be able
> > to switch to a smaller array without causing a short spike of needing
> > more memory first. But I'm sure I have overlooked something here.
>
> Ah, you don't want it to oscillate. Is that it?
> -peter
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ShrinkableHashMap.java
Type: text/x-java
Size: 4193 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20071122/e1823a80/ShrinkableHashMap.java>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AggressivelyShrinkingHashMapDescendant.java
Type: text/x-java
Size: 730 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20071122/e1823a80/AggressivelyShrinkingHashMapDescendant.java>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SlowlyShrinkingHashMapDescendant.java
Type: text/x-java
Size: 1030 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20071122/e1823a80/SlowlyShrinkingHashMapDescendant.java>