Java/Collections Data Structure/Map

A java.util.Map implementation using reference values

   
/**********************************************************************
Copyright (c) 2002 Mike Martin (TJDO) and others. All rights reserved.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
    http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
 
Contributors:
2002 Kelly Grizzle (TJDO)
2003 Andy Jefferson - commented
    ...
**********************************************************************/

import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * A <code>java.util.Map</code> implementation using reference values.
 *
 * <p>The values are stored in the map as references.  If the garbage collector
 * clears the reference, the corresponding key is automatically removed from the
 * map.
 *
 * @see java.lang.ref.Reference
 * @version $Revision: 1.3 $ 
 */
public abstract class ReferenceValueMap implements Map, Cloneable
{
    private HashMap map;
    private ReferenceQueue reaped = new ReferenceQueue();
    /**
     * Default Constructor.
     **/
    public ReferenceValueMap()
    {
        map = new HashMap();
    }
    /**
     * Constructor taking initial capacity.
     * @param initial_capacity Initial Capacity of HashMap
     **/
    public ReferenceValueMap(int initial_capacity)
    {
        map = new HashMap(initial_capacity);
    }
    /**
     * Constructor taking initial capacity and load factor.
     * @param initial_capacity Initial Capacity of HashMap
     * @param load_factor      Load Factor of HashMap
     **/
    public ReferenceValueMap(int initial_capacity,float load_factor)
    {
        map = new HashMap(initial_capacity, load_factor);
    }
    /**
     * Constructor taking initial Map.
     * @param m Map to initial with.
     **/
    public ReferenceValueMap(Map m)
    {
        map = new HashMap();
        putAll(m);
    }
    /**
     * Clone method.
     * @return Clone of this object.
     **/
    public Object clone()
    {
        reap();
        ReferenceValueMap rvm = null;
        
        try
        {
            rvm = (ReferenceValueMap)super.clone();
        }
        catch (CloneNotSupportedException e)
        {
            // Do nothing
        }
        rvm.map = (HashMap)map.clone(); // to preserve initialCapacity, loadFactor
        rvm.map.clear();
        rvm.reaped = new ReferenceQueue();
        rvm.putAll(entrySet());
        return rvm;
    }
    /**
     * References returned by <code>newValueReference</code> must implement
     * this interface to provide the corresponding map key for the value.
     */
    public interface ValueReference
    {
        /**
         * Returns the key associated with the value referenced by this
         * <code>Reference</code> object.
         * @return The Key
         */
        Object getKey();
    }
    /**
     * Returns a new <code>Reference</code> object to be inserted into the map.
     * Subclasses must implement this method to construct <code>Reference</code>
     * objects of the desired type (e.g. <code>SoftReference</code>, etc.).
     *
     * @param key   The key that will be inserted.
     * @param value The associated value to be referenced.
     * @param queue The <code>ReferenceQueue</code> with which to register the
     *              new <code>Reference</code> object.
     * @return The new ValueReference
     */
    protected abstract ValueReference newValueReference(Object key, Object value, ReferenceQueue queue);
    /**
     * Method to add an object to the Map.
     * @param key Key for object
     * @param value Value of object
     * @return The Object.
     **/ 
    public Object put(Object key, Object value)
    {
        reap();
        return map.put(key, newValueReference(key, value, reaped));
    }
    /**
     * Method to add the contents of a Map.
     * @param m Map
     **/ 
    public void putAll(Map m)
    {
        putAll(m.entrySet());
    }
    /**
     * Method to add the contents of a Set.
     * @param entrySet The Set
     **/
    private void putAll(Set entrySet)
    {
        Iterator i = entrySet.iterator();
        while (i.hasNext())
        {
            Map.Entry entry = (Map.Entry)i.next();
            put(entry.getKey(), entry.getValue());
        }
    }
    /**
     * Method to get a value for a key.
     * @param key The Key
     * @return The Value
     **/
    public Object get(Object key)
    {
        reap();
        Reference ref = (Reference)map.get(key);
        Object value = ref == null ? null : ref.get();
        return value;
    }
    /**
     * Method to empty the HashMap.
     **/
    public void clear()
    {
        reap();
        map.clear();
    }
    /**
     * Accessor for the size of the HashMap.
     * @return The size
     **/
    public int size()
    {
        reap();
        return map.size();
    }
    /**
     * Accessor for whether the Map contains the specified Key
     * @param obj The key
     * @return Whether the key exists
     **/
    public boolean containsKey(Object obj)
    {
        reap();
        return map.containsKey(obj);
    }
    /**
     * Accessor for whether the Map contains the specified value.
     * @param obj The value
     * @return Whether the Map contains the value.
     **/
    public boolean containsValue(Object obj)
    {
        reap();
        if (obj != null)
        {
            Iterator i = map.values().iterator();
            while (i.hasNext())
            {
                Reference ref = (Reference)i.next();
                if (obj.equals(ref.get()))
                {
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * Accessor for whether the Map is empty.
     * @return Whether the Map is empty.
     **/
    public boolean isEmpty()
    {
        reap();
        return map.isEmpty();
    }
    /**
     * Accessor for the Set of keys in the Map.
     * @return The Set of keys
     **/
    public Set keySet()
    {
        reap();
        return map.keySet();
    }
    /**
     * Accessor for the values from the Map.
     * @return The Values.
     **/
    public Collection values()
    {
        reap();
        Collection c = map.values();
        Iterator i = c.iterator();
        ArrayList l = new ArrayList(c.size());
        while (i.hasNext())
        {
            Reference ref = (Reference)i.next();
            Object obj = ref.get();
            if (obj != null)
            {
                l.add(obj);
            }
        }
        return Collections.unmodifiableList(l);
    }
    /**
     * Accessor for the entry set.
     * @return The Set.
     **/
    public Set entrySet()
    {
        reap();
        Set s = map.entrySet();
        Iterator i = s.iterator();
        HashMap m = new HashMap(s.size());
        while (i.hasNext())
        {
            Map.Entry entry = (Map.Entry)i.next();
            Reference ref = (Reference)entry.getValue();
            Object obj = ref.get();
            if (obj != null)
            {
                m.put(entry.getKey(), obj);
            }
        }
        return Collections.unmodifiableSet(m.entrySet());
    }
    /**
     * Method to remove an object for the specified key.
     * @param key The Key
     * @return The Object removed 
     **/
    public Object remove(Object key)
    {
        reap();
        return map.remove(key);
    }
    /**
     * Hashcode generator for this object.
     * @return The Hashcode
     **/
    public int hashCode()
    {
        reap();
        return map.hashCode();
    }
    /**
     * Equality operator.
     * @param o THe object to compare against.
     * @return Whether it is equal.
     **/
    public boolean equals(Object o)
    {
        reap();
        return map.equals(o);
    }
    /**
     * Utility method to reap objects.
     **/
    public void reap()
    {
        ValueReference ref;
        while ((ref = (ValueReference)reaped.poll()) != null)
        {
            map.remove(ref.getKey());
        }
    }
}

A map declared to hold objects of a type T can also hold objects that extend from T

   
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) {
    Map<Number, String> numMap = new HashMap<Number, String>();
    numMap.put(.5, "half");
    numMap.put(1, "first");
  }
}

Automatically Removing an Unreferenced Element from a Hash Table

   
import java.util.Iterator;
import java.util.Map;
import java.util.WeakHashMap;
public class Main {
  public static void main(String[] argv) throws Exception {
    Map weakMap = new WeakHashMap();
    Object keyObject = "";
    Object valueObject = "";
    weakMap.put(keyObject, valueObject);
    Iterator it = weakMap.keySet().iterator();
    while (it.hasNext()) {
      Object key = it.next();
    }
  }
}

A value retrieved from a type-specific collection does not need to be casted

   
import java.net.MalformedURLException;
import java.net.URL;
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) {
    Map<String, URL> urlMap = new HashMap<String, URL>();
    try {
      urlMap.put("java", new URL("http://www.jexp.ru"));
    } catch (MalformedURLException e) {
    }
    String s = urlMap.get("java").getHost();
  }
}

