HashMap的key可以是可變的對象嗎？？？

2019-11-14 15:38:03

字體：大中小

來源：轉載

供稿：網友

　　大家都知道，HashMap的是key-value（鍵值對）組成的，這個key既可以是基本數據類型對象，如Integer，Float，同時也可以是自己編寫的對象，那么問題來了，這個作為key的對象是否能夠改變呢？或者說key能否是一個可變的對象？如果可以該HashMap會怎么樣？

可變對象

　　可變對象是指創建后自身狀態能改變的對象。換句話說，可變對象是該對象在創建后它的哈希值（由類的hashCode（）方法可以得出哈希值）可能被改變。

　　為了能直觀的看出哈希值的改變，下面編寫了一個類，同時重寫了該類的hashCode（）方法和它的equals（）方法【至于為什么要重寫equals方法可以看博客：http://www.companysz.com/0201zcr/p/4769108.html】，在查找和添加（put方法）的時候都會用到equals方法。

　　在下面的代碼中，對象MutableKey的鍵在創建時變量 i=10 j=20，哈希值是1291。

　　然后我們改變實例的變量值，該對象的鍵 i 和 j 從10和20分別改變成30和40。現在Key的哈希值已經變成1931。

　　顯然，這個對象的鍵在創建后發生了改變。所以類MutableKey是可變的。

　　讓我們看看下面的示例代碼：

public class MutableKey {    PRivate int i;    private int j;     public MutableKey(int i, int j) {        this.i = i;        this.j = j;    }     public final int getI() {        return i;    }     public final void setI(int i) {        this.i = i;    }     public final int getJ() {        return j;    }     public final void setJ(int j) {        this.j = j;    }     @Override    public int hashCode() {        final int prime = 31;        int result = 1;        result = prime * result + i;        result = prime * result + j;        return result;    }     @Override    public boolean equals(Object obj) {        if (this == obj) {            return true;        }        if (obj == null) {            return false;        }        if (!(obj instanceof MutableKey)) {            return false;        }        MutableKey other = (MutableKey) obj;        if (i != other.i) {            return false;        }        if (j != other.j) {            return false;        }        return true;    }}

測試：

