时间戳

首页 > 解决方案 > Java TreeMap 有两个键并且可以使用单个键？

java - Java TreeMap 有两个键并且可以使用单个键？

问题描述

我想要一个带有两个键的 Treemap，它可以通过单个键调用。

示例：key1 是字符串，key2 是整数，值是对象。

数据示例：

{('alice', 124221, obj1), ('bob', 241241, obj2), .... }
getByString('alice') ==> obj1
getByInt(124221) ==> obj1

注意：永远不需要同时使用两个键来获取对象。一个就够了

问题：

可以在一张地图中实现吗？如果是，是否可以保证通过任一键获取值具有 O(log n) 时间复杂度？

标签： javadata-structureshashmaptreemap

解决方案

正如@azurefrog 指出的那样，您想要的行为不是由 TreeMap 直接提供的，因此您需要某种包装类。这是一个例子；我已经将 TreeMaps 用于内部实现，但除非您想以某种方式使用更多方法的排序，否则最好使用 HashMap 代替，因为那时您将获得 O(1) 获取和放置操作，而不是 O(log n) .

import java.util.Map;
import java.util.TreeMap;

public class TwoKeysMap<K1 extends Comparable<K1>, K2 extends Comparable<K2>, V> {
    private static class Entry<K1 extends Comparable<K1>, K2 extends Comparable<K2>, V> {
        private final K1 k1;
        private final K2 k2;
        private final V v;

        private Entry(K1 k1, K2 k2, V v) {
            this.k1 = k1;
            this.k2 = k2;
            this.v = v;
        }
    }

    private final Map<K1, Entry<K1, K2, V>> map1 = new TreeMap<>();
    private final Map<K2, Entry<K1, K2, V>> map2 = new TreeMap<>();

    public V getByKey1(K1 k1) {
        Entry<K1, K2, V> e = map1.get(k1);
        return e != null ? e.v : null;
    }

    public V getByKey2(K2 k2) {
        Entry<K1, K2, V> e = map2.get(k2);
        return e != null ? e.v : null;
    }

    public void put(K1 k1, K2 k2, V v) {
        Entry<K1, K2, V> e = new Entry<>(k1, k2, v);
        map1.put(k1, e);
        map2.put(k2, e);
    }
}

用法：

> TwoKeysMap<String, Integer, Object> map = new TwoKeysMap<>();
> map.put("alice", 124221, "Object 1");
> map.put("bob", 241241, "Object 2");
> map.getByKey1("alice")
"Object 1" (Object)
> map.getByKey2(124221)
"Object 1" (Object)

请注意，Entry“get”和“put”并不严格需要内部类，但如果您想通过 key1 删除，则条目也需要存储 key2，以便您可以从两个映射中删除，反之亦然：

    public void removeByKey1(K1 k1) {
        Entry<K1, K2, V> e = map1.remove(k1);
        if(e != null) {
            map2.remove(e.k2);
        }
    }

    public void removeByKey2(K2 k2) {
        Entry<K1, K2, V> e = map2.remove(k2);
        if(e != null) {
            map1.remove(e.k1);
        }
    }

推荐阅读