views:

373

answers:

1

What does Java use as a default probing method for HashMap? Is it Linear? Chaining or something else?

+6  A: 

Looks like chaining to me. Code: (link)

...
724         /**
725          * Create new entry.
726          */
727         Entry(int h, K k, V v, Entry n) {
728             value = v;
729             next = n;
730             key = k;
731             hash = h;
732         }
...

...
795     void addEntry(int hash, K key, V value, int bucketIndex) {
796     Entry e = table[bucketIndex];
797         table[bucketIndex] = new Entry(hash, key, value, e);
...

That is, grab the entry at bucketIndex, then replace it with a new entry that has as its "next" field the entry that was already there (i.e. chain it).

dfrankow
your link is broken, but otherwise, good answer
luke
It has an extra colon at the end.
sk
HashMap and ConcurrentHashMap use chains. IdentityHashMap and the implementation of ThreadLocal use linear probing. Other JDK implementations may use different algorithms.
Tom Hawtin - tackline
Good comments, thanks.
dfrankow