java - 多键、链接哈希

Question

我有一组具有两个属性的元素:name(字符串，不唯一)和id(整数，唯一)。所有具有相同名称的元素都存储在一起，并根据某些标准排序。

插入只需完成一次，因为所有元素都事先已知，因此可以轻松完成。删除是根据顺序(第一个)或最终根据 id 完成的。读取值将是最常见(也是相关)的操作。

性能是数据结构的首要要求。我认为多键、链接数据结构或混合 HashMap /堆栈将是理想的，但我知道不是。我考虑的一些选择是: - Guava 表(多个键)，但它们没有推送/弹出行为。 - LinkedHashMap，但它们只有一个键。

当然，对于必须根据 id 删除元素的情况，我可以使用 LinkedHasMaps 并迭代删除。我只是想知道是否已经实现了高性能的东西。

有什么建议吗？

谢谢大家

Answer 1

使用 Map<String, TreeSet<Integer>> 。这将允许您在同一键下存储多个项目，并保持整数值排序。

<小时/>

这个想法是，您有一个到可以保存多个值的数据结构的键映射。插入name, value对，你可以这样做:

private Map<String, TreeSet<Integer>> map = new HashMap<>();

public void insert(String name, int value)
{
    if (! map.containsKey(name))
    {
        map.put(name, new TreeSet<Integer>());
    }
    map.get(name).add(value);
}

<小时/>

一个LinkedHashMap只是跟踪键的插入顺序，并按该顺序迭代——与使用 HashMap 相比，它不会提高性能。 .