爲什麼HashMap自動排序字符類型的鍵，雖然是一個無序的集合？

Question

爲了演示HashMap和TreeMap的區別，我創建了一個小代碼示例。

public class HashMapSimpleValueAutosort { 

    private static final char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 

    public static void main(String[] args) { 

     Map<Character, Integer> map = new HashMap<>(); 

     inverseAbc(map, "HashMap"); 

     map = new TreeMap<>(); 

     inverseAbc(map, "TreeMap"); 
    } 

    private static void inverseAbc(Map<Character, Integer> map, String desc) { 

     System.out.println(desc); 

     for (int i=25; i>=0; --i) { 
      map.put(alphabet[i], 26 - i); 
     } 
     System.out.println(map); 
    } 

} 

它能做什麼，是分配在地圖中使用的按鍵及其在字母表中的相應值的位置內按照相反的順序字母，使用HashMap和一個TreeMap方法。

儘管按照反轉順序插入鍵，但HashMap toString（）按升序輸出它們，就像TreeMap一樣。

這樣就出現在這裏的問題是：

是否toString（）方法的HashMap的方法，返回地圖的字符串表示形式之前，內部排序鍵？

編輯：

它接縫，這可能是一個JDK或基於IDE症狀，而不是僅限於的toString（）。

public class HashMapSimpleValueAutosort { 

    private static final char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 

    public static void main(String[] args) { 

     Map<Character, Integer> map = new HashMap<>(); 

     printEntries(map, "HashMap"); 

     map = new TreeMap<>(); 

     printEntries(map, "TreeMap"); 
    } 


    private static void printEntries(Map<Character, Integer> map, String desc) { 

     System.out.println(desc); 

     for (int i=25; i>=0; --i) { 
      map.put(alphabet[i], 26 - i); 
     } 

     System.out.print("{ "); 
     for (Map.Entry<Character, Integer> entry : map.entrySet()) { 
      System.out.printf("%c=%d,", entry.getKey(), entry.getValue()); 
     } 
     System.out.println(" }"); 
    } 

} 

在上面的示例中，我將鍵值對作爲條目打印出來。

Answer 1

這是一個奇怪的結果實施HashMap。

A HashMap必須決定在哪個散列桶中放置條目。它根據關鍵對象的hashCode()來決定。現在，hashCode()可以是任何整數。所以，它首先這樣做是爲了哈希碼：

(h = key.hashCode())^(h >>> 16) 

現在，你在這種情況下，關鍵是Character類型。 Character的hashCode是字符本身的值。 Java char是16位寬。所以將它向右移16位將會給你零。 Xoring它與零給你的原始價值 - char價值！

您選擇的值是連續的。這意味着它們恰好存儲在索引i，i + 1，i + 2處的散列表桶中......

這也恰好是條目集迭代器的順序，toString遍歷該表格：它連續地瀏覽表格。所以只要你沒有碰撞，對於Character碰巧是連續的，你會看到結果「排序」。

Answer 2

巧合的是，HashMap出現排序，這只是因爲這些值非常簡單纔出現。

如果更改爲String，雙字母，這樣hashCode()回報更復雜的數值，HashMap會出現更像是通常預期：訂單隨機出現（這是不大，但很可能會成爲）。

private static final String[] alphabet = {"aa","bb","cc","dd","ee","ff","gg","hh","ii","jj","kk","ll","mm", 
              "nn","oo","pp","qq","rr","ss","tt","uu","vv","ww","xx","yy","zz"}; 
public static void main(String[] args) { 
    Map<String, Integer> map = new HashMap<>(); 
    inverseAbc(map, "HashMap"); 
    map = new TreeMap<>(); 
    inverseAbc(map, "TreeMap"); 
} 
private static void inverseAbc(Map<String, Integer> map, String desc) { 
    System.out.println(desc); 
    for (int i=alphabet.length-1; i>=0; --i) { 
     map.put(alphabet[i], alphabet.length - i); 
    } 
    System.out.println(map); 
} 

輸出

HashMap 
{tt=7, zz=1, xx=3, vv=5, rr=9, pp=11, nn=13, ll=15, jj=17, hh=19, ff=21, dd=23, bb=25, ss=8, yy=2, ww=4, uu=6, qq=10, oo=12, mm=14, kk=16, ii=18, gg=20, ee=22, cc=24, aa=26} 
TreeMap 
{aa=26, bb=25, cc=24, dd=23, ee=22, ff=21, gg=20, hh=19, ii=18, jj=17, kk=16, ll=15, mm=14, nn=13, oo=12, pp=11, qq=10, rr=9, ss=8, tt=7, uu=6, vv=5, ww=4, xx=3, yy=2, zz=1} 

Answer 3

首先 -

• HashMap中沒有有序集合。
• TreeMap是有序集合。

所以，如果你期待，你會把值在一定的順序在HashMap，它會繼續這樣做則是錯誤的。它是無序的集合。另外，我跑了我的本地和HashMap產量無序和TreeMap奉命

就像上面說的，TreeMap是一個有序集合，它的作品，因爲當你把值TreeMap然後Comparator是對它們進行排序。請參閱下面的TreeMap.put實施。

雖然當你把值放在HashMap那麼就沒有這樣的排序。

public V put(K key, V value) { 
    Entry<K,V> t = root; 
    if (t == null) { 
     compare(key, key); // type (and possibly null) check 

     root = new Entry<>(key, value, null); 
     size = 1; 
     modCount++; 
     return null; 
    } 
    int cmp; 
    Entry<K,V> parent; 
    // split comparator and comparable paths 
    Comparator<? super K> cpr = comparator; 
    if (cpr != null) { 
     do { 
      parent = t; 
      cmp = cpr.compare(key, t.key); 
      if (cmp < 0) 
       t = t.left; 
      else if (cmp > 0) 
       t = t.right; 
      else 
       return t.setValue(value); 
     } while (t != null); 
    } 
    else { 
     if (key == null) 
      throw new NullPointerException(); 
     Comparable<? super K> k = (Comparable<? super K>) key; 
     do { 
      parent = t; 
      cmp = k.compareTo(t.key); 
      if (cmp < 0) 
       t = t.left; 
      else if (cmp > 0) 
       t = t.right; 
      else 
       return t.setValue(value); 
     } while (t != null); 
    } 
    Entry<K,V> e = new Entry<>(key, value, parent); 
    if (cmp < 0) 
     parent.left = e; 
    else 
     parent.right = e; 
    fixAfterInsertion(e); 
    size++; 
    modCount++; 
    return null; 
} 

---

預Java8 V/S Java8：

執行在Java8 HashMapput方法的比Java7或前不同，並且它在內部使用TreeNode和所有，並邏輯看起來很不一樣......這可能是原因。檢查Java8 HashMap.puthere