Convert Properties into Map

   
 
import java.util.Properties;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    Properties properties = new Properties();
    properties.setProperty("name", "Designer");
    properties.setProperty("version", "1.0");
    properties.setProperty("vendor", "Inc");
    Map<String, String> map = new HashMap<String, String>((Map) properties);
    Set propertySet = map.entrySet();
    for (Object o : propertySet) {
      Map.Entry entry = (Map.Entry) o;
      System.out.printf("%s = %s%n", entry.getKey(), entry.getValue());
    }
  }
}

Create an array containing the keys in a map

   
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) throws Exception {
    Map map = new HashMap();
    Object[] objectArray = map.keySet().toArray();
    MyClass[] array = (MyClass[]) map.keySet().toArray(new MyClass[map.keySet().size()]);
  }
}
class MyClass {
}

Create an array containing the values in a map

   
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) throws Exception {
    Map map = new HashMap();
    Object[] objectArray = map.values().toArray();
    MyClass[] array = (MyClass[]) map.values().toArray(new MyClass[map.values().size()]);
  }
}
class MyClass {
}

Create type specific collections

   
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class Main {
  public static void main(String[] args) {
    Map<Integer, String> grades = new HashMap<Integer, String>();
    grades.put(1, "A");
    grades.put(2, "B");
    grades.put(3, "C");
    grades.put(4, "D");
    grades.put(5, "E");
    String value = grades.get(1);
    List<String> dayNames = new ArrayList<String>();
    dayNames.add("Sunday");
    dayNames.add("Monday");
    dayNames.add("Tuesday");
    dayNames.add("Wednesday");
    String firstDay = dayNames.get(0);
  }
}

