如果要对多个条目使用同一个键，则应考虑使用Google Guava的MultiMap。

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

< code>MultiMap接口的实现之一是< code>SortedSetMultimap,它在您的情况下可能非常有用。

这可能有点太具体了，无法存在于通用库中，但是可用于有效解决此问题的数据结构是阶统计树（即自平衡二叉搜索树（BST），其中每个节点存储根植于该节点的子树的大小）。

除了适当地增加和减少子树的大小之外，在这个树中插入和删除(我们可以将更新定义为删除，然后插入)看起来与常规BST完全一样。

为了获得第i个元素，我们从根开始，通过查看节点的数量，反复确定目标节点将位于哪个子子树中。

上述任何操作都需要O（log n）时间。

如果您能够以某种方式（例如使用相应的对象）对具有相同整数值的元素进行排序，则上述内容将按原样工作。如果它们不能排序，也可以让每个节点都是具有相同整数值的元素的集合（例如List），然后，我们跟踪每个子树中元素的数量（即每个节点的大小之和），而不是节点的数量。

注意:如果你找不到一个库或自平衡实现，最简单的方法可能是采用一个红黑树的工作实现，并修改它来跟踪大小。

如果您更喜欢简单：

如果您喜欢用O(n)获得第I个元素，每次更新用O(log n ),那么您可以像上面描述的那样，使用< code>TreeMap

如果你对 O（1） 获得第 i 个元素感到满意，但每次更新 O（n），你可以简单地使用排序的 ArrayList 并迭代以找到正确的元素并将其移动到正确的位置。更新可以优化为使用二进制搜索，但它仍将是 O（n）。