HashMap理解_ZenDei技術網路在線

hashCode() 和equals() 方法的重要性體現在什麼地方？ Java中的HashMap使用hashCode()和equals()方法設置值，根據鍵獲取值的時候也會用到這兩個方法。怎樣設置的值？ hashCode()獲得 hash值。而hash值用來確定hashmap中內部 Node ...

hashCode() 和equals() 方法的重要性體現在什麼地方？

Java中的HashMap使用hashCode()和equals()方法設置值，根據鍵獲取值的時候也會用到這兩個方法。

怎樣設置的值？

hashCode()獲得 hash值。而hash值用來確定hashmap中內部 Node數組的下標。
之後通過比較hash值與該下標處的key的hash值是不是相等，並使用equals方法比較兩個對象是否相同
- 如果hash和equals 都相等的話，說明兩個鍵是等價的
- 如果只有hash值相等的話，此時是 hash衝突了，需要用鏈地址法解決
- （這裡可以引出，如果只修改了equals方法的話而沒有修改hash方法，是不行的。兩個對象可能equals相等，但是由於沒有重寫hash方法，有可能導致hash不同。放入元素的key是hash1，取元素的key是hash2，雖然兩個key的equals重寫之後是相等的，但是key的hash沒有重寫，所以會取不出來）

來看源碼：

1 （前導）hash方法調用key的hashCode()方法（如果key的hashCode()方法沒有重寫的話，就是用的Object的hashCode()方法）

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

2 當往HashMap中存入一個值的時候，調用的其實是下麵這個方法。預先計算了hash(key)

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

3 比較 hash（通過hashCode()方法得到）是否相同和比較 equals()是否相等。依據情況存入值

   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // 如果數組為空的話，進行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 通過 （hash值和數組長度-1） 得到key的下標，
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果該下標處的值為空存入元素
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 通過比較hash值和判斷equals是否相等，如果相等覆蓋該值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                ...
            else {
                // HashMap採用的是鏈定址法
                for (int binCount = 0; ; ++binCount) {
                    // 一般情況下，如果鏈表的下一個是空的話，就插入到下一個中
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果鏈表中間存在相同的鍵，就覆蓋該值，並跳出迴圈
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

Java中的HashMap的工作原理是什麼？

HashMap採用的是 數組+鏈定址法 ，HashMap的內部中有一個叫做Node的內部類。HashMap其實就是維護了這個Node內部類數組 Node<K,V>[]。通過hashCode()方法得到hash址，然後通過和 數組長度-1 做位運算與存入數組的下標值。

如果該下標值處的位置沒有值，就填入該位置
如果有值了，就比較 hash值是否相同和 equals()是否相等，相等就可以覆蓋該值
否則將遞歸到該處的鏈表的最末尾（中間有相等的也可以覆蓋）

什麼是hashmap?

hashmap是一個散列表，存儲的內容是 鍵值對（key-value）映射，

HashMap 繼承於AbstractMap，實現了Map、Cloneable、java.io.Serializable介面。

hashmap 是線程不安全的，所以它的內部有一個 modCount 變數，表示修改次數。其它線程可能會修改hashmap的結構（刪除、增加），而此線程在迭代此時就會拋出 ConcurrentModifiedException。

初始容量大小是16，載入因數是0.75。也就是說在map到達12的時候，會擴容到兩倍

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

使用的是通過類似於數組下標的方式查找、刪除、更新元素等操作，非常高效。但是，當hash的衝突比較多的時候，那麼一個數組下標處有多個元素。此時java中的hashmap使用的是鏈定址法。就是數組+鏈表。發生hash衝突的時候，就在該下標處的鏈表末尾添加（如果中間有相等的鍵，就會覆蓋）

如何構造一致性哈希演算法。

？？？

Object作為HashMap的key的話，對Object有什麼要求嗎？

要求Object中hashcode不能變。

簡單的說就是 Object的equals方法和hashCode方法需要滿足一致性要求。而Object的equals方法是比較兩個對象的地址，而 hashCode則是 C/C++的原生方法（也是獲取記憶體地址值）。

兩者剛好對應，hashcode改變了就可能和equals對應不上。

解釋：

HashMap中是同時通過 hahsCode() 方法和 equals() 方法確定 key位置的

而 Object的 equals方法比較的是兩個變數的記憶體地址是否相同

    public boolean equals(Object obj) {
        return (this == obj);
    }

Object 的 hashCode是原生方法

    public native int hashCode();

hashCode方法的一致約定要求
（1）、在java應用的一次執行過程中，對於同一個對象的hashCode方法的多次調用，他們應該返回同樣的值（前提是該對象的信息沒有發生變化）；
（2）、對於兩個對象來說，如果使用equals方法比較返回true，那麼這兩個對象的hashCode值一定是相同的；
（3）對於兩個對象來說，如果使用equals方法返回false，那麼這兩個對象的hashCode值不要求一定不同（可以相同，可以不同），但是如果不同則可以提高應用的性能。
（4）、對於Object類來說，不同Object對象的hashCode值是不同的（Object類的hashcode值表示的是對象的地址）。

hashset 存的數是有序的嗎？

hashset 是無序的

為什麼HashMap的長度一定是 2 的次冪

通過源碼，我們可以發現每次擴容的時候，如果沒有超過最大容量的話。每次 newCap都會 << 1 (增加兩倍)

        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }

HashMap是通過 hash值和數組長度 - 1 的 &運算 得到數組下標的，這樣可以很好的將數據分散開。而每次擴容的時候。

而　(n - 1) & hash 這個操作如果在n為2的N次冪的情況下是等同於 hash % n 取餘數的值。

        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
         // 計算數組下標 i = 數組長度 & 哈希值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

重寫equals方法的時候，為什麼需要重寫hashCode方法

因為，如果不重寫hashCode方法。那麼在獲取對象的hash值的時候，會預設使用Object類的hashCode()方法。

而 HashMap()中需要通過 hashCode() 和 equals 方法設置鍵值對或者根據鍵獲取值。

只重寫了其中的一個的話，無法保證 hashCode方法的一致約定要求

在java應用的一次執行過程中，對於同一個對象的hashCode方法的多次調用，他們應該返回同樣的值（前提是該對象的信息沒有發生變化）；
對於兩個對象來說，如果使用equals方法比較返回true，那麼這兩個對象的hashCode值一定是相同的；
對於兩個對象來說，如果使用equals方法返回false，那麼這兩個對象的hashCode值不要求一定不同（可以相同，可以不同），但是如果不同則可以提高應用的性能。
對於Object類來說，不同Object對象的hashCode值是不同的（Object類的hashcode值表示的是對象的地址）。

參考資料： HashMap實現原理及源碼分析

HashMap理解