TreeMap的HashMap中VS在java8

-4

根據的Java 8this鏈接，以避免在地圖（HashMap, LinkedHashMap, and ConcurrentHashMap）碰撞使用平衡樹，而不是LinkedList實現。TreeMap的HashMap中VS在java8

那麼有什麼區別，如果：

兩者（TreeMap和其他地圖（HashMap, LinkedHashMap, and ConcurrentHashMap）使用自我平衡樹，爲最壞的情況下可訪問性是相同的時候實現

排序的entry我能實現如下：

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的其他屬性還有哪些？

來源

2017-04-03 Ramesh Papaganti

這不是計算器一個很好的問題，樹狀圖是當你需要時自動排序（例如字典），你似乎已經知道地圖。 –

您的觀點是什麼？在＃1中，你暗示沒有區別，因爲*最差情況*是相同的。對你而言，這是非常悲觀的，假設你總是有*最壞的情況*。在＃2中，你說你可以隨時在需要時對鍵進行排序，但排序很昂貴。一個'TreeMap'總是被排序的，所以如果'Map'不斷被修改，並且你不斷需要結果，那麼就會有巨大的性能差異。 'HashMap'性能更好（假設使用小數散列函數）並且不需要密鑰* * *。如果要求按鍵順序，'TreeMap'會更好。 – Andreas

...此外，無論鍵值是否在地圖中，「TreeMap」都可以爲您提供給定鍵值的相鄰鍵。一個'HashMap'不能做到這一點。排序後的列表不能做到這一點，除非您先浪費時間對列表進行排序，然後再執行二進制搜索*。 – Andreas

兩者（TreeMap和其他地圖（HashMap的，LinkedHashMap的，而ConcurrentHashMap的）得到了採用自平衡樹實現，最壞的情況下可訪問性是一樣的。

在JDK7老JDK recalculate bucket index時size >= threshold，並且每個桶impelements作爲linked list，但在jdk8是調整balancing-trees和impelemented作爲Red-Black Tree。

每個桶把這樣的事情的時候到HasMap在JDK7，然後查找節點只有一個桶是O(N)。當把這樣的事情到HasMap在jdk8但關鍵實施Comparable

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)

只有一個水桶。那麼查找節點是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); 
} 
```

來源

2017-04-03 19:07:56

@Holger請幫我看看這個答案是否正確？首先感謝。 –

當大小超過閾值（負載因素*大小）時，新的'HashMap'實現仍然調整/重新映射表。當每個桶的元素數量低於閾值時，它仍然使用鏈接列表（不要像類型名稱'LinkedList'那樣寫）。當超過閾值時，將會創建一個平衡樹，它首先使用哈希碼，因此，具有不同哈希碼的桶碰撞被整理出來，不管這些關鍵字是否可比較。只有真正相同的哈希碼，它會嘗試使用自然順序，如果有的話。 – Holger

a）'compareTo'返回零，但'equals'返回'false'（改變'last = new Foo（2）'爲'last = new Foo（1）'）或者b）而不是「Comparable」，在這種情況下，映射基本上會回退到帶有「O（n）」查找的鏈表。但是，必須強調的是，對於樹查找的「O（log（n））」，「n」是桶的數量，對於回退的「O（n）」，「n」是具有相同散列碼的對象，不具有'<' or '>'關係，所以'n'不等於'HashMap'的大小。 – Holger

TreeMap的HashMap中VS在java8

回答

相關問題