Faster HashMap implementation

[Doug Lea]

Inspired by the combination of Alex's efforts and ongoing
work on concurrent caches, I put together a version
of HashMap (called HashMapV2 for now) with a snapshot at
   http://gee.cs.oswego.edu/dl/wwwtmp/HashMapV2.java
(This retains the openjdk GPL header etc.)

There are a few remaining things to consider
before taking this too seriously as a replacement.
I'll be out for 10 days starting tomorrow so probably
won't get a chance to do so soon.

It does seem to be the best plan of attack for
open-table scheme that people keep wanting (because of
fewer cache misses etc). I think it hits all of the
other issues and concerns I listed in mail a few weeks ago.
It looks very good on various performance tests, including some
I need to add/update in our "loops" tests.

(I wish the concurrent cache version for j.u.c
was in this good a state...)

Pasted below is some of the internal documentation:


      * Overview:
      *
      * The main table uses open-addressing, with [key, value] pairs in
      * alternating elements of "kvTable" array, plus a side-array
      * "hashes" holding hashCodes of keys (plus status bit).  If uses
      * hash preconditioning for first probe, and pseudo-random probing
      * from there. This gives a very good approximation of "uniform
      * hashing" (see for example CLR ch12) across various key types.
      *
      * Key removal sometimes requires replacing keys with ABSENT
      * markers.  We minimize need for these by recording (via UNIQUE
      * bit, see below) whether we can instead safely null out entry.
      * Markers are cleared out on put when there are too many of them,
      * as triggered by decrementing "threshold" on adding marker.
      *
      * In steady state, total footprint (ignoring non-dynamic fields)
      * for open tables is less than chained, even with the side array
      * of hashes. At default load factors, the total numbers words is
      * about:
      *                  steady state              initial
      *                  min     ave     max    (default cap)
      * Open:           4.00N   6.00N   8.00N    24
      * Chained:        7.33N   8.00N   8.67N    16
      *
      * To conserve space for unused maps, arrays are left unallocated
      * upon construction and nulled upon clearing, but with the target
      * allocation size stored in negated form in threshold field,
      * which conveniently requires a (size > threshold) check on
      * insertion anyway.  Additionally, to ensure that tables do not
      * fill up with deletion markers, the threshold is decremented
      * each time an element is replaced with a ABSENT marker.  This
      * forces resize occurring on next insertion to then replace table
      * with one without markers.
      *
      * Maps of size >= CEILING_LENGTH hold overflowing entries in a
      * ternary bitwise trie (see nested class HashTrie). This provides
      * bounded handling without running out of array indices, at the
      * price of about 4X average operation costs and 2.5X per-item
      * space overhead.  The trie is also used for Null keys, which
      * simplifies and speeds up most other table operations. Because
      * operations for Maps allowing nulls don't compose in simple ways
      * (null return values do not reliably mean absent), the HashTrie
      * class is not itself a Map, and so not useful outside this
      * class.
      *