什麼是在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'。