RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Paul Sandoz]

Hi,

On Jun 4, 2013, at 1:34 AM, Brent Christian <brent.christian at oracle.com> wrote:

> Hi, Paul
> 
> If a HashMap is created via serialization or clone(), we don't check if the table needs resizing when adding entries, but still need to check if a bin should be converted to a TreeBin.  In this case, putForCreate() calls createEntry() directly, instead of addEntry().
> 

But putForCreate calculates "checkIfNeedTree":
1161         if (table[i] instanceof Entry) {
1162             int listSize = 0;
1163             Entry<K,V> e = (Entry<K,V>) table[i];
1164             for (; e != null; e = (Entry<K,V>)e.next) {
1165                 Object k;
1166                 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
1167                     e.value = value;
1168                     return;
1169                 }
1170                 listSize++;
1171             }
1172             // Didn't find, fall through to createEntry().
1173             // Check for conversion to TreeBin done via createEntry().
1174             checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1175         } else if (table[i] != null) {
...
1186 
1187         createEntry(hash, key, value, i, checkIfNeedTree);
1188     }

So the call to createEntry is just recalculating the same "listSize" value:

2232     void createEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {

...
2239         if (checkIfNeedTree) {
2240             int listSize = 0;
2241             for (e = (Entry<K,V>) table[bucketIndex]; e != null; e = (Entry<K,V>)e.next) {
2242                 listSize++;
2243                 if (listSize >= TreeBin.TREE_THRESHOLD) { // Convert to TreeBin
2244                     if (comparableClassFor(key) != null) {
2245                         TreeBin t = new TreeBin();
2246                         t.populate((Entry)table[bucketIndex]);
2247                         table[bucketIndex] = t;
2248                     }
2249                     break;
2250                 }
2251             }
2252         }
Paul.

> Thanks,
> -Brent
> 
> On 6/3/13 12:56 AM, Paul Sandoz wrote:
>> Hi Brent,
>> 
>> A minor thing: take it or leave it :-)
>> 
>> In HashMap:
>> 
>> 2207     void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
>> 2208         // assert key != null;
>> 2209         if ((size >= threshold) && (null != table[bucketIndex])) {
>> 2210             resize(2 * table.length);
>> 2211             hash = hash(key);
>> 2212             bucketIndex = indexFor(hash, table.length);
>> 2213         }
>> 2214         createEntry(hash, key, value, bucketIndex, checkIfNeedTree);
>> 2215     }
>> 
>> You could re-verify the bucket size if the table is resized rather
> than in createEntry, since that AFAICT is the only case where conditions
> after the call to addEntry might change.
>> 
>> Pau.
>>