java - 为什么PatriciaTrie中无法访问 `floorEntry`等方法？

Question

在实现 ip-lookup 结构时，我试图在类似 trie 的结构中维护一组键，该结构允许我搜索键的“floor”(即小于或等于的最大键)到给定的键)。我决定使用 Apache Collections 4 PatriciaTrie但遗憾的是，我发现floorEntry并且相关方法不是public。我当前的“肮脏”解决方案是强制它们进行反射(在 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

为什么这些方法不公开，我不知道。 (也许是因为您可以使用通用 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()返回一个 map View ，其键严格 低于给定的键。这意味着，对于上面的示例，trie.headMap("b").lastKey() 将返回 "a"，而不是 "b"(根据需要)。

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

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

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

现在一切都按预期工作，因为 \uefff 是最高的 unicode 字符。实际上，搜索 key + "\uefff"，无论 key 是什么，如果它属于 trie 或元素，都将始终返回 key如果 key 不存在于 trie 中，则紧接在 key 之前。

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