Pattern or antipattern: Using property of value as key in Dictionary/Hashmap

Question

I wonder if it is good practice to use a property of the value as key in an Hashmap.

In Java it looks like:

private HashMap<String, VariableCondition> m_conditions = new HashMap<String, VariableCondition>();

// ...
m_conditions.put(var, new VariableCondition(var, value));

It would be critical if the HashMap is accessible from outside the object. But even as member variable you have to care about consistency of the HashMap yourself.

Is there an alternative pattern to realize the usecase. Using a List would be possible but you have to iterate the whole list for every access.

Answer 1

maybe there are prettier ways around but i use this quite a bit, especially during prototyping.

collecting things:

one example - very close to your example - is that you have a bunch of dates and you'd like to get lists for each day.

List<Event> events = dearDataStorePlzGiveMeDates(); 
TreeMap<Date, List<Event>> byDay = new TreeMap<>(); 
for( Event e : events ){
    List<Event> forDay = byDay.get( e.getDate() ); 
    if( forDay == null ) byDay.put( forDay = new List<Event>() ); 

    forDay.add( e ); 
}

this is quite nice if you have a dull datastore and little amounts of data. i'm using treemaps instead of hashmaps because they have an ordering on the keys. i also vary the inner list type to some sorted data structure sometimes.

note that this would be done quite differently in functional languages (map events to dates, sort, then collect events for each of those dates; very slow, but a 1-liner).

as a dirty replacement for sets

another thing if often need is make some data structure unique by a crazy criterion, while still keeping one instance of the associated data. consider this:

List<Creatures> = ...; // from somewhere
HashTable<Integer, Creature> examples = new HashTable<>(); 

for( Create c : creatures ){
    examples.put( c.getNumberLegs(), c ); 
}

now this gets you an animal with one leg, an animal with two legs, etc.

overal

i don't mind these constructs at all, if you put a little comment about your intention on top they should be very easy to follow.

i find them particularly useful if you have to work on existing data, i.e. you don't have access to the datastore (like mysql) or the datastore is just very dull and doesn't know how to accomplish such tasks.

the big advantage of hashmaps is their complexity, they have O(1) access time (O(log n) for treemaps) which is quite good.

alternatives

it sounds like what you really want is an "index", a way to quickly access instances based on one of their properties. in java there's the TreeSet class for that. It has O(log n) complexity for all operations and is used something like this:

TreeSet<MyClass> indexed = new TreeSet<>( new Comparator<MyClass>(){
    public int compare( MyClass a, MyClass b ){
        // "sort" by the property (assuming they are Integers)
        return a.getThing().compareTo( b.getThing() ); 
    }
}); 

indexed.addAll( theList ); 

attention though: (1) the behaviour here differs from your example!! assume keys appear multiple times, in your code (with hashtable) the last duplicate would survive. in this case the first element would survive (the treemap basically says "this is already in there, so ...whatever") (2) runtime complexity is good but way worse than the O(1) runtime when using HashMaps.

hope this answers your question ...

Answer 2

In .NET there is a KeyedCollection that does exactly what you need.

But speaking generally the link between key and value is an internal knowledge that should be hidden from consumer. So I would recommend to encapsulate that hash in other class that will provide API to set / get data from it. Below is quick example in C#:

public class KeyedStorage<K, T>
{
    private readonly Func<T, K> keyFunc;
    private readonly Dictionary<K, T> dictionary = new Dictionary<K, T>();

    public KeyedStorage(Func<T, K> keyFunc)
    {
        this.keyFunc = keyFunc;
    }

    public void Add(T item)
    {
        var key = keyFunc(item);
        dictionary.Add(key, item);
    }

    public T this[K key]
    {
        get { return dictionary[key]; }
    }
}

public class KeyedStorageTests
{
    [Fact]
    public void should_return_item_after_add()
    {
        // arrange
        var keyedStorage = new KeyedStorage<int, string>(s => s.GetHashCode());

        // act
        keyedStorage.Add("werew");

        // assert
        keyedStorage["werew".GetHashCode()]
            .Should()
            .Be("werew");
    }
}

Answer 3

What you describe is like building an index on a collection. I don't see anything wrong with it in general. Just be sure that the key is unique!

If you use java you might consider the uniqueIndex method of guava's Maps class.

Answer 4

If your variable could have only one condition value it's perfectly good, but IMO it's easier to have map because pair {variable,value} it's itself {key,value} pair, so you don't need VariableCondition abstraction.