Faster HashMap implementation (original) (raw)

Doug Lea dl at cs.oswego.edu
Tue Jun 30 22:09:04 UTC 2009

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.
  *

More information about the core-libs-dev mailing list