java在给定另一个等价键对象的情况下获取映射项的当前键

Question

假设我有一个HashMap<K, V>和两个类型为K的对象，它们彼此相等，但不是同一个对象，并且映射有一个键k1的条目

给定k2，我是否可以仅使用HashMap（无外部数据结构）中以恒定时间执行的方法（即O（1）时间复杂度）获取对k1的引用

代码：

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?
}

我希望使用Java8添加的各种方法之一，例如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

我觉得你在这里运气不好

<>我实际上认为一个^ {< CD8>}方法对API是有用的补充，您可以考虑提交一个增强请求。

Answer 2

我不知道您在内存使用方面有多受限，但是如果您可以使用LinkedHashMap而不是HashMap（LinkedHashMap使用额外的引用来保持插入顺序），那么您可以利用它的^{}方法：

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，由put和putAll（来自removeEldestEntry方法文档）自动调用removeEldestEntry方法：

This method is invoked by put and putAll after inserting a new entry into the map.

因此，我们现在需要做的就是实现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 + '\'' +
                '}';
    }
}