Re: [really patch] Re: HashMap putAll/putAllInternal bug

[Eric Blake]

Here's an implementation idea that might work for an accurate size() for your 
case - maintain a single combined hash map which contains modified elements, 
with the submaps being views into the giant map, rather than maintaining the 
two submaps and having the combined map be a view.

Instead of key->value, you would have key->valueWrapper, where valueWrapper is 
something like:
class valueWrapper {
  private static final Object UNUSED = new Object();
  Object front; // UNUSED if not in front
  Object back; // UNUSED if not in back
}

The big map is maintains all three maps with independent size counts for the 
three views, and the small maps would just need to be custom implementations 
of AbstractMap that wrap the big map to provide the appropriate view, 
modifying their particular size count as appropriate.

Of course, having the small maps as wrappers of the big adds another layer of 
indirection, which may affect your performance, but at least size() would be 
O(1) for all three maps.


Stuart Ballard wrote:
> David Holmes wrote:
>
> Sure, I can calculate the size. The problem is that doing so requires a 
> full iteration over the elements of both sets: you can't just sum the 
> sizes, because you have to correctly account for elements that are in 
> both sets.
>
> That makes this "optimization" of just looping size() times actually a 
> pessimization, because you have to iterate over the elements twice 
> instead of once. I didn't provide a correct implementation of size() for 
> exactly this reason: I was afraid that it would get called a lot on the 
> assumption that it's fast, when it's not.
>
> As for why I need this implementation: it's being used for a language 
> interpreter and provides an implementation of nested scoping of 
> variables. Performance is important because it gets used a LOT. I wanted 
> to make sure that creating a new scope was cheap and didn't affect the 
> parent scope (it does caching to make sure that gets are cheap too). The 
> reasons why both the front and back scope need to be able to change 
> directly are complicated but (as far as I've found so far) unavoidable.
--
Someday, I might put a cute statement here.

Eric Blake             address@hidden