优化数据获取

Question

我有TreeMap private final TreeMap<Integer,SXSSFRow> rows = new TreeMap<>();

但是，我希望在恒定时间O(1)中从rows中检索数据，这样您就不必在每次迭代时从后面读取(log )。我能为这个做些什么？也许可以将数据从TreeMap传输到另一种数据结构，但它会有效吗？

Answer 1

如果您希望在固定时间内进行查找，即使在最坏的情况下，您需要的不是Map数据类型。

对于TreeMap，在所有情况下查找都是O(log )。

对于HashMap，查找值平均为O(1)，但在最坏情况下可达到O(n)。

如果您希望在所有情况下都查找O(1)，则需要一个数组，但是数组的大小可能变得太大，无法使用。如果您用键做了一些事情，比如模块或散列来缩小数组的大小，恭喜，您刚刚重新发明了HashMap (在最坏的情况下，由于碰撞而使用O(n)查找)。

顺便说一句，对于一个HashMap或一个数组，转换到另一个数据结构将花费O(n)，所以如果读取小于O(n)行，则效率不高。