问Java中的StringStartsWithKeyMap<T>？(匹配if key startsWith entry.key)
EN

Stack Overflow用户

提问于 2018-10-12 20:44:52

回答 3查看 347关注 0票数 2

我需要一个与startsWith()比较关键字的Map：如果是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)是否有紧凑的前缀树(基数树)的实现，也可以implements NavigableMap？

在最好的情况下，它将是：

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

更新

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

给定一个住宅地址(按照Country-City-Street- house Street顺序颠倒书写)，找到相应的邮局(邮政编码)。

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

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

因为这种类型的对象键对应于某种分类(class-subclass-group-subgroup-id)，所以我选择了单词重新分类。

java

android

algorithm

tree

回答 3

Stack Overflow用户

发布于 2018-10-12 21:24:49

据我所知，它没有默认的实现，但你可以很容易地自己编写：

    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;

票数 0

Stack Overflow用户

发布于 2018-10-13 00:04:19

这就是我目前使用的。它不支持冲突键(检测到冲突键时抛出RuntimeException )。

StringStartsWithKeyMap.java：

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * A map in which a key matches an entry if key.startsWith(entry.key)
 * @param <T>
 */
public class StringStartsWithKeyMap<T> implements Map<String, T> {
    TreeMap<String, T> map = new TreeMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
        return null != findEntry((String)key);
    }

    @Override
    public boolean containsValue(Object value) {
        return map.containsValue(value);
    }

    @Override
    public T get(Object key) {
        Entry<String, T> e = findEntry((String) key);
        return e == null ? null : e.getValue();
    }

    @Override
    public T put(String key, T value) {
        if (map.containsKey(key)) {
            return map.put(key, value);
        } else if (null == findEntry(key) && null == findHigherEntry(key)) {
            return map.put(key, value);
        }
        throw new RuntimeException("Conflicting keys: \""+key+"\" after "+findEntry(key)+" or before "+findHigherEntry(key));
    }

    @Override
    public T remove(Object key) {
        return map.remove(key);
    }

    @Override
    public void putAll(Map<? extends String, ? extends T> m) {
        m.forEach(this::put);
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public Set<String> keySet() {
        return map.keySet();
    }

    @Override
    public Collection<T> values() {
        return map.values();
    }

    @Override
    public Set<Entry<String, T>> entrySet() {
        return map.entrySet();
    }

    public StringStartsWithKeyMap<T> putSameValueFor(T value, String... keys) {
        for (String k : keys) {
            put(k, value);
        }
        return this;
    }
    public StringStartsWithKeyMap<T> putSameValueFor(T value, Iterable<String> keys) {
        for (String k : keys) {
            put(k, value);
        }
        return this;
    }
    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;
    }
    private Map.Entry<String, T> findHigherEntry(String key) {
        Map.Entry<String, T> entry = map.higherEntry(key);
        if (entry != null && entry.getKey().startsWith(key)) {
            return entry;
        }
        return null;
    }
}

以及测试结果：

StringStartsWithKeyMapTest.java：

import org.junit.Test;

import java.util.Arrays;
import java.util.Map;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

public class StringStartsWithKeyMapTest {

    @Test
    public void sizeTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.size(), is(3));
        assertThat(map0.size(), is(0));
    }

    @Test
    public void isEmptyTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.isEmpty(), is(false));
        assertThat(map0.isEmpty(), is(true));
    }

    @Test
    public void containsKeyTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.containsKey("foo"), is(true));
        assertThat(map3.containsKey("foobar"), is(true));
        assertThat(map3.containsKey("quux"), is(false));
        assertThat(map3.containsKey("quuxfoo"), is(false));
        assertThat(map0.containsKey("foo"), is(false));
    }

    @Test
    public void containsValueTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.containsValue(1), is(true));
        assertThat(map3.containsValue(1000), is(false));
        assertThat(map0.containsValue(1), is(false));
    }

    @Test
    public void getTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.get("foo"), is(1));
        assertThat(map3.get("foobar"), is(1));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baraboo"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("bah"), is((Integer) null));
        assertThat(map0.get("foo"), is((Integer) null));
        assertThat(map0.get(null), is((Integer) null));
    }

    @Test
    public void putTest() {
        Map<String, Integer> map3 = makeMap3();
        map3.put("qux",100);
        assertThat(map3.get("qux"), is(100));
        map3.put("foo",200);
        assertThat(map3.get("foo"), is(200));
        try {
            map3.put("foobar",6);
            assertThat(true, is(false));
        } catch (RuntimeException re) {
        }
        try {
            map3.put("fo",60);
            assertThat(true, is(false));
        } catch (RuntimeException re) {
        }
    }

    @Test
    public void removeTest() {
        Map<String, Integer> map3 = makeMap3();
        map3.remove("foo");
        map3.remove("baraboo");
        assertThat(map3.size(), is(2));
        assertThat(map3.get("foo"), is((Integer)null));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("baraboo"), is(2)); // need exact match for removal
    }

    @Test
    public void putAllTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map3a = makeMap3a();
        map3.putAll(map3a);
        assertThat(map3a.size(), is(3));
        assertThat(map3.size(), is(5));
        assertThat(map3.get("foo"), is(100));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("corge"), is(5));
        assertThat(map3.get("grault"), is(6));
        assertThat(map3.get("corgegrault"), is(5));
    }

    @Test
    public void clearTest() {
        Map<String, Integer> map3 = makeMap3();
        assertThat(map3.get("foo"), is(1));
        assertThat(map3.get("foobar"), is(1));
        map3.clear();
        assertThat(map3.get("foo"), is((Integer) null));
        assertThat(map3.get("foobar"), is((Integer) null));
        assertThat(map3.containsKey("foo"), is(false));
        assertThat(map3.containsValue(1), is(false));
        assertThat(map3.size(), is(0));
    }

    @Test
    public void keySetTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map0.keySet().isEmpty(), is(true));
        assertThat(map0.keySet().contains("foo"), is(false));
        assertThat(map3.keySet().size(), is(3));
        assertThat(map3.keySet().contains("foo"), is(true));
    }

    @Test
    public void valuesTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map0.values().isEmpty(), is(true));
        assertThat(map3.values().size(), is(3));
        assertThat(map3.values().contains(1), is(true));
        assertThat(map3.values().contains(2), is(true));
        assertThat(map3.values().contains(3), is(true));
    }

    @Test
    public void entrySetTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map0.entrySet().isEmpty(), is(true));
        assertThat(map3.entrySet().size(), is(3));
    }

    @Test
    public void putSameValueForTest() {
        StringStartsWithKeyMap<Integer> map3 = makeMap3();
        map3.putSameValueFor(400,"foo","corge","grault");
        assertThat(map3.size(), is(5));
        assertThat(map3.get("foo"), is(400));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("corge"), is(400));
        assertThat(map3.get("grault"), is(400));
        assertThat(map3.get("corgegrault"), is(400));
    }

    @Test
    public void putSameValueForTest2() {
        StringStartsWithKeyMap<Integer> map3 = makeMap3();
        map3.putSameValueFor(400, Arrays.asList("foo","corge","grault"));
        assertThat(map3.size(), is(5));
        assertThat(map3.get("foo"), is(400));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("corge"), is(400));
        assertThat(map3.get("grault"), is(400));
        assertThat(map3.get("corgegrault"), is(400));
    }

    private StringStartsWithKeyMap<Integer> makeMap3() {
        StringStartsWithKeyMap<Integer> res = new StringStartsWithKeyMap<>();
        res.put("foo",1);
        res.put("bar",2);
        res.put("baz",3);
        return res;
    }

    private StringStartsWithKeyMap<Integer> makeMap0() {
        StringStartsWithKeyMap<Integer> res = new StringStartsWithKeyMap<>();
        return res;
    }
    private StringStartsWithKeyMap<Integer> makeMap3a() {
        StringStartsWithKeyMap<Integer> res = new StringStartsWithKeyMap<>();
        res.put("foo",100);
        res.put("corge",5);
        res.put("grault",6);
        return res;
    }
}

票数 0

Stack Overflow用户

发布于 2020-12-29 22:14:31

我不确定我是否正确理解了您关于键冲突的观点。如果您的地图同时包含foo和foobar作为关键字，并且您希望搜索'startsWith( foo )‘，那么在我的理解中，应该返回同时对应于foo和foobar的值。通常，如果您使用键的前缀进行搜索，则永远不能保证映射将只包含满足该前缀的单个键。

如果您知道存储在map中的数据保证了这一点，那么您可以很好地读取从search方法返回的第一个值。

使用startsWith进行搜索的方法如下：

NavigableMap允许您在给定fromKey和toKey的情况下获取子图。要从中进行搜索的
前缀是必需的fromKey。可以从前缀计算toKey，这样我们就只得到那些满足前缀条件

的值

示例代码：

public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap<String, String> map = new TreeMap<>();
        map.put("abc", "value0");
        map.put("abcd", "value1");
        map.put("abcdef", "value2");
        map.put("abdfghij", "value3");
        map.put("abcefgh", "value4");
        map.put("abefijk", "value5");

        System.out.println("Values starting from abc");
        // expected output value0, value1, value2, value4

        searchByPrefix(map, "abc").stream().forEach(System.out::println);
    }

    private static Collection<String> searchByPrefix(NavigableMap<String, String> map, String begin) {
        String end = endKey(begin);
        // map.subMap(fromKey, fromInclusive, toKey, toInclusive), toKey should not be inclusive for our case
        return map.subMap(begin, true, end, false).values();
    }

    public static String endKey(String prefix) {
        return prefix.substring(0, prefix.length() - 1) + (char)(prefix.charAt(prefix.length() -1) + 1);
    }
}

上面的也可以推广到非字符串键，只要

键的世界是可排序的(事实上这是NavigableMap的主要要求，对于例如前缀)前缀，密钥组支持‘that

let’的概念，即按排序顺序前缀(K)K
AND

=映射中的所有关键字k其中K
AND(K)
p

== p

endKey >k对于K
AND中的所有关键字k‘其中k’是最小的关键字>中的所有关键字

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/52779823

复制

相似问题

问Java中的StringStartsWithKeyMap<T>？(匹配if key startsWith entry.key)
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java中的StringStartsWithKeyMap<T>？(匹配if key startsWith entry.key)EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java中的StringStartsWithKeyMap<T>？(匹配if key startsWith entry.key)
EN