RFR 8023463 Update HashMap and LinkedHashMap to use bins/buckets or trees (red/black)

[Paul Sandoz]

On Aug 26, 2013, at 11:13 PM, Remi Forax <forax at univ-mlv.fr> wrote:

> On 08/26/2013 10:10 PM, Paul Sandoz wrote:
>> On Aug 25, 2013, at 8:04 PM, Remi Forax <forax at univ-mlv.fr> wrote:
>> 
>>> On 08/21/2013 02:25 PM, Paul Sandoz wrote:
>>>> Hi,
>>>> 
>>>> Here are Doug's Linked/HashMap changes, discussed in a previous thread, as a webrev:
>>>> 
>>>>   http://cr.openjdk.java.net/~psandoz/tl/JDK-8023463-Linked-HashMap-bin-and-tree/webrev/
>>>> 
>>>> I also added some tests related to characteristics associated with fixing another bug.
>>>> 
>>>> Looking at the diffs will be tricky given there are so many changes.
>>> 
>>> The code can be simplified a little bit by using the diamond syntax,
>>> HashMap (lines: 919, 963, 1026, 1497, 1569) and
>>> LinkedHashMap (lines: 255, 264, 270, 278)
>>> 
>>> There are a bunch of @Override that are missing making the code harder than it should to read.
>>> 
>> Yes, i think this is because it sticks to the 166 style i suspect. Easy to change.
>> 

Note that j.u. classes are quite inconsistent in this respect to using diamonds and @Overrides. My preference is to do a sweeping change to all such code. I wonder if an IDE can automate that?

 
>>> In putVal, line 654, the null check (e != null) makes the method hard to read,
>>> at least I think a comment saying that it means that an existing node need to be altered is needed.
>>> 
>> e.g.:
>> 
>>             if (e != null) { // existing mapping for key
> 
> Yes, perfect.
> 
>> 
>> 
>>> And I still don't like the way the method clone() is implemented (the older implementation has the same issue),
>>> result should not be initialized to null and the catch clause should thow an InternalError or an AssertionError,
>>> 
>> You mean like this:
>> 
>>     public Object clone() {
>>         HashMap<K,V> result = null;
>>         try {
>>             result = (HashMap<K,V>)super.clone();
>>         } catch (CloneNotSupportedException e) {
>>             // this shouldn't happen, since we are Cloneable
>>             throw new InternalError(e);
>>         }
>>         result.reinitialize();
>>         result.putMapEntries(this, false);
>>         return result;
>>     }
> 
> Yes, and in that case, you don't need to initialize result to null (the first line), because when result is used
> (result.reinitialize()) result is already initialized by the return value of super.clone().
> 

Thanks.

Here is the latest patch that also includes updates for the above 2 comments and Mike's comments:

  http://cr.openjdk.java.net/~psandoz/tl/JDK-8023463-Linked-HashMap-bin-and-tree/webrev/

Paul.