为什么Lucene使用数组而不是哈希表作为其倒排索引？

我在看Adrien Grand的talk on Lucene's index architecture，他提出的一点是Lucene使用排序数组来表示其倒排索引的字典部分。背后使用排序数组而不是散列表（“经典”倒排索引数据结构）的原因是什么？为什么Lucene使用数组而不是哈希表作为其倒排索引？

哈希表提供O（1）插入和访问，这对我来说似乎对快速处理查询和合并索引段有很大帮助。另一方面，排序数组只能提供O（logN）访问和（gasp）O（N）插入，尽管合并2个排序数组与合并2个散列表具有相同的复杂度。

我能想到的散列表的唯一缺点是内存占用面积较大（这确实是一个问题）并且缓存友好性较差（尽管像查询排序数组这样的操作需要二进制搜索，就像缓存不友好一样）。

那又怎么样？ Lucene开发者必须有一个非常好的使用数组的理由。这与可伸缩性有关吗？磁盘读取速度？还有其他的东西吗？

优秀的问题！ – Eugene

@Ivan在这个答案中提供了Lucene不使用哈希表的多种原因：https：//stackoverflow.com/a/48053519/1697566 –

嗯，我会在这里推测（应该可能是一个评论 - 但它会太长）。

HashMap是在具有搜索时间O(1)一般快速查找结构 - 这意味着它是恒定的。但这是的平均情况;因为（至少在Java中）一个HashMap使用TreeNodes - 在该桶内搜索的是O(logn)。即使我们认为他们的搜索复杂度是O(1)，但这并不意味着它的时间明智的是相同的。这仅仅意味着它对于每个单独的数据结构都是不变的。
记忆确实 - 我会举一个例子here。总之，存储15_000_000的条目需要比RAM的1GB略多;排序的数组可能更加紧凑，特别是因为它们可以保存基元，而不是对象。在HashMap（通常）
把条目需要所有键重新散列这可能是一个显著的性能损失，因为它们都具有潜在的移动到不同的位置。
这里可能还有一点 - 在范围内搜索，这可能需要一些TreeMap，在这里数组更适合。我正在考虑对索引进行分区（可能是他们在内部执行）。
我和你有同样的想法 - 数组通常是连续的内存，可能更容易被CPU预取。
最后一点：把我放到他们的鞋子里，我会先从HashMap开始......我确信他们的决定有令人信服的理由。我想知道他们是否有实际的测试来证明这一选择。

2017-07-21 09:02:37 Eugene

感谢您的答案！我认为这也可能与Lucene必须推广到不仅仅是文本术语有关，而且散列任意术语可能相当受欢迎。但是我会看看是否可以做一点实验来看看'HashMap'和数组如何比较文本索引。 – CoconutFred

不要忘记他们的设置不变。 –

@AnthonyDeMeulemeester我不知道如何设置lucene，如零知识，thx为反馈 – Eugene

回答