1

我有一组具有两个属性的元素，名称（字符串，非唯一）和ID（整数，唯一）。所有具有相同名称的元素都存储在一起，并根据某些标准进行排序。

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

性能是对数据结构的最高要求。我认为多键、链接数据结构或混合哈希图/堆栈是理想的，但我知道不是。我考虑的一些选项是： - Guava 表（多个键），但它们没有推送/弹出行为。- LinkedHashMaps，但它们只有一个键。

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

有什么建议么？

谢谢大家

4

1 回答 1

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);
}

ALinkedHashMap只是跟踪键的插入顺序，并按该顺序进行迭代——与使用 a 相比，它不会提高性能HashMap。

于 2014-08-22T18:40:40.207 回答