Multiple indexes for a Java Collection - most basi

Question

I'm looking for the most basic solution to create multiple indexes on a Java Collection.

Required functionality:

• When a Value is removed, all index entries associated with that value must be removed.
• Index lookup must be faster than linear search (at least as fast as a TreeMap).

Side conditions:

• No dependencies on large (like Lucene) libraries. No uncommon or not well tested libraries. No database.
• A library like Apache Commons Collections etc. would be ok.
• Even better, if it works with JavaSE (6.0) alone.
• Edit: No self-implemented solution (thanks for the answers suggesting this - it's good to have them here for completeness, but I already have a solution very similar to Jay's) Whenever several people find out, that they implemented the same thing, this should be part of some common library.

Of course, I could write a class that manages multiple Maps myself (that's not hard, but it feels like reinventing the wheel). So I'd like to know, if it can be done without - while still getting a simple usage similar to using a single indexed java.util.Map.

Thanks, Chris

Update

It looks very much as if we haven't found anything. I like all your answers - the self developed versions, the links to database-like libraries.

Here's what I really want: To have the functionality in (a) Apache Commons Collections or (b) in Google Collections/Guava. Or maybe a very good alternative.

Do other people miss this functionality in these libraries, too? They do provide all sorts of things like MultiMaps, MulitKeyMaps, BidiMaps, ... I feel, it would fit in those libraries nicely - it could be called MultiIndexMap. What do you think?

Answer 1

If you want multiple indexes on your data, you can create and maintain multiple hash maps or use a library like Data Store:

https://github.com/jparams/data-store

Example:

Store<Person> store = new MemoryStore<>() ;
store.add(new Person(1, "Ed", 3));
store.add(new Person(2, "Fred", 7));
store.add(new Person(3, "Freda", 5));
store.index("name", Person::getName);
Person person = store.getFirst("name", "Ed");

With data store you can create case-insensitive indexes and all sorts of cool stuff. Worth checking out.

Answer 2

I'm not sure I understand the question, but I think what you're asking for is multiple ways to map from different, unique keys to values and appropriate clean-up when a value goes away.

I see that you don't want to roll your own, but there's a simple enough composition of map and multimap (I used the Guava multimap below, but the Apache one should work as well) to do what you want. I have a quick and dirty solution below (skipped the constructors, since that depends on what sort of underlying map/multimap you want to use):

package edu.cap10.common.collect;

import java.util.Collection;
import java.util.Map;

import com.google.common.collect.ForwardingMap;
import com.google.common.collect.Multimap;

public class MIndexLookupMap<T> extends ForwardingMap<Object,T>{

    Map<Object,T> delegate;
    Multimap<T,Object> reverse;

    @Override protected Map<Object, T> delegate() { return delegate; }

    @Override public void clear() {
        delegate.clear();
        reverse.clear();
    }

    @Override public boolean containsValue(Object value) { return reverse.containsKey(value); }

    @Override public T put(Object key, T value) {
        if (containsKey(key) && !get(key).equals(value)) reverse.remove(get(key), key); 
        reverse.put(value, key);
        return delegate.put(key, value);
    }

    @Override public void putAll(Map<? extends Object, ? extends T> m) {
        for (Entry<? extends Object,? extends T> e : m.entrySet()) put(e.getKey(),e.getValue());
    }

    public T remove(Object key) {
        T result = delegate.remove(key);
        reverse.remove(result, key);
        return result;
    }

    public void removeValue(T value) {
        for (Object key : reverse.removeAll(value)) delegate.remove(key);
    }

    public Collection<T> values() {
        return reverse.keySet();
    }   

}

removal is O(number of keys), but everything else is the same order as a typical map implementation (some extra constant scaling, since you also have to add things to the reverse).

I just used Object keys (should be fine with appropriate implementations of equals() and hashCode() and key distinction) - but you could also have a more specific type of key.

Answer 3

I've written a Table interface that includes methods like

V put(R rowKey, C columnKey, V value) 
V get(Object rowKey, Object columnKey) 
Map<R,V> column(C columnKey) 
Set<C> columnKeySet()
Map<C,V> row(R rowKey)
Set<R> rowKeySet()
Set<Table.Cell<R,C,V>> cellSet()

We'd like to include it in a future Guava release, but I don't know when that would happen. http://code.google.com/p/guava-libraries/issues/detail?id=173

Answer 4

Google Collections LinkedListMultimap

About your first requirement

• When a Value is removed, all index entries associated with that value must be removed.

I think There is neither a library nor a Helper that supports it.

Here is how i have done by using LinkedListMultimap

Multimap<Integer, String> multimap = LinkedListMultimap.create();

// Three duplicates entries
multimap.put(1, "A");
multimap.put(2, "B");
multimap.put(1, "A");
multimap.put(4, "C");
multimap.put(1, "A");

System.out.println(multimap.size()); // outputs 5

To get your first requirement, a Helper can play a good job

public static <K, V> void removeAllIndexEntriesAssociatedWith(Multimap<K, V> multimap, V value) {
    Collection<Map.Entry<K, V>> eCollection = multimap.entries();
    for (Map.Entry<K, V> entry : eCollection)
        if(entry.getValue().equals(value))
            eCollection.remove(entry);
}

...

removeAllIndexEntriesAssociatedWith(multimap, "A");

System.out.println(multimap.size()); // outputs 2

Google collections is

• lightweight
• Supported by Joshua Block (Effective Java)
• Nice features as ImmutableList, ImmutableMap and so on

Answer 5

lets look at project http://code.google.com/p/multiindexcontainer/wiki/MainPage This is generalized way how to use maps for JavaBean getters and perform lookups over indexed values. I think this is what you are looking for. Lets give it a try.

Answer 6

Basically a solution based on multiple hash maps would be possible, but in this case all of them have to be keped up-to-date manually. A very simple integrated solution can be found here: http://insidecoffe.blogspot.de/2013/04/indexable-hashmap-implementation.html