Java: Gibt es einen Container, der HashMap und ArrayList effektiv kombiniert?

Question

Ich finde immer wieder ein Bedürfnis nach einem Container, der sowohl eine HashMap (für schnelle Suche nach einem Schlüsseltyp) als auch ein ArrayList (für schnellen Zugriff durch einen ganzzahligen Index) ist.

LinkedHashMap ist fast richtig, da es eine durchiterierbare Liste enthält, aber leider ist es eine verkettete Liste... das Abrufen des N-ten Elements erfordert das Durchlaufen von 1 bis N.

Gibt es einen Container-Typ, der diese Anforderungen erfüllt und den ich irgendwie übersehen habe? Was machen andere Leute, wenn sie auf dieselben Daten sowohl nach Schlüssel als auch nach Index zugreifen müssen?

Answer 1

Werfen Sie einen Blick auf Apache Commons LinkedMap.

Answer 2

Wenn Sie entfernen (in der Mitte) sowie den Zugriff durch Index und durch Schlüssel (was bedeutet, dass die Indizes ändern), sind Sie möglich aus dem Blick - ich denke, es kann einfach nicht eine Implementierung, die bietet sein O(1) für beide von remove (nach Index, Schlüssel oder Iterator) und get(index) . Aus diesem Grund haben wir beide LinkedList (mit iterator.remove() o remove(0) en O(1) ) und ArrayList (mit get(index) en O(1) ) in der Standard-API.

Sie können sowohl das Entfernen als auch das Indexieren in O(log n) wenn Sie eine Baumstruktur anstelle eines Arrays oder einer verknüpften Liste verwenden (was mit einem O(1)-Schlüssel-basierten Lesezugriff kombiniert werden könnte - die Ermittlung des Index für Ihr Schlüssel-Wert-Paar würde allerdings immer noch O(log n) erfordern).

