给出另一个等效键对象的地图条目的当前键

Question

假设我有一个HashMap<K, V>和两个K类型的对象彼此相等但不是同一个对象，并且地图有一个关键k1的条目。

给定k2，我是否可以仅使用k1（无外部数据结构）的方法来获取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中的现有密钥，但它们都（似乎）将新的密钥对象传递给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 + '\'' +
                '}';
    }
}