为什么 Lucene 的倒排索引使用数组而不是哈希表？
Why does Lucene use arrays instead of hash tables for its inverted index?
我在看 Adrien Grand 的 talk on Lucene's index architecture，他指出 Lucene 使用排序数组来表示其倒排索引的字典部分。使用排序数组而不是哈希表（"classic" 倒排索引数据结构）背后的原因是什么？
哈希表提供 O(1) 的插入和访问，在我看来这对快速处理查询和合并索引段有很大帮助。另一方面，排序数组只能提供 O(logN) 访问和 (gasp) O(N) 插入，尽管合并 2 个排序数组与合并 2 个哈希表的复杂性相同。
我能想到的哈希表的唯一缺点是更大的内存占用（这确实可能是个问题）和缓存友好性较低（尽管查询排序数组等操作需要二进制搜索，这与缓存不友好一样).
怎么了？ Lucene 开发人员一定有充分的理由使用数组。这与可扩展性有关吗？磁盘读取速度？完全是别的东西？
好吧，我会在这里推测（可能应该是评论 - 但它会太长）。
HashMap 通常是一种具有搜索时间 O(1) 的快速查找结构 - 这意味着它是常数。但这是平均情况；因为（至少在 Java 中）HashMap 使用 TreeNodes - 搜索在那个桶内 O(logn)。即使我们认为他们的搜索复杂度是 O(1)，也不意味着它在时间上 相同 。这只是意味着它对于每个单独的数据结构都是不变的。
内存确实-我举个例子。简而言之，存储 15_000_000 个条目将需要 1GB 多一点的 RAM；排序后的数组可能更紧凑，尤其是因为它们可以容纳原语，而不是对象。
将条目放入 HashMap（通常）需要 所有 键重新散列，这可能会严重影响性能，因为它们所有人都可能不得不搬到不同的地方。
这里可能有一个额外的要点 - 在范围内搜索，这可能需要一些 TreeMap，数组在这里更适合。我正在考虑对索引进行分区（可能是他们在内部进行的）。
我和你有同样的想法 - 数组通常是连续的内存，可能更容易被 CPU.
最后一点：让我站在他们的立场上，我会先从 HashMap 开始……我相信他们的决定有令人信服的理由。我想知道他们是否有实际测试来证明这个选择。
我在想背后的原因。刚刚想到一个在文本搜索上下文中很重要的 use-case。我可能完全错了:)
为什么排序数组而不是字典？
是的，它在范围查询方面表现良好，但 IMO Lucene 主要是为文本搜索而构建的。现在假设您要搜索 prefix-based 个查询，例如：country:Ind*，您将需要扫描整个 HashMap/Dictionary。而如果您有一个排序数组，这将变为 log(n)。
由于我们有一个排序的数组，更新数组的效率很低。因此，在 Lucene 中段（倒排索引驻留在段中）是不可变的。
我在看 Adrien Grand 的 talk on Lucene's index architecture，他指出 Lucene 使用排序数组来表示其倒排索引的字典部分。使用排序数组而不是哈希表（"classic" 倒排索引数据结构）背后的原因是什么？
哈希表提供 O(1) 的插入和访问，在我看来这对快速处理查询和合并索引段有很大帮助。另一方面，排序数组只能提供 O(logN) 访问和 (gasp) O(N) 插入，尽管合并 2 个排序数组与合并 2 个哈希表的复杂性相同。
我能想到的哈希表的唯一缺点是更大的内存占用（这确实可能是个问题）和缓存友好性较低（尽管查询排序数组等操作需要二进制搜索，这与缓存不友好一样).
怎么了？ Lucene 开发人员一定有充分的理由使用数组。这与可扩展性有关吗？磁盘读取速度？完全是别的东西？
好吧，我会在这里推测（可能应该是评论 - 但它会太长）。
HashMap通常是一种具有搜索时间O(1)的快速查找结构 - 这意味着它是常数。但这是平均情况；因为（至少在 Java 中）HashMap使用TreeNodes- 搜索在那个桶内O(logn)。即使我们认为他们的搜索复杂度是O(1)，也不意味着它在时间上 相同 。这只是意味着它对于每个单独的数据结构都是不变的。内存确实-我举个例子
15_000_000个条目将需要1GB多一点的 RAM；排序后的数组可能更紧凑，尤其是因为它们可以容纳原语，而不是对象。将条目放入
HashMap（通常）需要 所有 键重新散列，这可能会严重影响性能，因为它们所有人都可能不得不搬到不同的地方。这里可能有一个额外的要点 - 在范围内搜索，这可能需要一些
TreeMap，数组在这里更适合。我正在考虑对索引进行分区（可能是他们在内部进行的）。我和你有同样的想法 - 数组通常是连续的内存，可能更容易被 CPU.
预取
最后一点：让我站在他们的立场上，我会先从
HashMap开始……我相信他们的决定有令人信服的理由。我想知道他们是否有实际测试来证明这个选择。
我在想背后的原因。刚刚想到一个在文本搜索上下文中很重要的 use-case。我可能完全错了:)
为什么排序数组而不是字典？
是的，它在范围查询方面表现良好，但 IMO Lucene 主要是为文本搜索而构建的。现在假设您要搜索 prefix-based 个查询，例如：country:Ind*，您将需要扫描整个 HashMap/Dictionary。而如果您有一个排序数组，这将变为 log(n)。
由于我们有一个排序的数组，更新数组的效率很低。因此，在 Lucene 中段（倒排索引驻留在段中）是不可变的。