Wenn Sie nichts entfernen wollen oder damit leben können, dass die folgenden Indizes nicht verschoben werden (d. h. remove(i) gleichbedeutend mit set(i, null) gibt es nichts, was verbietet, mit sowohl O(1) Index und Schlüssel Zugriff - in der Tat, dann der Index ist einfach ein zweiter Schlüssel hier, so dass Sie einfach eine HashMap und eine ArrayList (oder zwei HashMaps) dann, mit einem dünnen Wrapper kombinieren beide verwenden könnten.

---

Edita: Hier ist also eine Implementierung von ArrayHashMap wie im letzten Absatz oben beschrieben (unter Verwendung der Variante "teures Entfernen"). Sie implementiert die Schnittstelle IndexedMap unten. (Wenn Sie hier nicht kopieren und einfügen wollen, finden Sie beides auch in meinem Github-Konto die im Falle späterer Änderungen aktualisiert wird).

package de.fencing_game.paul.examples;

import java.util.*;

/**
 * A combination of ArrayList and HashMap which allows O(1) for read and
 * modifiying access by index and by key.
 * <p>
 *   Removal (either by key or by index) is O(n), though,
 *   as is indexed addition of a new Entry somewhere else than the end.
 *   (Adding at the end is in amortized O(1).)
 * </p>
 * <p>
 *   (The O(1) complexity for key based operations is under the condition
 *    "if the hashCode() method of the keys has a suitable distribution and
 *     takes constant time", as for any hash-based data structure.)
 * </p>
 * <p>
 *  This map allows null keys and values, but clients should think about
 *  avoiding using these, since some methods return null to show
 *  "no such mapping".
 * </p>
 * <p>
 *   This class is not thread-safe (like ArrayList and HashMap themselves).
 * </p>
 * <p>
 *  This class is inspired by the question
 *    <a href="http://stackoverflow.com/questions/5192706/java-is-there-a-container-which-effectively-combines-hashmap-and-arraylist">Is there a container which effectively combines HashMap and ArrayList?</a> on Stackoverflow.
 * </p>
 * @author Paulo Ebermann
 */
public class ArrayHashMap<K,V>
    extends AbstractMap<K,V>
    implements IndexedMap<K,V>
{

    /**
     * Our backing map.
     */
    private Map<K, SimpleEntry<K,V>> baseMap;
    /**
     * our backing list.
     */
    private List<SimpleEntry<K,V>> entries;

    /**
     * creates a new ArrayHashMap with default parameters.
     * (TODO: add more constructors which allow tuning.)
     */
    public ArrayHashMap() {
        this.baseMap = new HashMap<K,SimpleEntry<K,V>>();
        this.entries = new ArrayList<SimpleEntry<K,V>>();
    }

    /**
     * puts a new key-value mapping, or changes an existing one.
     *
     * If new, the mapping gets an index at the end (i.e. {@link #size()}
     * before it gets increased).
     *
     * This method runs in O(1) time for changing an existing value,
     *  amortized O(1) time for adding a new value.
     *
     * @return the old value, if such, else null.
     */
    public V put(K key, V value) {
        SimpleEntry<K,V> entry = baseMap.get(key);
        if(entry == null) {
            entry = new SimpleEntry<K,V>(key, value);
            baseMap.put(key, entry);
            entries.add(entry);
            return null;
        }
        return entry.setValue(value);
    }

    /**
     * retrieves the value for a key.
     *
     *   This method runs in O(1) time.
     *
     * @return null if there is no such mapping,
     *   else the value for the key.
     */
    public V get(Object key) {
        SimpleEntry<K,V> entry = baseMap.get(key);
        return entry == null ? null : entry.getValue();
    }

    /**
     * returns true if the given key is in the map.
     *
     *   This method runs in O(1) time.
     *
     */
    public boolean containsKey(Object key) {
        return baseMap.containsKey(key);
    }

    /**
     * removes a key from the map.
     *
     *   This method runs in O(n) time, n being the size of this map.
     *
     * @return the old value, if any.
     */
    public V remove(Object key) {
        SimpleEntry<K,V> entry = baseMap.remove(key);
        if(entry == null) {
            return null;
        }
        entries.remove(entry);
        return entry.getValue();
    }

    /**
     * returns a key by index.
     *
     *   This method runs in O(1) time.
     *
     */
    public K getKey(int index) {
        return entries.get(index).getKey();
    }

    /**
     * returns a value by index.
     *
     *   This method runs in O(1) time.
     *
     */
    public V getValue(int index) {
        return entries.get(index).getValue();
    }

    /**
     * Returns a set view of the keys of this map.
     *
     * This set view is ordered by the indexes.
     *
     * It supports removal by key or iterator in O(n) time.
     * Containment check runs in O(1).
     */
    public Set<K> keySet() {
        return new AbstractSet<K>() {
            public void clear() {
                entryList().clear();
            }

            public int size() {
                return entries.size();
            }

            public Iterator<K> iterator() {
                return keyList().iterator();
            }

            public boolean remove(Object key) {
                return keyList().remove(key);
            }

            public boolean contains(Object key) {
                return keyList().contains(key);
            }
        };
    }  // keySet()

    /**
     * Returns a set view of the entries of this map.
     *
     * This set view is ordered by the indexes.
     *
     * It supports removal by entry or iterator in O(n) time.
     *
     * It supports adding new entries at the end, if the key
     * is not already used in this map, in amortized O(1) time.
     *
     * Containment check runs in O(1).
     */
    public Set<Map.Entry<K,V>> entrySet() {
        return new AbstractSet<Map.Entry<K,V>>() {

            public void clear() {
                entryList().clear();
            }

            public int size() {
                return entries.size();
            }
            public Iterator<Map.Entry<K,V>> iterator() {
                return entryList().iterator();
            }
            public boolean add(Map.Entry<K,V> e) {
                return entryList().add(e);
            }

            public boolean contains(Object o) {
                return entryList().contains(o);
            }

            public boolean remove(Object o) {
                return entryList().remove(o);
            }

        };
    }  // entrySet()

    /**
     * Returns a list view of the entries of this map.
     *
     * This list view is ordered by the indexes.
     *
     * It supports removal by entry, iterator or sublist.clear in O(n) time.
     * (n being the length of the total list, not the sublist).
     *
     * It supports adding new entries at the end, if the key
     * is not already used in this map, in amortized O(1) time.
     *
     * Containment check runs in O(1).
     */
    public List<Map.Entry<K,V>> entryList() {
        return new AbstractList<Map.Entry<K,V>>() {
            public void clear() {
                baseMap.clear();
                entries.clear();
            }
            public Map.Entry<K,V> get(int index) {
                return entries.get(index);
            }
            public int size() {
                return entries.size();
            }
            public Map.Entry<K,V> remove(int index) {
                Map.Entry<K,V> e = entries.remove(index);
                baseMap.remove(e.getKey());
                return e;
            }
            public void add(int index, Map.Entry<K,V> newEntry) {
                K key = newEntry.getKey();
                SimpleEntry<K,V> clone = new SimpleEntry<K,V>(newEntry);
                if(baseMap.containsKey(key)) {
                    throw new IllegalArgumentException("duplicate key " +
                                                       key);
                }
                entries.add(index, clone);
                baseMap.put(key, clone);
            }

            public boolean contains(Object o) {
                if(o instanceof Map.Entry) {
                    SimpleEntry<K,V> inMap =
                        baseMap.get(((Map.Entry<?,?>)o).getKey());
                    return inMap != null &&
                        inMap.equals(o);
                }
                return false;
            }

            public boolean remove(Object o) {
                if (!(o instanceof Map.Entry)) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    SimpleEntry<K,V> inMap = baseMap.get(e.getKey());
                    if(inMap != null && inMap.equals(e)) {
                        entries.remove(inMap);
                        baseMap.remove(inMap.getKey());
                        return true;
                    }
                }
                return false;
            }

            protected void removeRange(int fromIndex, int toIndex) {
                List<SimpleEntry<K,V>> subList =
                    entries.subList(fromIndex, toIndex);
                for(SimpleEntry<K,V> entry : subList){
                    baseMap.remove(entry.getKey());
                }
                subList.clear();
            }

        };
    }   // entryList()

    /**
     * Returns a List view of the keys in this map.
     *
     * It allows index read access and key containment check in O(1).
     * Changing a key is not allowed.
     *
     * Removal by key, index, iterator or sublist.clear runs in O(n) time
     * (this removes the corresponding values, too).
     */
    public List<K> keyList() {
        return new AbstractList<K>() {
            public void clear() {
                entryList().clear();
            }
            public K get(int index) {
                return entries.get(index).getKey();
            }
            public int size() {
                return entries.size();
            }
            public K remove(int index) {
                Map.Entry<K,V> e = entries.remove(index);
                baseMap.remove(e.getKey());
                return e.getKey();
            }

            public boolean remove(Object key) {
                SimpleEntry<K,V> entry = baseMap.remove(key);
                if(entry == null) {
                    return false;
                }
                entries.remove(entry);
                return true;
            }

            public boolean contains(Object key) {
                return baseMap.containsKey(key);
            }

            protected void removeRange(int fromIndex, int toIndex) {
                entryList().subList(fromIndex, toIndex).clear();
            }
        };
    }  // keyList()

    /**
     * Returns a List view of the values in this map.
     *
     * It allows get and set by index in O(1) time (set changes the mapping).
     *
     * Removal by value, index, iterator or sublist.clear is possible
     * in O(n) time, this removes the corresponding keys too (only the first
     * key with this value for remove(value)).
     *
     * Containment check needs an iteration, thus O(n) time.
     */
    public List<V> values() {
        return new AbstractList<V>() {
            public int size() {
                return entries.size();
            }
            public void clear() {
                entryList().clear();
            }
            public V get(int index) {
                return entries.get(index).getValue();
            }
            public V set(int index, V newValue) {
                Map.Entry<K,V> e = entries.get(index);
                return e.setValue(newValue);
            }

            public V remove(int index) {
                Map.Entry<K,V> e = entries.remove(index);
                baseMap.remove(e.getKey());
                return e.getValue();
            }
            protected void removeRange(int fromIndex, int toIndex) {
                entryList().subList(fromIndex, toIndex).clear();
            }
        };
    }  // values()

    /**
     * an usage example method.
     */
    public static void main(String[] args) {
        IndexedMap<String,String> imap = new ArrayHashMap<String, String>();

        for(int i = 0; i < args.length-1; i+=2) {
            imap.put(args[i], args[i+1]);
        }
        System.out.println(imap.values());
        System.out.println(imap.keyList());
        System.out.println(imap.entryList());
        System.out.println(imap);
        System.out.println(imap.getKey(0));
        System.out.println(imap.getValue(0));

    }

}

