1

在实现 ip-lookup 结构时，我试图在类似 trie 的结构中维护一组键，允许我搜索键的“地板”（即小于或等于给定的最大键钥匙）。我决定使用 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]]

有没有什么干净的方法可以拥有相同的功能？为什么这种方法不公开？

4

1 回答 1

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

根据文档，这是非常有效的，因为它取决于树的最大密钥的位数。

编辑：根据下面的评论，上面的代码存在边界问题：headMap()返回其键严格低于给定键的地图视图。这意味着，即对于上面的示例，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"，不管是什么，如果它属于 trie，或者紧接在 之前的元素，如果在 trie 中不存在key，则总是返回。keykeykey

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

于 2015-09-12T14:21:02.433 回答