什么是在Map实现中搜索前缀的最佳方式？

Question

LinkedHashMap.put("a.a1","11");   
LinkedHashMap.put("a.a12","12");   
LinkedHashMap.put("b.b1","13");   
LinkedHashMap.put("c.c1","14");   
LinkedHashMap.put("c.c1","15");   

搜索“a”。键应该返回两个值。

在Trie DS实现中我们应该使用java中的哪个数据结构不可用。下一个我能想到的最好的只有LinkedHashMap

Answer 1

有另一个按前缀索引的地图。特别是使用Guava的Multimap，它允许一个键映射到一个集合值。

Answer 2

我写了我自己的MapFilter。我主要将它用于属性文件。本质上，你选择一个通用的前缀 - 说"com."和筛选你的地图，选择所有与该前缀条目。

该解决方案的优雅来源于这样一个事实，即过滤过程将指向它的值的底层映射，因此它确实是一个过滤器。此外，过滤过滤的地图具有效率优势。

/** 
* Allows the filtering of maps by key prefix. 
* 
* Note that all access through the filter reference the underlying Map so 
* adding to a MapFilder results in additions to the Map. 
* 
* @author OldCurmudgeon 
* @param <T> 
*/ 
public class MapFilter<T> implements Map<String, T> { 
    // The enclosed map -- could also be a MapFilter. 
    final private Map<String, T> map; 
    // Use a TreeMap for predictable iteration order. 
    // Store Map.Entry to reflect changes down into the underlying map. 
    // The Key is the shortened string. The entry.key is the full string. 
    final private Map<String, Map.Entry<String, T>> entries = new TreeMap<>(); 
    // The prefix they are looking for in this map. 
    final private String prefix; 

    public MapFilter(Map<String, T> map, String prefix) { 
    // Store my backing map. 
    this.map = map; 
    // Record my prefix. 
    this.prefix = prefix; 
    // Build my entries. 
    rebuildEntries(); 
    } 

    public MapFilter(Map<String, T> map) { 
    this(map, ""); 
    } 

    private synchronized void rebuildEntries() { 
    // Start empty. 
    entries.clear(); 
    // Build my entry set. 
    for (Map.Entry<String, T> e : map.entrySet()) { 
     String key = e.getKey(); 
     // Retain each one that starts with the specified prefix. 
     if (key.startsWith(prefix)) { 
     // Key it on the remainder. 
     String k = key.substring(prefix.length()); 
     // Entries k always contains the LAST occurrence if there are multiples. 
     entries.put(k, e); 
     } 
    } 

    } 

    @Override 
    public String toString() { 
    return "MapFilter(" + prefix + ") of " + map + " containing " + entrySet(); 
    } 

    // Constructor from a properties file. 
    public MapFilter(Properties p, String prefix) { 
    // Properties extends HashTable<Object,Object> so it implements Map. 
    // I need Map<String,T> so I wrap it in a HashMap for simplicity. 
    // Java-8 breaks if we use diamond inference. 
    this(new HashMap<>((Map) p), prefix); 
    } 

    // Helper to fast filter the map. 
    public MapFilter<T> filter(String prefix) { 
    // Wrap me in a new filter. 
    return new MapFilter<>(this, prefix); 
    } 

    // Count my entries. 
    @Override 
    public int size() { 
    return entries.size(); 
    } 

    // Are we empty. 
    @Override 
    public boolean isEmpty() { 
    return entries.isEmpty(); 
    } 

    // Is this key in me? 
    @Override 
    public boolean containsKey(Object key) { 
    return entries.containsKey(key); 
    } 

    // Is this value in me. 
    @Override 
    public boolean containsValue(Object value) { 
    // Walk the values. 
    for (Map.Entry<String, T> e : entries.values()) { 
     if (value.equals(e.getValue())) { 
     // Its there! 
     return true; 
     } 
    } 
    return false; 
    } 

    // Get the referenced value - if present. 
    @Override 
    public T get(Object key) { 
    return get(key, null); 
    } 

    // Get the referenced value - if present. 
    public T get(Object key, T dflt) { 
    Map.Entry<String, T> e = entries.get((String) key); 
    return e != null ? e.getValue() : dflt; 
    } 

    // Add to the underlying map. 
    @Override 
    public T put(String key, T value) { 
    T old = null; 
    // Do I have an entry for it already? 
    Map.Entry<String, T> entry = entries.get(key); 
    // Was it already there? 
    if (entry != null) { 
     // Yes. Just update it. 
     old = entry.setValue(value); 
    } else { 
     // Add it to the map. 
     map.put(prefix + key, value); 
     // Rebuild. 
     rebuildEntries(); 
    } 
    return old; 
    } 

    // Get rid of that one. 
    @Override 
    public T remove(Object key) { 
    // Do I have an entry for it? 
    Map.Entry<String, T> entry = entries.get((String) key); 
    if (entry != null) { 
     entries.remove(key); 
     // Change the underlying map. 
     return map.remove(prefix + key); 
    } 
    return null; 
    } 

