列表中的高效查找

Question

我有一种情况,我ArrayList用TransactionEvent"s " 填充. TransactionEvent有一个属性"事务ID".在大多数情况下,每个新事件的事务ID都大于先前事件的ID - 但是,这不能保证; 即数据几乎是分类的.

我的问题是:如何根据交易ID执行快速查询？我目前的想法是调用Collections.binarySearch(...),如果失败则执行线性搜索.但是,我注意到Javadoc声明binarySearch的结果是未定义的,因为数据是无序的,所以我可能不得不滚动自己的实现.

额外:

• 我曾尝试使用索引 - >事务ID的映射,但这种方法存在缺陷,因为无论何时更新/删除列表元素,我都必须重建整个映射; 即任何收益都会被删除.
• 这不是过早优化的情况:当包含大量行(100,000)时List,它是TableModel当前执行速度非常慢的基础.

任何帮助赞赏.

Answer 1

您可以通过在添加每个 ArrayList 时搜索插入点来保持 ArrayList 的排序TransactionEvent。 Collections.binarySearch返回

搜索关键字的索引（如果它包含在列表中）；否则，(-(插入点) - 1)。插入点定义为将键插入列表的点：大于键的第一个元素的索引，或 list.size()（如果列表中的所有元素都小于指定键）。请注意，这保证了当且仅当找到键时返回值>= 0。

搜索插入点后，您可以使用 ArrayList add(int index, Object element)方法，而不是像通常那样仅添加到列表末尾。这将使每次插入速度减慢一小部分，但它将使您能够使用二分搜索进行快速查找。