RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Paul Sandoz]

I forgot to say please don't let this hold up getting the patch into TL. I think it more important to get the code in then iterate on it.

Paul.

On Jun 4, 2013, at 9:45 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:

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