獲取給定另一個等效密鑰對象的地圖條目的當前密鑰

Question

假設我有一個HashMap<K, V>和類型K的兩個對象彼此相等但不是相同的對象，並且該地圖具有密鑰​​的條目。

鑑於k2，可以使用僅在HashMap（無外部數據結構）中執行的方法（即O（1）時間複雜度）獲得對​​的引用嗎？

在代碼：

K k1, k2; 
k1.equals(k2) // true 
k1.hashCode() == k2.hashCode() // true 
k1 == k2 // false 
myMap.put(k1, someValue); 

K existingKey = getExistingKey(myMap, k2); 
existingKey == k1 // true <- this is the goal 

<K> K getExistingKey(HashMap<K, V> map, K k) { 
    // What impl goes here? 
} 

我希望使用與Java 8中添加的各種方法中的一種，如compute()「嗅」在現有的拉姆達內的關鍵，但他們都（似乎）將新的密鑰對象傳遞給lambda，而不是現有密鑰。

通過entrySet()的迭代可以找到現有密鑰，但不是在固定時間內。

我可以使用Map<K, K>來存儲密鑰，我可以保持它的同步，但這並不回答這個問題。

Answer 1

您正在尋找的東西像

Map.Entry<K,V> getEntry(K key) 

起初我以爲它會很容易使HashMap自定義子類，返回這一點，因爲get(K key)只是

public V get(Object key) { 
    Node<K,V> e; 
    return (e = getNode(hash(key), key)) == null ? null : e.value; 
} 

其中Node工具Map.Entry。這看起來像：

public class MyHashMap<K,V> extends HashMap<K,V> 
{ 
    public MyHashMap() {} 
    // Other constructors as needed 

    public Map.Entry<K, V> getEntry(K key) 
    { 
     Map.Entry<K, V> e = getNode(hash(key),key); 
     return e; 
    } 
} 

不幸的是，getNode()和hash()都是包私有，因此不可見的子類。

下一步是把類java.util但這未能在Java中9

The package java.util conflicts with a package accessible from another module: java.base 

我覺得你的運氣了這裏。

我實際上認爲一個getEntry()方法將是API的一個有用的補充，你可以考慮提交一個增強請求。

Answer 2

我不知道如何限制你對於內存的使用，但如果你能使用LinkedHashMap代替HashMap（LinkedHashMap使用額外的引用，以保持插入順序），那麼你可以利用它的removeEldestEntry方法：

public class HackedMap<K, V> extends LinkedHashMap<K, V> { 

    K lastKey; 

    @Override 
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { 
     lastKey = eldest.getKey(); 
     return false; 
    } 

    K getLastKey() { 
     return lastKey; 
    } 
} 

我認爲這個代碼是不言自明的。我們保留對原始密鑰的參考，我們從removeEldestEntry方法的論點中獲取。 至於removeEldestEntry方法的返回值，它是false，所以我們不允許刪除最老的條目（畢竟，我們不希望該映射工作爲緩存）。

現在，具有共同的插入順序LinkedHashMap，所述removeEldestEntry方法被自動通過put和putAll稱爲（從removeEldestEntry方法文檔）：

此方法由PUT和的putAll插入一個新的條目之後調用進入地圖。

因此，所有我們現在需要做的就是實現你getExistingKey方法以這樣一種方式，它調用put不修改地圖，你可以做如下：

<K, V> K getExistingKey(HackedMap<K, V> map, K k) { 
    if (k == null) return null; 
    V v = map.get(k); 
    if (v == null) return null; 
    map.put(k, v); 
    return map.getLastKey(); 
} 

這樣做是因爲，當映射已包含映射到給定鍵的條目時，put方法將替換該值而不觸摸鍵。

我不知道我做過的空檢查，也許你需要改進。當然這HackedMap不支持併發訪問，但HashMap和LinkedHashMap也不支持。

您可以放心地使用HackedMap而不是HashMap。這是測試代碼：

Key k1 = new Key(10, "KEY 1"); 
Key k2 = new Key(10, "KEY 2"); 
Key k3 = new Key(10, "KEY 3"); 

HackedMap<Key, String> myMap = new HackedMap<>(); 

System.out.println(k1.equals(k2)); // true 
System.out.println(k1.equals(k3)); // true 
System.out.println(k2.equals(k3)); // true 

System.out.println(k1.hashCode() == k2.hashCode()); // true 
System.out.println(k1.hashCode() == k3.hashCode()); // true 
System.out.println(k2.hashCode() == k3.hashCode()); // true 

System.out.println(k1 == k2); // false 
System.out.println(k1 == k3); // false 
System.out.println(k2 == k3); // false 

myMap.put(k1, "k1 value"); 
System.out.println(myMap); // {Key{k=10, d='KEY 1'}=k1 value} 

myMap.put(k3, "k3 value"); // Key k1 (the one with its field d='KEY 1') remains in 
          // the map but value is now 'k3 value' instead of 'k1 value' 

System.out.println(myMap); // {Key{k=10, d='KEY 1'}=k3 value} 

Key existingKey = getExistingKey(myMap, k2); 

System.out.println(existingKey == k1); // true 
System.out.println(existingKey == k2); // false 
System.out.println(existingKey == k3); // false 

// Just to be sure 
System.out.println(myMap); // {Key{k=10, d='KEY 1'}=k3 value} 

---

這裏的Key類我用：

public class Key { 

    private final int k; 

    private final String d; 

    Key(int k, String d) { 
     this.k = k; 
     this.d = d; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 
     Key key1 = (Key) o; 
     return k == key1.k; 
    } 

    @Override 
    public int hashCode() { 
     return Objects.hash(k); 
    } 

    @Override 
    public String toString() { 
     return "Key{" + 
       "k=" + k + 
       ", d='" + d + '\'' + 
       '}'; 
    } 
}