Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8346850

Clarify HashMap Documentation Regarding Treeification and Comparable Consistency

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P4 P4
    • None
    • None
    • core-libs

      A DESCRIPTION OF THE PROBLEM :
      The current documentation of HashMap does not explicitly mention that treeification (conversion of a bucket to a Red-Black Tree) relies on the compareTo method if keys implement Comparable. This can lead to unexpected behavior if the compareTo method is inconsistent with equals, even though such inconsistency violates the Comparable contract. The documentation should:

      Clearly state that during treeification, compareTo is used for ordering.
      Emphasize that compareTo must be consistent with equals for predictable behavior.
      By documenting this behavior, developers will better understand the interplay between Comparable and HashMap, avoiding misuse and debugging challenges.


      In the attached example, we can see that because of incorrect implementation of compareTo, the entries go missing in the map when we search for them after treeification.

      ACTUAL -
      /*
      Adding: Employee{id=1, name='Employee1'}. Size=1. Bucket:java.util.HashMap$Node
      Adding: Employee{id=2, name='Employee2'}. Size=2. Bucket:java.util.HashMap$Node
      Adding: Employee{id=3, name='Employee3'}. Size=3. Bucket:java.util.HashMap$Node
      Adding: Employee{id=4, name='Employee4'}. Size=4. Bucket:java.util.HashMap$Node
      Adding: Employee{id=5, name='Employee5'}. Size=5. Bucket:java.util.HashMap$Node
      Adding: Employee{id=6, name='Employee6'}. Size=6. Bucket:java.util.HashMap$Node
      Adding: Employee{id=7, name='Employee7'}. Size=7. Bucket:java.util.HashMap$Node
      Adding: Employee{id=8, name='Employee8'}. Size=8. Bucket:java.util.HashMap$Node
      Adding: Employee{id=9, name='Employee9'}. Size=9. Bucket:java.util.HashMap$TreeNode
      Adding: Employee{id=10, name='Employee10'}. Size=10. Bucket:java.util.HashMap$TreeNode


      ################################
      Print all the HashMap entries
      Employee{id=4, name='Employee4'} -> Address4
      Employee{id=1, name='Employee1'} -> Address1
      Employee{id=2, name='Employee2'} -> Address2
      Employee{id=3, name='Employee3'} -> Address3
      Employee{id=5, name='Employee5'} -> Address5
      Employee{id=6, name='Employee6'} -> Address6
      Employee{id=7, name='Employee7'} -> Address7
      Employee{id=8, name='Employee8'} -> Address8
      Employee{id=9, name='Employee9'} -> Address9
      Employee{id=10, name='Employee10'} -> Address10


      ################################
      Search all the HashMap entries
      Employee{id=1, name='Employee1'}-null
      Employee{id=2, name='Employee2'}-null
      Employee{id=3, name='Employee3'}-null
      Employee{id=4, name='Employee4'}-Address4
      Employee{id=5, name='Employee5'}-null
      Employee{id=6, name='Employee6'}-Address6
      Employee{id=7, name='Employee7'}-null
      Employee{id=8, name='Employee8'}-Address8
      Employee{id=9, name='Employee9'}-Address9
      Employee{id=10, name='Employee10'}-Address10


      ################################
      Remove all the HashMap entries
      Removing: Employee{id=1, name='Employee1'}. Size=10. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=2, name='Employee2'}. Size=10. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=3, name='Employee3'}. Size=10. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=4, name='Employee4'}. Size=9. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=5, name='Employee5'}. Size=8. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=6, name='Employee6'}. Size=7. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=7, name='Employee7'}. Size=6. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=8, name='Employee8'}. Size=5. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=9, name='Employee9'}. Size=4. Bucket:java.util.HashMap$TreeNode
      Removing: Employee{id=10, name='Employee10'}. Size=3. Bucket:java.util.HashMap$Node


      ################################
      Print all the HashMap entries. HashMap should be empty now.
      Employee{id=2, name='Employee2'} -> Address2
      Employee{id=1, name='Employee1'} -> Address1
      Employee{id=3, name='Employee3'} -> Address3


      ################################
      Search all the HashMap entries. No etries should be found because we removed everything.
      Employee{id=1, name='Employee1'}-Address1
      Employee{id=2, name='Employee2'}-Address2
      Employee{id=3, name='Employee3'}-Address3
      Employee{id=4, name='Employee4'}-null
      Employee{id=5, name='Employee5'}-null
      Employee{id=6, name='Employee6'}-null
      Employee{id=7, name='Employee7'}-null
      Employee{id=8, name='Employee8'}-null
      Employee{id=9, name='Employee9'}-null
      Employee{id=10, name='Employee10'}-null

      Process finished with exit code 0

       */

      ---------- BEGIN SOURCE ----------
      import java.lang.reflect.Field;
      import java.util.ArrayList;
      import java.util.Collections;
      import java.util.HashMap;
      import java.util.Map;

      class Employee implements Comparable<Employee> {
          private final int id;
          private final String name;

          public Employee(int id, String name) {
              this.id = id;
              this.name = name;
          }

          @Override
          public int hashCode() {
              // Force hash collision for all Employee objects
              return 42;
          }

          @Override
          public boolean equals(Object obj) {
              if (this == obj) return true;
              if (obj == null || getClass() != obj.getClass()) return false;
              Employee employee = (Employee) obj;
              return id == employee.id && name.equals(employee.name);
          }

          @Override
          public String toString() {
              return "Employee{id=" + id + ", name='" + name + "'}";
          }

          @Override
          public int compareTo(Employee o) {
              return 1; // This line brings the unpredictable behaviour.
          }
      }

      public class HashMapTreeifyExample {
          public static void main(String[] args) throws Exception {
              // Set initial capacity to at least 64 to prevent resizing
              Map<Employee, String> map = new HashMap<>(64);
              ArrayList<Employee> list = new ArrayList<>();
              // Add 10 Employee-Address pairs to the same bucket
              for (int i = 1; i <= 10; i++) {
                  Employee employee = new Employee(i, "Employee" + i);
                  String address = "Address" + i;
                  map.put(employee, address);
                  System.out.println("Adding: " + employee + ". Size=" + map.size() + ". "+ printTreeOrLinkedList(map));
                  list.add(employee);
              }

              System.out.println("\n\n################################");
              System.out.println("Print all the HashMap entries");
              map.forEach((key, value) -> {
                  System.out.println(key + " -> " + value);
              });

              System.out.println("\n\n################################");
              System.out.println("Search all the HashMap entries");
              for (Employee e : list) {
                  System.out.println(e + "-" + map.get(e));
              }

              System.out.println("\n\n################################");
              System.out.println("Remove all the HashMap entries");
              for(Employee employee :list){
                  map.remove(employee);
                  System.out.println("Removing: " + employee + ". Size=" + map.size() + ". "+ printTreeOrLinkedList(map));
              }

              System.out.println("\n\n################################");
              System.out.println("Print all the HashMap entries. HashMap should be empty now.");
              map.forEach((key, value) -> {
                  System.out.println(key + " -> " + value);
              });

              System.out.println("\n\n################################");
              System.out.println("Search all the HashMap entries. No etries should be found because we removed everything.");
              for (Employee e : list) {
                  System.out.println(e + "-" + map.get(e));
              }


          }

          static <K,V> String printTreeOrLinkedList(Map<K, V> map) throws Exception{
              String value = "Bucket:";
              Field tableField = HashMap.class.getDeclaredField("table");
              tableField.setAccessible(true);

              // Get the table array from the HashMap
              Object[] table = (Object[]) tableField.get(map);

              // Iterate over the table array
              for (Object bucket : table) {
                  if (bucket != null) {
                     value += bucket.getClass().getName();
                  }
              }
              return value;
          }
      }

            Unassigned Unassigned
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated: