java - Java 中的 StringStartsWithKeyMap<T>？ (如果键以 entry.key 开头则匹配)

Question

我需要一个 Map 将键与 startsWith() 进行比较:如果 key.startsWith(entry.getKey())，则键必须匹配.有没有现成的实现？

我发现:前缀树(trie)和基数树(紧凑的前缀树) 和PATRICIA 树。我找到了一些实现，但它们没有定义 navigableMap.floorEntry(key) 和 navigableMap.higherEntry(key) 等方法。

使用 startsWith() 进行键比较的棘手部分是冲突解决:如果映射同时包含“foo”和“foobar”的条目，那会发生什么？

使用 NavigableMap 很容易实现所需的功能，例如TreeMap，如果我们禁止键冲突，像这样:

private Map.Entry<String, T> findEntry(String key) {
    Map.Entry<String, T> entry = map.floorEntry(key);
    if (entry != null && key.startsWith(entry.getKey())) {
        return entry;
    }
    return null;
}

但是如果我们想支持冲突键，我们不能像上面代码那样依赖floorEntry():map.floorEntry("foobaz") 将找到 "foobar" 而不是 "foo" 的条目。这可以通过给“foobar”条目一个指向“foo”条目的指针来解决...看起来我们正在 TreeMap 之上重新发明紧凑前缀树>.

所以:

1) 是否存在将节点键与 startWith 进行比较的树的现有实现？

2) 是否有紧凑前缀树(基数树)的实现也实现了NavigableMap？

最好的情况是:

3) HashMap 的一些模拟支持 startsWith() 匹配

UPD

我意识到这是一个非常普遍的问题:重新分类。

给定一个房屋地址(好吧，写反了，Country-City-Street-HouseNumber 顺序)，找到相应的邮局(邮政编码)。

给定一个 IP 地址，找到相应的提供商。

在一般情况下，问题是:给定一个对象键，确定对象的类。 对象由 M 位的 key 标识，但只有前 N 位，N

由于这种排序的对象键对应一些分类(class-subclass-group-subgroup-id)，所以我选择了re-classification这个词。

Answer 1

据我所知，没有默认实现，但您可以轻松地自己编写:

    List<String> matchingKeys = map.keySet().stream().
            filter(key -> key.startsWith(prefix)).
            collect(Collectors.toList());

当您有匹配的键时，您可以调整要执行的操作。也许是这样的:

    for(Map.Entry<String, Object> entry : map.entrySet()) {
        if(matchingKeys.indexOf(entry.getKey()) != -1) {
            return entry;
        }
    }

或者另一种方法:

Optional<Entry<String, T>> matchingEntry = map.entrySet().stream().
        filter((k) -> k.getKey().startsWith(prefix)).findFirst();

if(matchingEntry.isPresent()) {
    return matchingEntry.get();
}

return null;