我需要一个与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),所以我选择了单词重新分类。
发布于 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;
发布于 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;
}
}
发布于 2020-12-29 22:14:31
我不确定我是否正确理解了您关于键冲突的观点。如果您的地图同时包含foo和foobar作为关键字,并且您希望搜索'startsWith( foo )‘,那么在我的理解中,应该返回同时对应于foo和foobar的值。通常,如果您使用键的前缀进行搜索,则永远不能保证映射将只包含满足该前缀的单个键。
如果您知道存储在map中的数据保证了这一点,那么您可以很好地读取从search方法返回的第一个值。
使用startsWith进行搜索的方法如下:
的值
示例代码:
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);
}
}
上面的也可以推广到非字符串键,只要
k
== p
https://stackoverflow.com/questions/52779823
复制相似问题