Appropriately backing a case insensitive map

Question

I want to implement a case insensitive hash map. This question by itself isn't new, but I wanted to add extra functionality and don't know what general direction to take. I want the client to be able to do something like this:

boolean preserve_case = true;
Map<String, MyClass> maplet = new CaseInsensitiveHashMap<MyClass>(preserve_case); // If the client enters true at construction, then the put, get, and remove methods should still be case insensitive, but the entry and key sets should preserve the case that the client used when calling put.

maplet.put("FoO", my_class);

MyClass bar = maplet.get("foo"); // Should return a reference to my_class

Set<Entry<String, MyClass>> case_sensitive_set = maplet.entrySet(); // Since the client input true to preserve order, this entry set should be ["FoO"=my_class.toString()]

I can handle most of this pretty well; I simply keep a HashMap on the backend. When a client puts anything in, I uppercase the key before adding it to the map.

I'm just having a hard time writing the keySet() and entrySet() methods. I want the returned entry set and key set to be backed by the map, as is the standard with Java maps.

However, the only way I can think of handling this is to create a second backing data structure, something like a preserved_case_map, which contains the input.toUpperCase() => input as key value pairs. When the client calls for the entrySet() (or keySet()), I can construct the returned entry set by looping through the preserved_case_map. The problem here is that the returned entry set will not be modified if I make changes to the HashMap, unless I'm misunderstanding something...

Let me know if this makes sense, or if I'm convoluting a simple situation.

Answer 1

You could use a TreeMap with case insensitive comparator. The TreeMap will use the comparator to compare keys in a case-insensitive way:

    Map<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

    map.put("Foo", 1);
    map.put("fOo", 2);

    System.out.println(map.get("foo")); // prints 2
    System.out.println(map.keySet()); // prints [Foo]

Answer 2

To simplify wrapping a map you can use the ForwardingMap from Googles Guava libraries but thats optional.

Before putting/getting something from the backing map, wrap your String key in a class that overrides hashCode()/equals() and use the wrapper as the key in the map. Something like:

class KeyWrapper { 
    int hashCode() { 
        return actualStringKey.toUpperCase().hashCode()
    }
    boolean equals(Object o) {...} // compare case-insensitive
}

If you override keySet() you can create a new set and fill it with actualStringKeys.

Answer 3

You could use CaseInsensitiveMap from Apache's Commons Collections.

http://commons.apache.org/proper/commons-collections/

Answer 4

Instead of just storing the value, store a KeyValuePair of both the input key (which still has the user-supplied case) and the value, and use the upper-cased key as the key.

When you pull out the value, extract it from the KeyValuePair before returning it. You can also retrieve the case of the original key by doing the same lookup with the uppercased key, and then pulling out the original key.

Answer 5

I do something along these lines for a mapped Cache that I have written. Naming changed here to reflect your case-insensitivity instead of my caching, but the concepts are the same.

This would give you an UncasedMap class that could be re-used to hold anything, but would be limited to using Strings as keys.

// Map that uses case insensitive strings as keys to any kind of element
public class UncasedMap<V> extends HashMap<String, V>
{
    private static final long serialVersionUID = 1L;
    private Map<String, MappedObject> backingMap = new HashMap<String, MappedObject>();

    @Override
    public V put(String key, V value)
    {
        MappedObject currentVal = backingMap.get( key.toUpperCase() );
        backingMap.put( key.toUpperCase(), new MappedObject(key.toUpperCase(), value) );
        return currentVal.getElement();

    }
    @Override
    public V get(Object key)
    {
        return backingMap.get(key.toString().toUpperCase()).getElement();
    }

    // a private inner class of my case insensitive map, to wrap the callers element
    private class MappedObject
    {
        private String key;
        private String orig_key;
        private V mapElement;

        public MappedObject(String keyx, V elem)
        {
            this.orig_key = keyx;
            this.key = keyx.toUpperCase();
            this.mapElement = elem;
        }

        public V getElement()
        {
            return this.mapElement;
        }
    }
}

Implementing keySet() and emptySet() would be more complicated, but done along the same lines.

Answer 6

One way is to inherit from HashMap<String, V>, then call methods in the base class after calling toUpperCase() on the key(s).

However, it is much easier to just override the hashCode() method in MyClass (or whatever classes you'll use), and then use the standard HashMap<K, V> class, without implementing your own. For example:

public int hashCode() {
    return this.toString().toUperCase().hashCode();
}

If you put that in a base class and then have your classes inherit from it, then you will have a DRY and very simple solution to your problem.