Creating a Hash Table

   
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class Main {
  public static void main(String[] argv) throws Exception {
    Map<String, Integer> map = new HashMap<String, Integer>();
    map = new TreeMap();
    map.put("a", new Integer(1));
    map.put("b", new Integer(2));
    map.put("c", new Integer(3));
    int size = map.size(); // 2
    Object oldValue = map.put("a", new Integer(9)); // 1
    oldValue = map.remove("c"); // 3
    Iterator it = map.keySet().iterator();
    while (it.hasNext()) {
      Object key = it.next();
    }
    it = map.values().iterator();
    while (it.hasNext()) {
      Object value = it.next();
    }
  }
}

Creating a Map That Retains Order-of-Insertion

   
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) throws Exception {
    Map<String, String> map = new LinkedHashMap<String, String>();
    map.put("1", "value1");
    map.put("2", "value2");
    map.put("3", "value3");
    map.put("2", "value4");
    for (Iterator it = map.keySet().iterator(); it.hasNext();) {
      Object key = it.next();
      Object value = map.get(key);
    }
  }
}

Creating and storing arrays in a map

   
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class Main {
  public static void main(String[] args) {
    Map<String, int[]> map = new TreeMap<String, int[]>();
    int[] array = new int[3];
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    map.put("array", array);
    Iterator<String> iter = map.keySet().iterator();
    while (iter.hasNext()) {
      String arrayName = iter.next();
      array = map.get(arrayName);
      System.out.print(arrayName + ":");
      for (int i = 0; i < array.length; i++) {
        System.out.print(array[i]);
      }
    }
  }
}
//array:012

Creating a Type-Specific Map [5.0]

   
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) throws Exception {
    Map<Integer, String> map = new HashMap<Integer, String>();
    map.put(1, "first");
    map.put(2, "second");
    // map.put(1, 2); <- Syntax error
  }
}

Creating a Type-Specific Map: creates a map whose keys are Integer objects and values are String objects.

   
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) {
    Map<Integer, String> map = new HashMap<Integer, String>();
    map.put(1, "first");
    map.put(2, "second");
    // map.put(1, 2); <- Syntax error
  }
}

Get a key from value with an HashMap

   
import java.util.HashMap;
import java.util.Map;
public class Main {
  public static void main(String[] argv) {
    Map<String, String> map = new HashMap<String, String>();
    map.put("1","one");
    map.put("2","two");
    map.put("3","three");
    map.put("4","four");
    
    System.out.println(getKeyFromValue(map,"three"));
  }
  public static Object getKeyFromValue(Map hm, Object value) {
    for (Object o : hm.keySet()) {
      if (hm.get(o).equals(value)) {
        return o;
      }
    }
    return null;
  }
}

Map techniques.

   
import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class Main {
  public static void main(String args[]) {
    Map<String, Integer> atomNums = new TreeMap<String, Integer>();
    atomNums.put("A", 1);
    atomNums.put("B", 2);
    atomNums.put("C", 3);
    atomNums.put("D", 4);
    atomNums.put("E", 5);
    atomNums.put("F", 6);
    System.out.println("The map contains these " + atomNums.size() + " entries:");
    Set<Map.Entry<String, Integer>> set = atomNums.entrySet();
    for (Map.Entry<String, Integer> me : set) {
      System.out.print(me.getKey() + ", Atomic Number: ");
      System.out.println(me.getValue());
    }
    TreeMap<String, Integer> atomNums2 = new TreeMap<String, Integer>();
    atomNums2.put("Q", 30);
    atomNums2.put("W", 82);
    atomNums.putAll(atomNums2);
    set = atomNums.entrySet();
    System.out.println("The map now contains these " + atomNums.size() + " entries:");
    for (Map.Entry<String, Integer> me : set) {
      System.out.print(me.getKey() + ", Atomic Number: ");
      System.out.println(me.getValue());
    }
    if (atomNums.containsKey("A"))
      System.out.println("A has an atomic number of " + atomNums.get("A"));
    if (atomNums.containsValue(82))
      System.out.println("The atomic number 82 is in the map.");
    System.out.println();
    if (atomNums.remove("A") != null)
      System.out.println("A has been removed.\n");
    else
      System.out.println("Entry not found.\n");
    Set<String> keys = atomNums.keySet();
    for (String str : keys)
      System.out.println(str + " ");
    Collection<Integer> vals = atomNums.values();
    for (Integer n : vals)
      System.out.println(n + " ");
    atomNums.clear();
    if (atomNums.isEmpty())
      System.out.println("The map is now empty.");
  }
}

