Implement case insensitive map

Implement a map that satisfies below conditions.

a.   It should treat keys case insensitively. For example, the key "India", "INDIA", "inDIA" are treated as equal and there is only one entry exist for the keys "India", "INDIA", "inDIA" at any point of time.

b.   It should return the key as it is (do not convert key to lower case (or) upper case while storing)

c.   Maintain the order of insertion.

d.   If the key is not a string, then it should behave like normal map

Before going to read the solution, I would recommend you to go through ‘How HashMap works in Java?’, ‘How LinkedHashMap works in Java?’, ‘How TreeMap works in Java?’

All the crud specific methods like get, put, putAll, containsKey, remove, entrySet, keySet is going to be impacted to implement a map case sensitively.

While inserting a key into the map, we should check whether the key is instance of string or not. If key is instance of string, we need to check, whether any case-insensitive string present or not. If the case insensitive string is already existed in the map, then we should replace that entry with given entry.

There can be multiple implementations possible, but I would like to go with below approach.

I defined new class ‘CaseInsensitiveString’ to wrap string keys.

 private static class CaseInsensitiveString {
  private String key;

  public CaseInsensitiveString(String key) {
   this.key = key;
  }

  @Override
  public int hashCode() {
   if (key == null)
    return 0;

   return key.toUpperCase().hashCode();
  }

  @Override
  public boolean equals(Object obj) {
   if (this == obj)
    return true;
   if (obj == null)
    return false;
   if (getClass() != obj.getClass())
    return false;
   CaseInsensitiveString other = (CaseInsensitiveString) obj;
   if (key == null) {
    if (other.key != null)
     return false;
   } else if (!key.toUpperCase().equals(other.key.toUpperCase()))
    return false;
   return true;
  }

  @Override
  public String toString() {
   return key;
  }

 }

If the key is of type string, then I will wrap the string using CaseInsensitiveString object. I override the hashCode and equals method such that, two case-insensitive equal strings always point to same bucket and treated as equal. If you would like to know the relation between equals and hashCode method, I would recommend you to go through ‘Contract between hashCode and equals’.

To satisfy the point c, we should use the LinkedHashMap.

Find the below working application, java documentation on the methods is self-explanatory.

InsensitiveMap.java

package com.sample.collections;

import java.util.AbstractMap;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;


public class InsensitiveMap<K, V> implements Map<K, V> {
 private Map<K, V> map;

 public InsensitiveMap() {
  map = new LinkedHashMap<>();
 }

 /**
  * Convert the object to Case insensitive string.
  * 
  * @param obj
  * @return
  */
 private static CaseInsensitiveString convertObjectToCaseInsensitiveString(Object obj) {
  String keyStr = (String) obj;
  return new CaseInsensitiveString(keyStr);
 }

 @Override
 public int size() {
  return map.size();
 }

 @Override
 public boolean isEmpty() {
  return map.isEmpty();
 }

 @Override
 public boolean containsKey(Object key) {
  if (!(key instanceof String)) {
   return map.containsKey(key);
  }

  return map.containsKey(convertObjectToCaseInsensitiveString(key));
 }

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

 @Override
 public V get(Object key) {
  if (!(key instanceof String)) {
   return map.get(key);
  }

  return map.get(convertObjectToCaseInsensitiveString(key));
 }

 @Override
 public V put(K key, V value) {
  if (!(key instanceof String)) {
   return map.put(key, value);
  }

  CaseInsensitiveString caseInsensitiveString = convertObjectToCaseInsensitiveString(key);
  return map.put((K) caseInsensitiveString, value);

 }

 @Override
 public V remove(Object key) {
  if (!(key instanceof String)) {
   return map.remove(key);
  }

  return map.remove(convertObjectToCaseInsensitiveString(key));

 }

 @Override
 public void putAll(Map<? extends K, ? extends V> m) {
  if (m == null) {
   return;
  }

  for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
   put(entry.getKey(), entry.getValue());
  }
 }

 @Override
 public void clear() {
  map.clear();
 }

 @Override
 public Set<K> keySet() {

  Set set = new LinkedHashSet();

  for (Object key : map.keySet()) {
   set.add(key instanceof CaseInsensitiveString ? key.toString() : key);
  }
  return set;
 }

 @Override
 public Collection<V> values() {
  return map.values();
 }

 @Override
 public Set<java.util.Map.Entry<K, V>> entrySet() {
  Set<Entry<K, V>> entrySet = map.entrySet();
  Set<Entry<K, V>> outputSet = new LinkedHashSet<Entry<K, V>>();

  for (Entry entry : entrySet) {
   if (!(entry.getKey() instanceof CaseInsensitiveString)) {
    outputSet.add(entry);
   }

   CaseInsensitiveString key = (CaseInsensitiveString) entry.getKey();
   entry = new AbstractMap.SimpleImmutableEntry<K, V>((K) key.toString(), (V) entry.getValue());

  }

  return outputSet;
 }

 private static class CaseInsensitiveString {
  private String key;

  public CaseInsensitiveString(String key) {
   this.key = key;
  }

  @Override
  public int hashCode() {
   if (key == null)
    return 0;

   return key.toUpperCase().hashCode();
  }

  @Override
  public boolean equals(Object obj) {
   if (this == obj)
    return true;
   if (obj == null)
    return false;
   if (getClass() != obj.getClass())
    return false;
   CaseInsensitiveString other = (CaseInsensitiveString) obj;
   if (key == null) {
    if (other.key != null)
     return false;
   } else if (!key.toUpperCase().equals(other.key.toUpperCase()))
    return false;
   return true;
  }

  @Override
  public String toString() {
   return key;
  }

 }

}

Test.java

package com.sample.collections;

import java.util.Map;
import java.util.Set;

import com.sample.collections.InsensitiveMap;

public class Test {

 private static void printMap(Map map) {

  Set set = map.keySet();

  for (Object obj : set) {
   System.out.println(obj + " " + map.get(obj));
  }
 }

 public static void main(String args[]) throws CloneNotSupportedException {
  InsensitiveMap<String, String> map = new InsensitiveMap<>();

  map.put("Krishna", "ptr");

  printMap(map);

  map.put("KRIshna", "123");
  printMap(map);

  map.put("KRISHNA", "abcde");
  printMap(map);

 }
}

Output

Krishna ptr
Krishna 123
Krishna abcde

You may like

Miscellaneous

Interview Questions

How IdentityHashMap Works in Java?

Implement Bijective Map

Get elements of LinkedHashMap by access order?

Implement LRU cache using LinkedHashMap

How to override hashCode method

How to get the interfaces implemented by a class?

Different ways to sort Array list in Java

Initialize list in one line

Merge generic arrays

How to get shallow copy of array?