java - 使用 Java Collections 最大化按人名排序的数据结构的效率

Question

我需要一个由人名映射的数据结构，这意味着必须存储重复的键。我希望有 log(n) 次(最多)用于插入、删除和搜索。

理想情况下，我会有一个由唯一标识符映射的哈希表，该标识符将在插入时生成。通过这样做，我可以在恒定时间内插入。使用辅助有序平衡树，每个条目都是对哈希表中条目的引用，我将能够在对数时间内按名称搜索/删除，并在线性时间内打印所有条目，按名称排序。

有没有办法通过重用可用的集合在 Java 中做到这一点？或者至少是具有类似复杂性的解决方案...

在this question ，建议用一个Map来解决这个问题。但是据我了解，没有 Map 可以正确处理重复的键。

Answer 1

如果我对问题的理解正确，您需要一个 MultiMap。 Guava 中有一些实现和 Commons-Lang ，或者您可以使用例如自己推出一个 HashMap(或者 TreeMap，如果你怀疑你的 .hashCode() 实现太慢或太差，但我会首先进行基准测试)和一个 List 或 Set 实现作为值类型。

请注意，如果您想迭代基于名称顺序的值，您最好使用基于树的多重映射:如果名称已经是键，您的顺序将是无需执行任何其他操作。