Retrieve environment variables (JDK1.5)

   
import java.util.Iterator;
import java.util.Map;
public class Main {
  public static void main(String args[]) {
    System.out.println("PATH = " + System.getenv("PATH"));
    Map env = System.getenv();
    for (Iterator it = env.entrySet().iterator(); it.hasNext();) {
      Map.Entry entry = (Map.Entry) it.next();
      System.out.println(entry.getKey() + " = " + entry.getValue());
    }
  }
}

Sort based on the values

   
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class Main {
  public static void main(String[] a) {
    Map<String, String> yourMap = new HashMap<String, String>();
    yourMap.put("1", "one");
    yourMap.put("2", "two");
    yourMap.put("3", "three");
    Map<String, Object> map = new LinkedHashMap<String, Object>();
    List<String> keyList = new ArrayList<String>(yourMap.keySet());
    List<String> valueList = new ArrayList<String>(yourMap.values());
    Set<String> sortedSet = new TreeSet<String>(valueList);
    
    Object[] sortedArray = sortedSet.toArray();
    int size = sortedArray.length;
    for (int i = 0; i < size; i++) {
      map.put(keyList.get(valueList.indexOf(sortedArray[i])), sortedArray[i]);
    }
    Set ref = map.keySet();
    Iterator it = ref.iterator();
    while (it.hasNext()) {
      String i = (String) it.next();
      System.out.println(i);
    }
  }
}

Use Iterator to loop through the HashMap class

   
 
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Main {
  public static void main(String[] args) {
    Map errors = new HashMap();
    errors.put("404", "A.");
    errors.put("403", "B.");
    errors.put("500", "C.");
    String errorDesc = (String) errors.get("404");
    System.out.println("Error 404: " + errorDesc);
    Iterator iterator = errors.keySet().iterator();
    while (iterator.hasNext()) {
      String key = (String) iterator.next();
      System.out.println("Error " + key + " means " + errors.get(key));
    }
  }
}

Utility method that return a String representation of a map. The elements will be represented as "key = value"

  
import java.io.UnsupportedEncodingException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
/*
 *  Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *  
 *    http://www.apache.org/licenses/LICENSE-2.0
 *  
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License. 
 *  
 */

/**
 * Various string manipulation methods that are more efficient then chaining
 * string operations: all is done in the same buffer without creating a bunch of
 * string objects.
 * 
 * @author 
 */
public class Main {
  /**
   * Utility method that return a String representation of a map. The elements
   * will be represented as "key = value"
   * 
   * @param map
   *            The map to transform to a string
   * @return A csv string
   */
  public static final String mapToString( Map map )
  {
      if ( ( map == null ) || ( map.size() == 0 ) )
      {
          return "";
      }
      StringBuffer sb = new StringBuffer();
      boolean isFirst = true;
      Iterator iter = map.keySet().iterator();
      while ( iter.hasNext() )
      {
          if ( isFirst )
          {
              isFirst = false;
          }
          else
          {
              sb.append( ", " );
          }
          Object key = iter.next();
          sb.append( key );
          sb.append( " = "" ).append( map.get( key ) ).append( """ );
      }
      return sb.toString();
  }
}

Utility method that return a String representation of a map. The elements will be represented as "key = value" (tab)

  
import java.io.UnsupportedEncodingException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
/*
 *  Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *  
 *    http://www.apache.org/licenses/LICENSE-2.0
 *  
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License. 
 *  
 */

/**
 * Various string manipulation methods that are more efficient then chaining
 * string operations: all is done in the same buffer without creating a bunch of
 * string objects.
 * 
 * @author 
 */
public class Main {
  /**
   * Utility method that return a String representation of a map. The elements
   * will be represented as "key = value"
   * 
   * @param map
   *            The map to transform to a string
   * @return A csv string
   */
  public static final String mapToString( Map map, String tabs )
  {
      if ( ( map == null ) || ( map.size() == 0 ) )
      {
          return "";
      }
      StringBuffer sb = new StringBuffer();
      Iterator iter = map.keySet().iterator();
      while ( iter.hasNext() )
      {
          Object key = iter.next();
          sb.append( tabs );
          sb.append( key );
          Object value = map.get( key );
          sb.append( " = "" ).append( value.toString() ).append( ""\n" );
      }
      return sb.toString();
  }
}