java - 在列表中高效查找

Question

我有一种情况，我正在用“TransactionEvent”填充 ArrayList。 TransactionEvent 有一个属性“事务 ID”。在大多数情况下，每个新事件的交易 ID 都大于前一个事件的 ID——但是，这并不能保证；即数据几乎已排序。

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

附加:

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

感谢任何帮助。

Answer 1

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

index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

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