java8中的TreeMap与HashMap

Question

根据Java8中的这个链接，为了避免在map（HashMap， LinkedHashMap， and Converter tHashMap）中的冲突，使用平衡树来实现，而不是LinkedList。

那么，如果：

>

（TreeMap和其他映射（HashMap、LinkedHashMap和ConcurrentHashMap）都是使用自平衡树实现的，因为最坏情况下的可访问性是相同的

条目的排序我可以实现如下：

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);
        }
    });
}

除了排序和可访问性，TreeMap的其他属性是什么？

Answer 1

>

在jdk7和旧jdk中重新计算桶索引时大小

在jdk7的HasMap中放入这样的内容时，只有一个bucket。那么查找节点是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)

在jdk8中，当把这样的东西放到HasMap中时，只有一个bucket，但是实现的键是可比较的。然后查找节点是O（log（N）），但是如果i相同，则查找节点将回退到O（N）。

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

排序LinkedHashMap您可以改为创建TreeMap实例，因为Map.keySet（）返回无序集而不是列表，因此您无法通过排序其键对地图进行排序。

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