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