[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Eric Blake
Subject: Re: [really patch] Re: HashMap putAll/putAllInternal bug
Date: Thu, 16 Oct 2003 06:42:35 -0600
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.4) Gecko/20030624

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]