public class MutableDemo {     public static void main(String[] args) {         // Object created        MutableKey key = new MutableKey(10, 20);        System.out.println("Hash code: " + key.hashCode());         // Object State is changed after object creation.        key.setI(30);        key.setJ(40);        System.out.println("Hash code: " + key.hashCode());    }}

結果:

Hash code: 1291

Hash code: 1931

　　只要MutableKey 對象的成員變量i或者j改變了，那么該對象的哈希值改變了，所以該對象是一個可變的對象。

HashMap如何存儲鍵值對

　　HashMap底層是使用Entry對象數組存儲的，而Entry是一個單項的鏈表。當調用一個put（）方法將一個鍵值對添加進來是，先使用hash（）函數獲取該對象的hash值，然后調用indexFor方法查找到該對象在數組中應該存儲的下標，假如該位置為空，就將value值插入，如果該下標出不為空，則要遍歷該下標上面的對象，使用equals方法進行判斷，如果遇到equals（）方法返回真的則進行替換，否則將其插入，源碼詳解可看：http://www.companysz.com/0201zcr/p/4769108.html。

　　查找時只需要查詢通過key值獲取獲取hash值，然后找到其下標，遍歷該下標下面的Entry對象即可查找到value。【具體看下面源碼及其解釋】

在HashMap中使用可變對象作為Key帶來的問題

　　如果HashMap Key的哈希值在存儲鍵值對后發生改變，Map可能再也查找不到這個Entry了。

public V get(Object key)   {    // 如果 key 是 null，調用 getForNullKey 取出對應的 value    if (key == null)        return getForNullKey();    // 根據該 key 的 hashCode 值計算它的 hash 碼   int hash = hash(key.hashCode());    // 直接取出 table 數組中指定索引處的值，   for (Entry<K,V> e = table[indexFor(hash, table.length)];        e != null;        // 搜索該 Entry 鏈的下一個 Entr        e = e.next)         // ①   {        Object k;        // 如果該 Entry 的 key 與被搜索 key 相同       if (e.hash == hash && ((k = e.key) == key            || key.equals(k)))            return e.value;    }    return null;   }

　　上面是HashMap的get（）方法源碼，通過上面我們可以知道，如果 HashMap 的每個 bucket 里只有一個 Entry 時，HashMap 可以根據索引、快速地取出該 bucket 里的 Entry；在發生“Hash 沖突”的情況下，單個 bucket 里存儲的不是一個 Entry，而是一個 Entry 鏈，系統只能必須按順序遍歷每個 Entry，直到找到想搜索的 Entry 為止——如果恰好要搜索的 Entry 位于該 Entry 鏈的最末端（該 Entry 是最早放入該 bucket 中），那系統必須循環到最后才能找到該元素。

　　同時我們也看到，判斷是否找到該對象，我們還需要判斷他的哈希值是否相同，假如哈希值不相同，根本就找不到我們要找的值。

　　如果Key對象是可變的，那么Key的哈希值就可能改變。在HashMap中可變對象作為Key會造成數據丟失。

　　下面的例子將會向你展示HashMap中有可變對象作為Key帶來的問題。

import java.util.HashMap;import java.util.Map; public class MutableDemo1 {     public static void main(String[] args) {         // HashMap        Map<MutableKey, String> map = new HashMap<>();         // Object created        MutableKey key = new MutableKey(10, 20);         // Insert entry.        map.put(key, "Robin");         // This line will print 'Robin'        System.out.println(map.get(key));         // Object State is changed after object creation.        // i.e. Object hash code will be changed.        key.setI(30);         // This line will print null as Map would be unable to retrieve the        // entry.        System.out.println(map.get(key));    }}

輸出：

Robinnull

如何解決

　　在HashMap中使用不可變對象。在HashMap中，使用String、Integer等不可變類型用作Key是非常明智的。　

　　我們也能定義屬于自己的不可變類。

　　如果可變對象在HashMap中被用作鍵，那就要小心在改變對象狀態的時候，不要改變它的哈希值了。我們只需要保證成員變量的改變能保證該對象的哈希值不變即可。

　　在下面的Employee示例類中，哈希值是用實例變量id來計算的。一旦Employee的對象被創建，id的值就不能再改變。只有name可以改變，但name不能用來計算哈希值。所以，一旦Employee對象被創建，它的哈希值不會改變。所以Employee在HashMap中用作Key是安全的。

import java.util.HashMap;import java.util.Map; public class MutableSafeKeyDemo {     public static void main(String[] args) {        Employee emp = new Employee(2);        emp.setName("Robin");         // Put object in HashMap.        Map<Employee, String> map = new HashMap<>();        map.put(emp, "Showbasky");         System.out.println(map.get(emp));         // Change Employee name. Change in 'name' has no effect        // on hash code.        emp.setName("Lily");        System.out.println(map.get(emp));    }} class Employee {    // It is specified while object creation.    // Cannot be changed once object is created. No setter for this field.    private int id;    private String name;     public Employee(final int id) {        this.id = id;    }     public final String getName() {        return name;    }     public final void setName(final String name) {        this.name = name;    }     public int getId() {        return id;    }     // Hash code depends only on 'id' which cannot be    // changed once object is created. So hash code will not change    // on object's state change    @Override    public int hashCode() {        final int prime = 31;        int result = 1;        result = prime * result + id;        return result;    }     @Override    public boolean equals(Object obj) {        if (this == obj)            return true;        if (obj == null)            return false;        if (getClass() != obj.getClass())            return false;        Employee other = (Employee) obj;        if (id != other.id)            return false;        return true;    }}