Hier die Schnittstelle:

package de.fencing_game.paul.examples;

import java.util.*;

/**
 * A map which additionally to key-based access allows index-based access
 * to keys and values.
 * <p>
 * Inspired by the question <a href="http://stackoverflow.com/questions/5192706/java-is-there-a-container-which-effectively-combines-hashmap-and-arraylist">Is there a container which effectively combines HashMap and ArrayList?</a> on Stackoverflow.
 * </p>
 * @author Paulo Ebermann
 * @see ArrayHashMap
 */
public interface IndexedMap<K,V>
    extends Map<K,V>
{

    /**
     * returns a list view of the {@link #entrySet} of this Map.
     *
     * This list view supports removal of entries, if the map is mutable.
     *
     * It may also support indexed addition of new entries per the
     *  {@link List#add add} method - but this throws an
     *  {@link IllegalArgumentException} if the key is already used.
     */
    public List<Map.Entry<K,V>> entryList();

    /**
     * returns a list view of the {@link #keySet}.
     * 
     * This list view supports removal of keys (with the corresponding
     * values), but does not support addition of new keys.
     */
    public List<K> keyList();

    /**
     * returns a list view of values contained in this map.
     *
     * This list view supports removal of values (with the corresponding
     * keys), but does not support addition of new values.
     * It may support the {@link List#set set} operation to change the
     * value for a key.
     */
    public List<V> values();

    /**
     * Returns a value of this map by index.
     *
     * This is equivalent to
     *   {@ #values() values()}.{@link List#get get}{@code (index)}.
     */
    public V getValue(int index);

    /**
     * Returns a key of this map by index.
     *
     * This is equivalent to
     *   {@ #keyList keyList()}.{@link List#get get}{@code (index)}.
     */
    public K getKey(int index);

}

Answer 3

Warum behalten Sie einfach nicht die HashMap und verwenden dann hashMap.entrySet().toArray(); wie hier vorgeschlagen ?

Answer 4

Du könntest es selbst machen, aber hier ist eine Beispielimplementierung. Der entsprechende Google-Suchbegriff wäre "ArrayMap".

Ich bin mir nicht sicher, aber vielleicht hat Commons Collections oder Google Collections eine solche Map.

Bearbeitung:

Du kannst eine HashMap erstellen, die mit einer ArrayList implementiert ist. Sie würde wie LinkedHashMap funktionieren, wobei die Reihenfolge der Einfügung den Listenindex definiert. Dies würde schnellen Zugriff mit get(Index) (O(1)) und get(Name) (O(1)) ermöglichen, auch die Einfügung wäre O(1) (es sei denn, das Array muss erweitert werden), aber das Löschen wäre O(n), da das Löschen des ersten Elements erfordern würde, dass alle Indizes aktualisiert werden müssen.

Der Trick könnte durch eine Map gemacht werden, die intern eine Map für key-> index und dann eine ArrayList enthält.

get(Schlüssel) wäre dann (einfaches Beispiel ohne Fehlerüberprüfung):

list.get(keyIndexMap.get(schlüssel));