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
2008-11-06 02:53:50
your link is broken, but otherwise, good answer
luke
2008-11-06 03:45:23
It has an extra colon at the end.
sk
2008-11-06 04:52:12
HashMap and ConcurrentHashMap use chains. IdentityHashMap and the implementation of ThreadLocal use linear probing. Other JDK implementations may use different algorithms.
Tom Hawtin - tackline
2008-11-06 16:07:17
Good comments, thanks.
dfrankow
2009-10-27 17:48:21