为什么在 PatriciaTrie 中无法访问 `floorEntry` 和其他方法？

Question

在实现 ip-lookup 结构时，我试图在类似 trie 的结构中维护一组键，该结构允许我搜索键的 "floor"（即，最大的键小于或等于给定的键）。我决定使用 Apache Collections 4 PatriciaTrie but sadly, I found that the floorEntry 并且相关方法不是 public。我当前的 "dirty" 解决方案是用反射强制他们（在 Scala 中）：

val pt = new PatriciaTrie[String]()
val method = pt.getClass.getSuperclass.getDeclaredMethod("floorEntry", classOf[Object])
method.setAccessible(true)
// and then for retrieving the entry for floor(key) 
val entry = method.invoke(pt, key).asInstanceOf[Entry[String, String]]

是否有任何干净的方法来拥有相同的功能？为什么这些方法不公开？

Answer 1

为什么这些方法不是 public，我不知道。（也许是因为你可以用common Map API达到你想要的效果）。

这里有一个方法可以满足您的要求：

PatriciaTrie<String> trie = new PatriciaTrie<>();
trie.put("a", "a");
trie.put("b", "b");
trie.put("d", "d");

String floorKey = trie.headMap("d").lastKey(); // d

根据文档，这是非常有效的，因为它取决于 trie 中最大键的位数。

编辑： 根据下面的评论，上面的代码有一个边界问题：headMap() returns 地图的视图，其键是严格低于给定的密钥。这意味着，对于上面的示例，trie.headMap("b").lastKey() 将 return "a"，而不是 "b"（根据需要）。

为了解决这个边界问题，您可以使用以下技巧：

String cFloorKey = trie.headMap("c" + "\uefff").lastKey(); // b

String dFloorKey = trie.headMap("d" + "\uefff").lastKey(); // d

现在一切正常，因为 \uefff 是最高的 unicode 字符。实际上，搜索 key + "\uefff"，无论 key 是什么，如果它属于 trie，则总是 return key，或者 key 之前的元素，如果key 不在 trie 中。

现在，这个技巧适用于 String 键，但也可以扩展到其他类型。即对于 Integer 键，您可以搜索 key + 1，对于 Date 键，您可以添加 1 毫秒，等等

为什么在 PatriciaTrie 中无法访问 `floorEntry` 和其他方法？

Why `floorEntry` and other methods are not accessible in PatriciaTrie?

java

scala

reflection

apache-commons-collection

patricia-trie