Каков наилучший способ поиска префиксов в реализации карты?

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." ключ должен вернуть два значения.

Какую структуру данных в java следует использовать, поскольку реализация Trie DS недоступна. Следующее лучшее, что я мог придумать, было только LinkedHashMap

Answer 1

Есть другая карта, которая индексирует префикс. В частности, используйте Guava's 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 Trie является сжатой Trie. Вместо хранения всех данных по краям Trie (и имеющих пустые внутренние узлы) PATRICIA хранит данные в каждом узле. Это позволяет очень эффективно выполнять операции обхода, вставки, удаления, предшественника, преемника, префикса, диапазона и выбора (объекта). Все операции выполняются в худшем случае в O (K) времени, где K - количество бит в наибольшем элементе в дереве. На практике фактически выполняется время O (A (K)), где A (K) - среднее количество бит всех элементов в дереве.

Самое главное, что PATRICIA требует очень мало сравнений с ключами при выполнении любой операции. При выполнении поиска каждое сравнение (не более K из них, описанное выше) будет выполнять однобитовое сравнение с данным ключом, вместо сравнения всего ключа с другим ключом.

В частности, prefixMap(prefix) operation возвращает SortedMap вид со всеми записями, которые соответствуют данному префиксу.

Опять же, из документации:

Например, если Trie содержит 'Анна', 'АНАЭЛЬ', 'Analu', 'Andreas' 'Андреа', 'Андрес' и «Анатоля ', то поиск «И» вернет «Андреас», «Андреа» и «Андрес».