Faster HashMap implementation

[Alex Yakovlev]

Doug,

On Wed, Jul 22, 2009 at 8:21 PM, Doug Lea<dl at cs.oswego.edu> wrote:

> On further evaluating it (among other possible HashMap replacements),
> I'm not convinced that they are enough better to commit.

> Size:    ...  9216  36864 147456 589824
> HashMap  ...    45     97    208    273
> V2       ...    40     78    188    257
Gain             +12%   +24%   +11%    +6%

More than 10% average improvement on big maps,
not worse on tiny maps, less memory usage - not a bad result imho

> Similarly for the mixed-side-array approach of Alex's Compact/Fast HashMap.

My version is a chained map, not an open map,
So concerns about locality and hit rates does not apply.
And with defragmentation there is not so many cache misses on collisions.

Alex