TreeMap vs HashMap in java8

Question

According to this link in Java 8, to avoid collisions in map (HashMap, LinkedHashMap, and ConcurrentHashMap) are implemented using balanced trees instead of LinkedList.

Then what is the difference if:

1. Both (TreeMap and Other Maps (HashMap, LinkedHashMap, and ConcurrentHashMap) got implemented using self-balancing-trees, as worst case accessibility is same.

2. Sorting of entry I can achieve as follows:

   public <K extends Comparable,V extends Comparable> LinkedHashMap<K,V> sortByKeys(LinkedHashMap<K,V> map){
       List<K> keys = new LinkedList<K>(map.keySet());
       Collections.sort(keys, (Comparator<? super K>) new Comparator<String>() {
           @Override
           public int compare(String first, String second) {                
               return first.compareTo(second);
           }
       });
   }
   

Apart from sorting and accessbility what are the other properties of TreeMap?

Answer 1

1. Both (TreeMap and Other Maps (HashMap, LinkedHashMap, and ConcurrentHashMap) got implemented using self-balancing-trees, as worst case accessibility is same.

   In jdk7 and old jdk recalculate bucket index when size >= threshold,and each bucket impelements as a linked list, but in jdk8 that is adjust the balancing-trees and each bucket impelemented as a Red-Black Tree.

   there is only one bucket when put something like this into HasMap in jdk7. then lookup node is O(N).

   class Foo{
      int hashCode(){
          return 0;
      }
   }
   Foo first=new Foo();
   Foo last=new Foo();
   map.put(first,"anything");
   map.put(last,"anything");
   map.get(last | first);// O(N)
   

   there is only one bucket when put something like this into HasMap in jdk8 but the key implemented Comparable. then lookup node is O(log(N)), however lookup node will be fallback to O(N) if i are identical.

   class Foo implements Comparable<Foo> {
       private int i;
   
       public Foo(int i) {
   
           this.i = i;
       }
   
       public int hashCode() {
           return 0;
       }
   
       @Override
       public int compareTo(Foo that) {
           return i - that.i;
       }
   }
   
   Foo first=new Foo(1);
   Foo last=new Foo(2);
   map.put(first,"anything");
   for(int i=2;i<threshold;i++)
     map.put(new Foo(i + 1), "anything");
   map.put(last,"anything");
   map.get(last | first);// O(log(N))
   

2. sort a LinkedHashMap you can create a TreeMap instance instead, since Map.keySet() returns unordered set not a list so you can't sort the map via sort its keys.

   public <K extends Comparable<? super K>, V> Map<K, V> sortByKeys(Map<K, V> map) {
    return new TreeMap<K, V>(map);
   }