    // Add all of them. 
    @Override 
    public void putAll(Map<? extends String, ? extends T> m) { 
    for (Map.Entry<? extends String, ? extends T> e : m.entrySet()) { 
     put(e.getKey(), e.getValue()); 
    } 
    } 

    // Clear everything out. 
    @Override 
    public void clear() { 
    // Just remove mine. 
    // This does not clear the underlying map - perhaps it should remove the filtered entries. 
    for (String key : entries.keySet()) { 
     map.remove(prefix + key); 
    } 
    entries.clear(); 
    } 

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

    @Override 
    public Collection<T> values() { 
    // Roll them all out into a new ArrayList. 
    List<T> values = new ArrayList<>(); 
    for (Map.Entry<String, T> v : entries.values()) { 
     values.add(v.getValue()); 
    } 
    return values; 
    } 

    @Override 
    public Set<Map.Entry<String, T>> entrySet() { 
    // Roll them all out into a new TreeSet. 
    Set<Map.Entry<String, T>> entrySet = new TreeSet<>(); 
    for (Map.Entry<String, Map.Entry<String, T>> v : entries.entrySet()) { 
     entrySet.add(new Entry<>(v)); 
    } 
    return entrySet; 
    } 

    /** 
    * An entry. 
    * 
    * @param <T> 
    * 
    * The type of the value. 
    */ 
    private static class Entry<T> implements Map.Entry<String, T>, Comparable<Entry<T>> { 
    // Note that entry in the entry is an entry in the underlying map. 
    private final Map.Entry<String, Map.Entry<String, T>> entry; 

    Entry(Map.Entry<String, Map.Entry<String, T>> entry) { 
     this.entry = entry; 
    } 

    @Override 
    public String getKey() { 
     return entry.getKey(); 
    } 

    @Override 
    public T getValue() { 
     // Remember that the value is the entry in the underlying map. 
     return entry.getValue().getValue(); 
    } 

    @Override 
    public T setValue(T newValue) { 
     // Remember that the value is the entry in the underlying map. 
     return entry.getValue().setValue(newValue); 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (!(o instanceof Entry)) { 
     return false; 
     } 
     Entry e = (Entry) o; 
     return getKey().equals(e.getKey()) && getValue().equals(e.getValue()); 
    } 

    @Override 
    public int hashCode() { 
     return getKey().hashCode()^getValue().hashCode(); 
    } 

    @Override 
    public String toString() { 
     return getKey() + "=" + getValue(); 
    } 

    @Override 
    public int compareTo(Entry<T> o) { 
     return getKey().compareTo(o.getKey()); 
    } 

    } 

    // Simple tests. 
    public static void main(String[] args) { 
    String[] samples = { 
     "Some.For.Me", 
     "Some.For.You", 
     "Some.More", 
     "Yet.More"}; 
    Map map = new HashMap(); 
    for (String s : samples) { 
     map.put(s, s); 
    } 
    Map all = new MapFilter(map); 
    Map some = new MapFilter(map, "Some."); 
    Map someFor = new MapFilter(some, "For."); 
    System.out.println("All: " + all); 
    System.out.println("Some: " + some); 
    System.out.println("Some.For: " + someFor); 

    Properties props = new Properties(); 
    props.setProperty("namespace.prop1", "value1"); 
    props.setProperty("namespace.prop2", "value2"); 
    props.setProperty("namespace.iDontKnowThisNameAtCompileTime", "anothervalue"); 
    props.setProperty("someStuff.morestuff", "stuff"); 
    Map<String, String> filtered = new MapFilter(props, "namespace."); 
    System.out.println("namespace props " + filtered); 
    } 

} 

Answer 3

您正在寻找Apache Patricia Trie。这是您的用例的确切数据结构。

从自己的文件：

一个PATRICIA特里是一个压缩的特里。 PATRICIA将数据存储在每个节点中，而不是将所有数据存储在Trie的边缘（并且具有空的内部节点）。这允许非常高效的遍历，插入，删除，前导，后继，前缀，范围和选择（对象）操作。所有操作在O（K）时间内执行最差，其中K是树中最大项目中的位数。实际上，操作实际上需要O（A（K））时间，其中A（K）是树中所有项的平均比特数。

最重要的是，PATRICIA在进行任何操作时只需要很少的键比较。在执行查找时，每个比较（至多K个，如上所述）将对给定密钥执行单比特比较，而不是将整个密钥与另一个密钥进行比较。

特别是，prefixMap(prefix) operation返回一个SortedMap视图与所有与给定前缀匹配的条目。

再次，从文档：

例如，如果Trie树包含 '安娜'， 'Anael'， 'Analu'， '安德烈亚斯'， '安德烈'， '安德烈' 和“阿纳托利'，那么查找'And'会返回'Andreas'，'Andrea'和'Andres'。