Java Tutorial/Collections/Customized Map

A fixed size map implementation.

   <source lang="java">

/*

* 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.
*/

import java.io.Serializable; import java.util.AbstractList; import java.util.AbstractSet; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**

* A fixed size map implementation. Holds an array of keys and array of values which correspond by
* index. Null key entries are available for use. This means that null is not a valid key.
* 
* @author Jonathan Locke
* @param <K>
*            Key type
* @param <V>
*            Value type
*/

public class MiniMap<K, V> implements Map<K, V>, Serializable {

 private static final long serialVersionUID = 1L;
 /** The array of keys. Keys that are null are not used. */
 private final K[] keys;
 /** The array of values which correspond by index with the keys array. */
 private final V[] values;
 /** The number of valid entries */
 private int size;
 /** The last search index. This makes putting and getting more efficient. */
 private int lastSearchIndex;
 /**
  * Constructor
  * 
  * @param maxEntries
  *            The maximum number of entries this map can hold
  */
 @SuppressWarnings("unchecked")
 public MiniMap(final int maxEntries)
 {
   keys = (K[])new Object[maxEntries];
   values = (V[])new Object[maxEntries];
 }
 /**
  * Constructor
  * 
  * @param map
  *            The map
  * @param maxEntries
  *            The maximum number of entries this map can hold
  */
 public MiniMap(final Map<? extends K, ? extends V> map, final int maxEntries)
 {
   this(maxEntries);
   putAll(map);
 }
 /**
  * @return True if this MicroMap is full
  */
 public boolean isFull()
 {
   return size == keys.length;
 }
 /**
  * @see java.util.Map#size()
  */
 public int size()
 {
   return size;
 }
 /**
  * @see java.util.Map#isEmpty()
  */
 public boolean isEmpty()
 {
   return size == 0;
 }
 /**
  * @see java.util.Map#containsKey(java.lang.Object)
  */
 public boolean containsKey(final Object key)
 {
   return findKey(0, key) != -1;
 }
 /**
  * @see java.util.Map#containsValue(java.lang.Object)
  */
 public boolean containsValue(final Object value)
 {
   return findValue(0, value) != -1;
 }
 /**
  * @see java.util.Map#get(java.lang.Object)
  */
 public V get(final Object key)
 {
   // Search for key
   final int index = findKey(key);
   if (index != -1)
   {
     // Return value
     return values[index];
   }
   // Failed to find key
   return null;
 }
 /**
  * @see java.util.Map#put(java.lang.Object, java.lang.Object)
  */
 public V put(final K key, final V value)
 {
   // Search for key
   final int index = findKey(key);
   if (index != -1)
   {
     // Replace existing value
     final V oldValue = values[index];
     values[index] = value;
     return oldValue;
   }
   // Is there room for a new entry?
   if (size < keys.length)
   {
     // Store at first null index and continue searching after null index
     // next time
     final int nullIndex = nextNullKey(lastSearchIndex);
     lastSearchIndex = nextIndex(nullIndex);
     keys[nullIndex] = key;
     values[nullIndex] = value;
     size++;
     return null;
   }
   else
   {
     throw new IllegalStateException("Map full");
   }
 }
 /**
  * @see java.util.Map#remove(java.lang.Object)
  */
 public V remove(final Object key)
 {
   // Search for key
   final int index = findKey(key);
   if (index != -1)
   {
     // Store value
     final V oldValue = values[index];
     keys[index] = null;
     values[index] = null;
     size--;
     return oldValue;
   }
   return null;
 }
 /**
  * @see java.util.Map#putAll(java.util.Map)
  */
 public void putAll(Map<? extends K, ? extends V> map)
 {
   for (final Iterator<? extends Entry<? extends K, ? extends V>> iterator = map.entrySet()
     .iterator(); iterator.hasNext();)
   {
     final Map.Entry<? extends K, ? extends V> e = iterator.next();
     put(e.getKey(), e.getValue());
   }
 }
 /**
  * @see java.util.Map#clear()
  */
 public void clear()
 {
   for (int i = 0; i < keys.length; i++)
   {
     keys[i] = null;
     values[i] = null;
   }
   size = 0;
 }
 /**
  * @see java.util.Map#keySet()
  */
 public Set<K> keySet()
 {
   return new AbstractSet<K>()
   {
     @Override
     public Iterator<K> iterator()
     {
       return new Iterator<K>()
       {
         public boolean hasNext()
         {
           return i < size - 1;
         }
         public K next()
         {
           // Just in case... (WICKET-428)
           if (!hasNext())
           {
             throw new NoSuchElementException();
           }
           // Find next key
           i = nextKey(nextIndex(i));
           // Get key
           return keys[i];
         }
         public void remove()
         {
           keys[i] = null;
           values[i] = null;
           size--;
         }
         int i = -1;
       };
     }
     @Override
     public int size()
     {
       return size;
     }
   };
 }
 /**
  * @see java.util.Map#values()
  */
 public Collection<V> values()
 {
   return new AbstractList<V>()
   {
     @Override
     public V get(final int index)
     {
       if (index > size - 1)
       {
         throw new IndexOutOfBoundsException();
       }
       int keyIndex = nextKey(0);
       for (int i = 0; i < index; i++)
       {
         keyIndex = nextKey(keyIndex + 1);
       }
       return values[keyIndex];
     }
     @Override
     public int size()
     {
       return size;
     }
   };
 }
 /**
  * @see java.util.Map#entrySet()
  */
 public Set<Entry<K, V>> entrySet()
 {
   return new AbstractSet<Entry<K, V>>()
   {
     @Override
     public Iterator<Entry<K, V>> iterator()
     {
       return new Iterator<Entry<K, V>>()
       {
         public boolean hasNext()
         {
           return index < size;
         }
         public Entry<K, V> next()
         {
           if (!hasNext())
           {
             throw new NoSuchElementException();
           }
           keyIndex = nextKey(nextIndex(keyIndex));
           index++;
           return new Map.Entry<K, V>()
           {
             public K getKey()
             {
               return keys[keyIndex];
             }
             public V getValue()
             {
               return values[keyIndex];
             }
             public V setValue(final V value)
             {
               final V oldValue = values[keyIndex];
               values[keyIndex] = value;
               return oldValue;
             }
           };
         }
         public void remove()
         {
           keys[keyIndex] = null;
           values[keyIndex] = null;
         }
         int keyIndex = -1;
         int index = 0;
       };
     }
     @Override
     public int size()
     {
       return size;
     }
   };
 }
 /**
  * Computes the next index in the key or value array (both are the same length)
  * 
  * @param index
  *            The index
  * @return The next index, taking into account wraparound
  */
 private int nextIndex(final int index)
 {
   return (index + 1) % keys.length;
 }
 /**
  * Finds the index of the next non-null key. If the map is empty, -1 will be returned.
  * 
  * @param start
  *            Index to start at
  * @return Index of next non-null key
  */
 private int nextKey(final int start)
 {
   int i = start;
   do
   {
     if (keys[i] != null)
     {
       return i;
     }
     i = nextIndex(i);
   }
   while (i != start);
   return -1;
 }
 /**
  * Finds the index of the next null key. If no null key can be found, the map is full and -1
  * will be returned.
  * 
  * @param start
  *            Index to start at
  * @return Index of next null key
  */
 private int nextNullKey(final int start)
 {
   int i = start;
   do
   {
     if (keys[i] == null)
     {
       return i;
     }
     i = nextIndex(i);
   }
   while (i != start);
   return -1;
 }
 /**
  * Finds a key by starting at lastSearchIndex and searching from there. If the key is found,
  * lastSearchIndex is advanced so the next key search can find the next key in the array, which
  * is the most likely to be retrieved.
  * 
  * @param key
  *            Key to find in map
  * @return Index of matching key or -1 if not found
  */
 private int findKey(final Object key)
 {
   if (size > 0)
   {
     // Find key starting at search index
     final int index = findKey(lastSearchIndex, key);
     // Found match?
     if (index != -1)
     {
       // Start search at the next index next time
       lastSearchIndex = nextIndex(index);
       // Return index of key
       return index;
     }
   }
   return -1;
 }
 /**
  * Searches for a key from a given starting index.
  * 
  * @param key
  *            The key to find in this map
  * @param start
  *            Index to start at
  * @return Index of matching key or -1 if not found
  */
 private int findKey(final int start, final Object key)
 {
   int i = start;
   do
   {
     if (key.equals(keys[i]))
     {
       return i;
     }
     i = nextIndex(i);
   }
   while (i != start);
   return -1;
 }
 /**
  * Searches for a value from a given starting index.
  * 
  * @param start
  *            Index to start at
  * @param value
  *            The value to find in this map
  * @return Index of matching value or -1 if not found
  */
 private int findValue(final int start, final Object value)
 {
   int i = start;
   do
   {
     if (value.equals(values[i]))
     {
       return i;
     }
     i = nextIndex(i);
   }
   while (i != start);
   return -1;
 }

}</source>

A hash map that uses primitive ints for the key rather than objects.

   <source lang="java">

/*

* 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.
*/

/*

* Note: originally released under the GNU LGPL v2.1, 
* but rereleased by the original author under the ASF license (above).
*/

/**

* A hash map that uses primitive ints for the key rather than objects.
*
* Note that this class is for internal optimization purposes only, and may
* not be supported in future releases of Apache Commons Lang.  Utilities of
* this sort may be included in future releases of Apache Commons Collections.
*
* @author Justin Couch
* @author Alex Chaffee (alex@apache.org)
* @author Stephen Colebourne
* @since 2.0
* @version $Revision: 561230 $
* @see java.util.HashMap
*/

class IntHashMap {

   /**
    * The hash table data.
    */
   private transient Entry table[];
   /**
    * The total number of entries in the hash table.
    */
   private transient int count;
   /**
    * The table is rehashed when its size exceeds this threshold.  (The
    * value of this field is (int)(capacity * loadFactor).)
    *
    * @serial
    */
   private int threshold;
   /**
    * The load factor for the hashtable.
    *
    * @serial
    */
   private float loadFactor;
   /**
    * Innerclass that acts as a datastructure to create a new entry in the
    * table.
    */
   private static class Entry {
       int hash;
       int key;
       Object value;
       Entry next;
       /**
        * Create a new entry with the given values.
        *
        * @param hash The code used to hash the object with
        * @param key The key used to enter this in the table
        * @param value The value for this key
        * @param next A reference to the next entry in the table
        */
       protected Entry(int hash, int key, Object value, Entry next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
       }
   }
   /**
    * Constructs a new, empty hashtable with a default capacity and load
    * factor, which is 20 and 0.75 respectively.
    */
   public IntHashMap() {
       this(20, 0.75f);
   }
   /**
    * Constructs a new, empty hashtable with the specified initial capacity
    * and default load factor, which is 0.75.
    *
    * @param  initialCapacity the initial capacity of the hashtable.
    * @throws IllegalArgumentException if the initial capacity is less
    *   than zero.
    */
   public IntHashMap(int initialCapacity) {
       this(initialCapacity, 0.75f);
   }
   /**
    * Constructs a new, empty hashtable with the specified initial
    * capacity and the specified load factor.
    *
    * @param initialCapacity the initial capacity of the hashtable.
    * @param loadFactor the load factor of the hashtable.
    * @throws IllegalArgumentException  if the initial capacity is less
    *             than zero, or if the load factor is nonpositive.
    */
   public IntHashMap(int initialCapacity, float loadFactor) {
       super();
       if (initialCapacity < 0) {
           throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
       }
       if (loadFactor <= 0) {
           throw new IllegalArgumentException("Illegal Load: " + loadFactor);
       }
       if (initialCapacity == 0) {
           initialCapacity = 1;
       }
       this.loadFactor = loadFactor;
       table = new Entry[initialCapacity];
       threshold = (int) (initialCapacity * loadFactor);
   }
   /**
    * Returns the number of keys in this hashtable.
    *
    * @return  the number of keys in this hashtable.
    */
   public int size() {
       return count;
   }
   /**
    * Tests if this hashtable maps no keys to values.
    *
    * @return  true if this hashtable maps no keys to values;
    *          false otherwise.
    */
   public boolean isEmpty() {
       return count == 0;
   }
   /**
    * Tests if some key maps into the specified value in this hashtable.
    * This operation is more expensive than the containsKey
    * method.
    *
    * Note that this method is identical in functionality to containsValue,
    * (which is part of the Map interface in the collections framework).
    *
    * @param      value   a value to search for.
    * @return     true if and only if some key maps to the
    *             value argument in this hashtable as
    *             determined by the equals method;
    *             false otherwise.
    * @throws  NullPointerException  if the value is null.
    * @see        #containsKey(int)
    * @see        #containsValue(Object)
    * @see        java.util.Map
    */
   public boolean contains(Object value) {
       if (value == null) {
           throw new NullPointerException();
       }
       Entry tab[] = table;
       for (int i = tab.length; i-- > 0;) {
           for (Entry e = tab[i]; e != null; e = e.next) {
               if (e.value.equals(value)) {
                   return true;
               }
           }
       }
       return false;
   }
   /**
    * Returns true if this HashMap maps one or more keys
    * to this value.
    *
    * Note that this method is identical in functionality to contains
    * (which predates the Map interface).
    *
    * @param value value whose presence in this HashMap is to be tested.
    * @return boolean true if the value is contained
    * @see    java.util.Map
    * @since JDK1.2
    */
   public boolean containsValue(Object value) {
       return contains(value);
   }
   /**
    * Tests if the specified object is a key in this hashtable.
    *
    * @param  key  possible key.
    * @return true if and only if the specified object is a
    *    key in this hashtable, as determined by the equals
    *    method; false otherwise.
    * @see #contains(Object)
    */
   public boolean containsKey(int key) {
       Entry tab[] = table;
       int hash = key;
       int index = (hash & 0x7FFFFFFF) % tab.length;
       for (Entry e = tab[index]; e != null; e = e.next) {
           if (e.hash == hash) {
               return true;
           }
       }
       return false;
   }
   /**
    * Returns the value to which the specified key is mapped in this map.
    *
    * @param   key   a key in the hashtable.
    * @return  the value to which the key is mapped in this hashtable;
    *          null if the key is not mapped to any value in
    *          this hashtable.
    * @see     #put(int, Object)
    */
   public Object get(int key) {
       Entry tab[] = table;
       int hash = key;
       int index = (hash & 0x7FFFFFFF) % tab.length;
       for (Entry e = tab[index]; e != null; e = e.next) {
           if (e.hash == hash) {
               return e.value;
           }
       }
       return null;
   }
   /**
    * Increases the capacity of and internally reorganizes this
    * hashtable, in order to accommodate and access its entries more
    * efficiently.
    *
    * This method is called automatically when the number of keys
    * in the hashtable exceeds this hashtable"s capacity and load
    * factor.
    */
   protected void rehash() {
       int oldCapacity = table.length;
       Entry oldMap[] = table;
       int newCapacity = oldCapacity * 2 + 1;
       Entry newMap[] = new Entry[newCapacity];
       threshold = (int) (newCapacity * loadFactor);
       table = newMap;
       for (int i = oldCapacity; i-- > 0;) {
           for (Entry old = oldMap[i]; old != null;) {
               Entry e = old;
               old = old.next;
               int index = (e.hash & 0x7FFFFFFF) % newCapacity;
               e.next = newMap[index];
               newMap[index] = e;
           }
       }
   }
   /**
    * Maps the specified key to the specified
    * value in this hashtable. The key cannot be
    * null. 
    *
    * The value can be retrieved by calling the get method
    * with a key that is equal to the original key.
    *
    * @param key     the hashtable key.
    * @param value   the value.
    * @return the previous value of the specified key in this hashtable,
    *         or null if it did not have one.
    * @throws  NullPointerException  if the key is null.
    * @see     #get(int)
    */
   public Object put(int key, Object value) {
       // Makes sure the key is not already in the hashtable.
       Entry tab[] = table;
       int hash = key;
       int index = (hash & 0x7FFFFFFF) % tab.length;
       for (Entry e = tab[index]; e != null; e = e.next) {
           if (e.hash == hash) {
               Object old = e.value;
               e.value = value;
               return old;
           }
       }
       if (count >= threshold) {
           // Rehash the table if the threshold is exceeded
           rehash();
           tab = table;
           index = (hash & 0x7FFFFFFF) % tab.length;
       }
       // Creates the new entry.
       Entry e = new Entry(hash, key, value, tab[index]);
       tab[index] = e;
       count++;
       return null;
   }
   /**
    * Removes the key (and its corresponding value) from this
    * hashtable.
    *
    * This method does nothing if the key is not present in the
    * hashtable.
    *
    * @param   key   the key that needs to be removed.
    * @return  the value to which the key had been mapped in this hashtable,
    *          or null if the key did not have a mapping.
    */
   public Object remove(int key) {
       Entry tab[] = table;
       int hash = key;
       int index = (hash & 0x7FFFFFFF) % tab.length;
       for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
           if (e.hash == hash) {
               if (prev != null) {
                   prev.next = e.next;
               } else {
                   tab[index] = e.next;
               }
               count--;
               Object oldValue = e.value;
               e.value = null;
               return oldValue;
           }
       }
       return null;
   }
   /**
    * Clears this hashtable so that it contains no keys.
    */
   public synchronized void clear() {
       Entry tab[] = table;
       for (int index = tab.length; --index >= 0;) {
           tab[index] = null;
       }
       count = 0;
   }
   

}</source>

A java.util.Map implementation using reference values

   <source lang="java">

/********************************************************************** 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 java.util.Map implementation using reference values.
*
* 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 newValueReference 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
        * Reference object.
        * @return The Key
        */
       Object getKey();
   }
   /**
    * Returns a new Reference object to be inserted into the map.
    * Subclasses must implement this method to construct Reference
    * objects of the desired type (e.g. SoftReference, etc.).
    *
    * @param key   The key that will be inserted.
    * @param value The associated value to be referenced.
    * @param queue The ReferenceQueue with which to register the
    *              new Reference 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());
       }
   }

}</source>

A Map where keys are compared by object identity, rather than equals()

   <source lang="java">

/*

* Hibernate, Relational Persistence for Idiomatic Java
*
* Copyright (c) 2008, Red Hat Middleware LLC or third-party contributors as
* indicated by the @author tags or express copyright attribution
* statements applied by the authors.  All third-party contributions are
* distributed under license by Red Hat Middleware LLC.
*
* This copyrighted material is made available to anyone wishing to use, modify,
* copy, or redistribute it subject to the terms and conditions of the GNU
* Lesser General Public License, as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
* for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this distribution; if not, write to:
* Free Software Foundation, Inc.
* 51 Franklin Street, Fifth Floor
* Boston, MA  02110-1301  USA
*
*/

import java.io.Serializable; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Set; /**

* A Map where keys are compared by object identity,
* rather than equals().
*/

public final class IdentityMap implements Map {

 private final Map map;
 private transient Map.Entry[] entryArray = new Map.Entry[0];
 private transient boolean dirty = false;
 /**
  * Return a new instance of this class, with an undefined
  * iteration order.
  *
  * @param size The size of the map
  * @return Map
  */
 public static Map instantiate(int size) {
   return new IdentityMap( new HashMap( size ) );
 }
 /**
  * Return a new instance of this class, with iteration
  * order defined as the order in which entries were added
  *
  * @param size The size of the map to create
  * @return
  */
 public static Map instantiateSequenced(int size) {
   return new IdentityMap( new LinkedHashMap( size ) );
 }
 /**
  * Private ctor used in serialization.
  *
  * @param underlyingMap The delegate map.
  */
 private IdentityMap(Map underlyingMap) {
   map = underlyingMap;
   dirty = true;
 }
 /**
  * Return the map entries (as instances of Map.Entry in a collection that
  * is safe from concurrent modification). ie. we may safely add new instances to
  * the underlying Map during iteration of the entries().
  *
  * @param map
  * @return Collection
  */
 public static Map.Entry[] concurrentEntries(Map map) {
   return ( (IdentityMap) map ).entryArray();
 }
 public static List entries(Map map) {
   return ( (IdentityMap) map ).entryList();
 }
 public static Iterator keyIterator(Map map) {
   return ( (IdentityMap) map ).keyIterator();
 }
 public Iterator keyIterator() {
   return new KeyIterator( map.keySet().iterator() );
 }
 public static final class IdentityMapEntry implements java.util.Map.Entry {
   IdentityMapEntry(Object key, Object value) {
     this.key=key;
     this.value=value;
   }
   private Object key;
   private Object value;
   public Object getKey() {
     return key;
   }
   public Object getValue() {
     return value;
   }
   public Object setValue(Object value) {
     Object result = this.value;
     this.value = value;
     return result;
   }
 }
 public static final class IdentityKey implements Serializable {
   private Object key;
   IdentityKey(Object key) {
     this.key=key;
   }
   public boolean equals(Object other) {
     return key == ( (IdentityKey) other ).key;
   }
   public int hashCode() {
     return System.identityHashCode(key);
   }
   public String toString() {
     return key.toString();
   }
   public Object getRealKey() {
     return key;
   }
 }
 public int size() {
   return map.size();
 }
 public boolean isEmpty() {
   return map.isEmpty();
 }
 public boolean containsKey(Object key) {
   IdentityKey k = new IdentityKey(key);
   return map.containsKey(k);
 }
 public boolean containsValue(Object val) {
   return map.containsValue(val);
 }
 public Object get(Object key) {
   IdentityKey k = new IdentityKey(key);
   return map.get(k);
 }
 public Object put(Object key, Object value) {
   dirty = true;
   return map.put( new IdentityKey(key), value );
 }
 public Object remove(Object key) {
   dirty = true;
   IdentityKey k = new IdentityKey(key);
   return map.remove(k);
 }
 public void putAll(Map otherMap) {
   Iterator iter = otherMap.entrySet().iterator();
   while ( iter.hasNext() ) {
     Map.Entry me = (Map.Entry) iter.next();
     put( me.getKey(), me.getValue() );
   }
 }
 public void clear() {
   dirty = true;
   entryArray = null;
   map.clear();
 }
 public Set keySet() {
   // would need an IdentitySet for this!
   throw new UnsupportedOperationException();
 }
 public Collection values() {
   return map.values();
 }
 public Set entrySet() {
   Set set = new HashSet( map.size() );
   Iterator iter = map.entrySet().iterator();
   while ( iter.hasNext() ) {
     Map.Entry me = (Map.Entry) iter.next();
     set.add( new IdentityMapEntry( ( (IdentityKey) me.getKey() ).key, me.getValue() ) );
   }
   return set;
 }
 public List entryList() {
   ArrayList list = new ArrayList( map.size() );
   Iterator iter = map.entrySet().iterator();
   while ( iter.hasNext() ) {
     Map.Entry me = (Map.Entry) iter.next();
     list.add( new IdentityMapEntry( ( (IdentityKey) me.getKey() ).key, me.getValue() ) );
   }
   return list;
 }
 public Map.Entry[] entryArray() {
   if (dirty) {
     entryArray = new Map.Entry[ map.size() ];
     Iterator iter = map.entrySet().iterator();
     int i=0;
     while ( iter.hasNext() ) {
       Map.Entry me = (Map.Entry) iter.next();
       entryArray[i++] = new IdentityMapEntry( ( (IdentityKey) me.getKey() ).key, me.getValue() );
     }
     dirty = false;
   }
   return entryArray;
 }
 /**
  * Workaround for a JDK 1.4.1 bug where IdentityHashMaps are not
  * correctly deserialized.
  *
  * @param map
  * @return Object
  */
 public static Object serialize(Map map) {
   return ( (IdentityMap) map ).map;
 }
 /**
  * Workaround for a JDK 1.4.1 bug where IdentityHashMaps are not
  * correctly deserialized.
  *
  * @param o
  * @return Map
  */
 public static Map deserialize(Object o) {
   return new IdentityMap( (Map) o );
 }
 
 public String toString() {
   return map.toString();
 }
 public static Map invert(Map map) {
   Map result = instantiate( map.size() );
   Iterator iter = map.entrySet().iterator();
   while ( iter.hasNext() ) {
     Map.Entry me = (Map.Entry) iter.next();
     result.put( me.getValue(), me.getKey() );
   }
   return result;
 }
 static final class KeyIterator implements Iterator {
   private KeyIterator(Iterator iter) {
     identityKeyIterator = iter;
   }
   private final Iterator identityKeyIterator;
   public boolean hasNext() {
     return identityKeyIterator.hasNext();
   }
   public Object next() {
     return ( (IdentityKey) identityKeyIterator.next() ).key;
   }
   public void remove() {
     throw new UnsupportedOperationException();
   }
 }

}</source>

A memory-efficient hash map.

   <source lang="java">

/*

* Copyright 2009 Google Inc.
* 
* 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.
*/

import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**

* A memory-efficient hash map.
* 
* @param <K> the key type
* @param <V> the value type
*/

public class HashMap<K, V> implements Map<K, V>, Serializable {

 /**
  * In the interest of memory-savings, we start with the smallest feasible
  * power-of-two table size that can hold three items without rehashing. If we
  * started with a size of 2, we"d have to expand as soon as the second item
  * was added.
  */
 private static final int INITIAL_TABLE_SIZE = 4;
 private class EntryIterator implements Iterator<Entry<K, V>> {
   private int index = 0;
   private int last = -1;
   {
     advanceToItem();
   }
   public boolean hasNext() {
     return index < keys.length;
   }
   public Entry<K, V> next() {
     if (!hasNext()) {
       throw new NoSuchElementException();
     }
     last = index;
     Entry<K, V> toReturn = new HashEntry(index++);
     advanceToItem();
     return toReturn;
   }
   public void remove() {
     if (last < 0) {
       throw new IllegalStateException();
     }
     internalRemove(last);
     if (keys[last] != null) {
       index = last;
     }
     last = -1;
   }
   private void advanceToItem() {
     for (; index < keys.length; ++index) {
       if (keys[index] != null) {
         return;
       }
     }
   }
 }
 private class EntrySet extends AbstractSet<Entry<K, V>> {
   @Override
   public boolean add(Entry<K, V> entry) {
     boolean result = !HashMap.this.containsKey(entry.getKey());
     HashMap.this.put(entry.getKey(), entry.getValue());
     return result;
   }
   @Override
   public boolean addAll(Collection<? extends Entry<K, V>> c) {
     HashMap.this.ensureSizeFor(size() + c.size());
     return super.addAll(c);
   }
   @Override
   public void clear() {
     HashMap.this.clear();
   }
   @Override
   @SuppressWarnings("unchecked")
   public boolean contains(Object o) {
     if (!(o instanceof Entry)) {
       return false;
     }
     Entry<K, V> entry = (Entry<K, V>) o;
     V value = HashMap.this.get(entry.getKey());
     return HashMap.this.valueEquals(value, entry.getValue());
   }
   @Override
   public int hashCode() {
     return HashMap.this.hashCode();
   }
   @Override
   public Iterator<java.util.Map.Entry<K, V>> iterator() {
     return new EntryIterator();
   }
   @Override
   @SuppressWarnings("unchecked")
   public boolean remove(Object o) {
     if (!(o instanceof Entry)) {
       return false;
     }
     Entry<K, V> entry = (Entry<K, V>) o;
     int index = findKey(entry.getKey());
     if (index >= 0 && valueEquals(values[index], entry.getValue())) {
       internalRemove(index);
       return true;
     }
     return false;
   }
   @Override
   public boolean removeAll(Collection<?> c) {
     boolean didRemove = false;
     for (Object o : c) {
       didRemove |= remove(o);
     }
     return didRemove;
   }
   @Override
   public int size() {
     return HashMap.this.size;
   }
 }
 private class HashEntry implements Entry<K, V> {
   private final int index;
   public HashEntry(int index) {
     this.index = index;
   }
   @Override
   @SuppressWarnings("unchecked")
   public boolean equals(Object o) {
     if (!(o instanceof Entry)) {
       return false;
     }
     Entry<K, V> entry = (Entry<K, V>) o;
     return keyEquals(getKey(), entry.getKey())
         && valueEquals(getValue(), entry.getValue());
   }
   @SuppressWarnings("unchecked")
   public K getKey() {
     return (K) unmaskNullKey(keys[index]);
   }
   @SuppressWarnings("unchecked")
   public V getValue() {
     return (V) values[index];
   }
   @Override
   public int hashCode() {
     return keyHashCode(getKey()) ^ valueHashCode(getValue());
   }
   @SuppressWarnings("unchecked")
   public V setValue(V value) {
     V previous = (V) values[index];
     values[index] = value;
     return previous;
   }
   @Override
   public String toString() {
     return getKey() + "=" + getValue();
   }
 }
 private class KeyIterator implements Iterator<K> {
   private int index = 0;
   private int last = -1;
   {
     advanceToItem();
   }
   public boolean hasNext() {
     return index < keys.length;
   }
   @SuppressWarnings("unchecked")
   public K next() {
     if (!hasNext()) {
       throw new NoSuchElementException();
     }
     last = index;
     Object toReturn = unmaskNullKey(keys[index++]);
     advanceToItem();
     return (K) toReturn;
   }
   public void remove() {
     if (last < 0) {
       throw new IllegalStateException();
     }
     internalRemove(last);
     if (keys[last] != null) {
       index = last;
     }
     last = -1;
   }
   private void advanceToItem() {
     for (; index < keys.length; ++index) {
       if (keys[index] != null) {
         return;
       }
     }
   }
 }
 private class KeySet extends AbstractSet<K> {
   @Override
   public void clear() {
     HashMap.this.clear();
   }
   @Override
   public boolean contains(Object o) {
     return HashMap.this.containsKey(o);
   }
   @Override
   public int hashCode() {
     int result = 0;
     for (int i = 0; i < keys.length; ++i) {
       Object key = keys[i];
       if (key != null) {
         result += keyHashCode(unmaskNullKey(key));
       }
     }
     return result;
   }
   @Override
   public Iterator<K> iterator() {
     return new KeyIterator();
   }
   @Override
   public boolean remove(Object o) {
     int index = findKey(o);
     if (index >= 0) {
       internalRemove(index);
       return true;
     }
     return false;
   }
   @Override
   public boolean removeAll(Collection<?> c) {
     boolean didRemove = false;
     for (Object o : c) {
       didRemove |= remove(o);
     }
     return didRemove;
   }
   @Override
   public int size() {
     return HashMap.this.size;
   }
 }
 private class ValueIterator implements Iterator<V> {
   private int index = 0;
   private int last = -1;
   {
     advanceToItem();
   }
   public boolean hasNext() {
     return index < keys.length;
   }
   @SuppressWarnings("unchecked")
   public V next() {
     if (!hasNext()) {
       throw new NoSuchElementException();
     }
     last = index;
     Object toReturn = values[index++];
     advanceToItem();
     return (V) toReturn;
   }
   public void remove() {
     if (last < 0) {
       throw new IllegalStateException();
     }
     internalRemove(last);
     if (keys[last] != null) {
       index = last;
     }
     last = -1;
   }
   private void advanceToItem() {
     for (; index < keys.length; ++index) {
       if (keys[index] != null) {
         return;
       }
     }
   }
 }
 private class Values extends AbstractCollection<V> {
   @Override
   public void clear() {
     HashMap.this.clear();
   }
   @Override
   public boolean contains(Object o) {
     return HashMap.this.containsValue(o);
   }
   @Override
   public int hashCode() {
     int result = 0;
     for (int i = 0; i < keys.length; ++i) {
       if (keys[i] != null) {
         result += valueHashCode(values[i]);
       }
     }
     return result;
   }
   @Override
   public Iterator<V> iterator() {
     return new ValueIterator();
   }
   @Override
   public boolean remove(Object o) {
     if (o == null) {
       for (int i = 0; i < keys.length; ++i) {
         if (keys[i] != null && values[i] == null) {
           internalRemove(i);
           return true;
         }
       }
     } else {
       for (int i = 0; i < keys.length; ++i) {
         if (valueEquals(values[i], o)) {
           internalRemove(i);
           return true;
         }
       }
     }
     return false;
   }
   @Override
   public boolean removeAll(Collection<?> c) {
     boolean didRemove = false;
     for (Object o : c) {
       didRemove |= remove(o);
     }
     return didRemove;
   }
   @Override
   public int size() {
     return HashMap.this.size;
   }
 }
 private static final Object NULL_KEY = new Serializable() {
   Object readResolve() {
     return NULL_KEY;
   }
 };
 static Object maskNullKey(Object k) {
   return (k == null) ? NULL_KEY : k;
 }
 static Object unmaskNullKey(Object k) {
   return (k == NULL_KEY) ? null : k;
 }
 /**
  * Backing store for all the keys; transient due to custom serialization.
  * Default access to avoid synthetic accessors from inner classes.
  */
 transient Object[] keys;
 /**
  * Number of pairs in this set; transient due to custom serialization. Default
  * access to avoid synthetic accessors from inner classes.
  */
 transient int size = 0;
 /**
  * Backing store for all the values; transient due to custom serialization.
  * Default access to avoid synthetic accessors from inner classes.
  */
 transient Object[] values;
 public HashMap() {
   initTable(INITIAL_TABLE_SIZE);
 }
 public HashMap(Map<? extends K, ? extends V> m) {
   int newCapacity = INITIAL_TABLE_SIZE;
   int expectedSize = m.size();
   while (newCapacity * 3 < expectedSize * 4) {
     newCapacity <<= 1;
   }
   initTable(newCapacity);
   internalPutAll(m);
 }
 public void clear() {
   initTable(INITIAL_TABLE_SIZE);
   size = 0;
 }
 public boolean containsKey(Object key) {
   return findKey(key) >= 0;
 }
 public boolean containsValue(Object value) {
   if (value == null) {
     for (int i = 0; i < keys.length; ++i) {
       if (keys[i] != null && values[i] == null) {
         return true;
       }
     }
   } else {
     for (Object existing : values) {
       if (valueEquals(existing, value)) {
         return true;
       }
     }
   }
   return false;
 }
 public Set<Entry<K, V>> entrySet() {
   return new EntrySet();
 }
 @Override
 @SuppressWarnings("unchecked")
 public boolean equals(Object o) {
   if (!(o instanceof Map)) {
     return false;
   }
   Map<K, V> other = (Map<K, V>) o;
   return entrySet().equals(other.entrySet());
 }
 @SuppressWarnings("unchecked")
 public V get(Object key) {
   int index = findKey(key);
   return (index < 0) ? null : (V) values[index];
 }
 @Override
 public int hashCode() {
   int result = 0;
   for (int i = 0; i < keys.length; ++i) {
     Object key = keys[i];
     if (key != null) {
       result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]);
     }
   }
   return result;
 }
 public boolean isEmpty() {
   return size == 0;
 }
 public Set<K> keySet() {
   return new KeySet();
 }
 @SuppressWarnings("unchecked")
 public V put(K key, V value) {
   ensureSizeFor(size + 1);
   int index = findKeyOrEmpty(key);
   if (keys[index] == null) {
     ++size;
     keys[index] = maskNullKey(key);
     values[index] = value;
     return null;
   } else {
     Object previousValue = values[index];
     values[index] = value;
     return (V) previousValue;
   }
 }
 public void putAll(Map<? extends K, ? extends V> m) {
   ensureSizeFor(size + m.size());
   internalPutAll(m);
 }
 @SuppressWarnings("unchecked")
 public V remove(Object key) {
   int index = findKey(key);
   if (index < 0) {
     return null;
   }
   Object previousValue = values[index];
   internalRemove(index);
   return (V) previousValue;
 }
 public int size() {
   return size;
 }
 @Override
 public String toString() {
   if (size == 0) {
     return "{}";
   }
   StringBuilder buf = new StringBuilder(32 * size());
   buf.append("{");
   boolean needComma = false;
   for (int i = 0; i < keys.length; ++i) {
     Object key = keys[i];
     if (key != null) {
       if (needComma) {
         buf.append(",").append(" ");
       }
       key = unmaskNullKey(key);
       Object value = values[i];
       buf.append(key == this ? "(this Map)" : key).append("=").append(
           value == this ? "(this Map)" : value);
       needComma = true;
     }
   }
   buf.append("}");
   return buf.toString();
 }
 public Collection<V> values() {
   return new Values();
 }
 /**
  * Adapted from {@link org.apache.rumons.collections.map.AbstractHashedMap}.
  */
 @SuppressWarnings("unchecked")
 protected void doReadObject(ObjectInputStream in) throws IOException,
     ClassNotFoundException {
   int capacity = in.readInt();
   initTable(capacity);
   int items = in.readInt();
   for (int i = 0; i < items; i++) {
     Object key = in.readObject();
     Object value = in.readObject();
     put((K) key, (V) value);
   }
 }
 /**
  * Adapted from {@link org.apache.rumons.collections.map.AbstractHashedMap}.
  */
 protected void doWriteObject(ObjectOutputStream out) throws IOException {
   out.writeInt(keys.length);
   out.writeInt(size);
   for (int i = 0; i < keys.length; ++i) {
     Object key = keys[i];
     if (key != null) {
       out.writeObject(unmaskNullKey(key));
       out.writeObject(values[i]);
     }
   }
 }
 /**
  * Returns whether two keys are equal for the purposes of this set.
  */
 protected boolean keyEquals(Object a, Object b) {
   return (a == null) ? (b == null) : a.equals(b);
 }
 /**
  * Returns the hashCode for a key.
  */
 protected int keyHashCode(Object k) {
   return (k == null) ? 0 : k.hashCode();
 }
 /**
  * Returns whether two values are equal for the purposes of this set.
  */
 protected boolean valueEquals(Object a, Object b) {
   return (a == null) ? (b == null) : a.equals(b);
 }
 /**
  * Returns the hashCode for a value.
  */
 protected int valueHashCode(Object v) {
   return (v == null) ? 0 : v.hashCode();
 }
 /**
  * Ensures the map is large enough to contain the specified number of entries.
  * Default access to avoid synthetic accessors from inner classes.
  */
 void ensureSizeFor(int expectedSize) {
   if (keys.length * 3 >= expectedSize * 4) {
     return;
   }
   int newCapacity = keys.length << 1;
   while (newCapacity * 3 < expectedSize * 4) {
     newCapacity <<= 1;
   }
   Object[] oldKeys = keys;
   Object[] oldValues = values;
   initTable(newCapacity);
   for (int i = 0; i < oldKeys.length; ++i) {
     Object k = oldKeys[i];
     if (k != null) {
       int newIndex = getKeyIndex(unmaskNullKey(k));
       while (keys[newIndex] != null) {
         if (++newIndex == keys.length) {
           newIndex = 0;
         }
       }
       keys[newIndex] = k;
       values[newIndex] = oldValues[i];
     }
   }
 }
 /**
  * Returns the index in the key table at which a particular key resides, or -1
  * if the key is not in the table. Default access to avoid synthetic accessors
  * from inner classes.
  */
 int findKey(Object k) {
   int index = getKeyIndex(k);
   while (true) {
     Object existing = keys[index];
     if (existing == null) {
       return -1;
     }
     if (keyEquals(k, unmaskNullKey(existing))) {
       return index;
     }
     if (++index == keys.length) {
       index = 0;
     }
   }
 }
 /**
  * Returns the index in the key table at which a particular key resides, or
  * the index of an empty slot in the table where this key should be inserted
  * if it is not already in the table. Default access to avoid synthetic
  * accessors from inner classes.
  */
 int findKeyOrEmpty(Object k) {
   int index = getKeyIndex(k);
   while (true) {
     Object existing = keys[index];
     if (existing == null) {
       return index;
     }
     if (keyEquals(k, unmaskNullKey(existing))) {
       return index;
     }
     if (++index == keys.length) {
       index = 0;
     }
   }
 }
 /**
  * Removes the entry at the specified index, and performs internal management
  * to make sure we don"t wind up with a hole in the table. Default access to
  * avoid synthetic accessors from inner classes.
  */
 void internalRemove(int index) {
   keys[index] = null;
   values[index] = null;
   --size;
   plugHole(index);
 }
 private int getKeyIndex(Object k) {
   int h = keyHashCode(k);
   // Copied from Apache"s AbstractHashedMap; prevents power-of-two collisions.
   h += ~(h << 9);
   h ^= (h >>> 14);
   h += (h << 4);
   h ^= (h >>> 10);
   // Power of two trick.
   return h & (keys.length - 1);
 }
 private void initTable(int capacity) {
   keys = new Object[capacity];
   values = new Object[capacity];
 }
 private void internalPutAll(Map<? extends K, ? extends V> m) {
   for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
     K key = entry.getKey();
     V value = entry.getValue();
     int index = findKeyOrEmpty(key);
     if (keys[index] == null) {
       ++size;
       keys[index] = maskNullKey(key);
       values[index] = value;
     } else {
       values[index] = value;
     }
   }
 }
 /**
  * Tricky, we left a hole in the map, which we have to fill. The only way to
  * do this is to search forwards through the map shuffling back values that
  * match this index until we hit a null.
  */
 private void plugHole(int hole) {
   int index = hole + 1;
   if (index == keys.length) {
     index = 0;
   }
   while (keys[index] != null) {
     int targetIndex = getKeyIndex(unmaskNullKey(keys[index]));
     if (hole < index) {
       /*
        * "Normal" case, the index is past the hole and the "bad range" is from
        * hole (exclusive) to index (inclusive).
        */
       if (!(hole < targetIndex && targetIndex <= index)) {
         // Plug it!
         keys[hole] = keys[index];
         values[hole] = values[index];
         keys[index] = null;
         values[index] = null;
         hole = index;
       }
     } else {
       /*
        * "Wrapped" case, the index is before the hole (we"ve wrapped) and the
        * "good range" is from index (exclusive) to hole (inclusive).
        */
       if (index < targetIndex && targetIndex <= hole) {
         // Plug it!
         keys[hole] = keys[index];
         values[hole] = values[index];
         keys[index] = null;
         values[index] = null;
         hole = index;
       }
     }
     if (++index == keys.length) {
       index = 0;
     }
   }
 }
 private void readObject(ObjectInputStream in) throws IOException,
     ClassNotFoundException {
   in.defaultReadObject();
   doReadObject(in);
 }
 private void writeObject(ObjectOutputStream out) throws IOException {
   out.defaultWriteObject();
   doWriteObject(out);
 }

}</source>

An IdentityMap that uses reference-equality instead of object-equality

   <source lang="java">

/*

* Copyright 2005 Ralf Joachim
*
* 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.
*/

import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**

* An IdentityMap that uses reference-equality instead of object-equality. According
* to its special function it violates some design contracts of the Map
* interface.
* 
* @author 
* @version $Revision: 7491 $ $Date: 2006-04-13 10:49:49 -0600 (Thu, 13 Apr 2006) $
* @since 0.9.9
*/
class IdentitySet implements Set {
   //--------------------------------------------------------------------------
   /** Default number of buckets. */
   private static final int    DEFAULT_CAPACITY = 17;
   
   /** Default load factor. */
   private static final float  DEFAULT_LOAD = 0.75f;
   
   /** Default number of entries. */
   private static final int    DEFAULT_ENTRIES = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD);
   
   /** Default factor to increment capacity. */
   private static final int    DEFAULT_INCREMENT = 2;
   
   /** First prime number to check is 3 as we prevent 2 by design. */
   private static final int    FIRST_PRIME_TO_CHECK = 3;
   
   //--------------------------------------------------------------------------
   /** Number of buckets. */
   private int                     _capacity;
   
   /** Maximum number of entries before rehashing. */
   private int                     _maximum;
   /** Buckets. */
   private Entry[]                 _buckets;
   /** Number of map entries. */
   private int                     _entries = 0;
   //--------------------------------------------------------------------------
   /**
    * Construct a set with default capacity.
    */
   public IdentitySet() {
       _capacity = DEFAULT_CAPACITY;
       _maximum = DEFAULT_ENTRIES;
       _buckets = new Entry[DEFAULT_CAPACITY];
   }
   
   /**
    * Construct a set with given capacity.
    * 
    * @param  capacity     The capacity of entries this set should be initialized with.
    */
   public IdentitySet(final int capacity) {
       _capacity = capacity;
       _maximum = (int) (capacity * DEFAULT_LOAD);
       _buckets = new Entry[capacity];
   }
   
   /**
    * {@inheritDoc}
    * @see java.util.Collection#clear()
    */
   public void clear() {
       _capacity = DEFAULT_CAPACITY;
       _maximum = DEFAULT_ENTRIES;
       _buckets = new Entry[DEFAULT_CAPACITY];
       _entries = 0;
   }
   /**
    * {@inheritDoc}
    * @see java.util.Collection#size()
    */
   public int size() { return _entries; }
   /**
    * {@inheritDoc}
    * @see java.util.Collection#isEmpty()
    */
   public boolean isEmpty() { return (_entries == 0); }
   /**
    * {@inheritDoc}
    * @see java.util.Collection#add(java.lang.Object)
    */
   public boolean add(final Object key) {
       int hash = System.identityHashCode(key);
       int index = hash % _capacity;
       if (index < 0) { index = -index; }
       Entry entry = _buckets[index];
       Entry prev = null;
       while (entry != null) {
           if (entry.getKey() == key) {
               // There is already a mapping for this key.
               return false;
           }
           prev = entry;
           entry = entry.getNext();
       }
       if (prev == null) {
           // There is no previous entry in this bucket.
           _buckets[index] = new Entry(key, hash);
       } else {
           // Next entry is empty so we have no mapping for this key.
           prev.setNext(new Entry(key, hash));
       }
       _entries++;
       if (_entries > _maximum) { rehash(); }
       return true;
   }
   /**
    * Rehash the map into a new array with increased capacity.
    */
   private void rehash() {
       long nextCapacity = _capacity * DEFAULT_INCREMENT;
       if (nextCapacity > Integer.MAX_VALUE) { return; }
       nextCapacity = nextPrime(nextCapacity);
       if (nextCapacity > Integer.MAX_VALUE) { return; }
       int newCapacity = (int) nextCapacity;
       Entry[] newBuckets = new Entry[newCapacity];
       Entry entry = null;
       Entry temp = null;
       Entry next = null;
       int newIndex = 0;
       for (int index = 0; index < _capacity; index++) {
           entry = _buckets[index];
           while (entry != null) {
               next = entry.getNext();
               newIndex = entry.getHash() % newCapacity;
               if (newIndex < 0) { newIndex = -newIndex; }
               temp = newBuckets[newIndex];
               if (temp == null) {
                   // First entry of the bucket.
                   entry.setNext(null);
               } else {
                   // Hook entry into beginning of the buckets chain.
                   entry.setNext(temp);
               }
               newBuckets[newIndex] = entry;
               entry = next;
           }
       }
       _capacity = newCapacity;
       _maximum = (int) (newCapacity * DEFAULT_LOAD);
       _buckets = newBuckets;
   }
   /**
    * Find next prime number greater than minimum.
    * 
    * @param  minimum  The minimum (exclusive) value of the next prime number.
    * @return The next prime number greater than minimum.
    */
   private long nextPrime(final long minimum) {
       long candidate = ((minimum + 1) / 2) * 2 + 1;
       while (!isPrime(candidate)) { candidate += 2; }
       return candidate;
   }
   /**
    * Check for prime number.
    * 
    * @param  candidate  Number to be checked for being a prime number.
    * @return true if the given number is a prime number
    *         false otherwise.
    */
   private boolean isPrime(final long candidate) {
       if ((candidate / 2) * 2 == candidate) { return false; }
       long stop = candidate / 2;
       for (long i = FIRST_PRIME_TO_CHECK; i < stop; i += 2) {
           if ((candidate / i) * i == candidate) { return false; }
       }
       return true;
   }
   /**
    * {@inheritDoc}
    * @see java.util.Collection#contains(java.lang.Object)
    */
   public boolean contains(final Object key) {
       int hash = System.identityHashCode(key);
       int index = hash % _capacity;
       if (index < 0) { index = -index; }
       Entry entry = _buckets[index];
       while (entry != null) {
           if (entry.getKey() == key) { return true; }
           entry = entry.getNext();
       }
       return false;
   }
   /**
    * {@inheritDoc}
    * @see java.util.Collection#remove(java.lang.Object)
    */
   public boolean remove(final Object key) {
       int hash = System.identityHashCode(key);
       int index = hash % _capacity;
       if (index < 0) { index = -index; }
       Entry entry = _buckets[index];
       Entry prev = null;
       while (entry != null) {
           if (entry.getKey() == key) {
               // Found the entry.
               if (prev == null) {
                   // First element in bucket matches.
                   _buckets[index] = entry.getNext();
               } else {
                   // Remove the entry from the chain.
                   prev.setNext(entry.getNext());
               }
               _entries--;
               return true;
           }
           prev = entry;
           entry = entry.getNext();
       }
       return false;
   }
   
   /**
    * {@inheritDoc}
    * @see java.util.Collection#iterator()
    */
   public Iterator iterator() {
       return new IdentityIterator();
   }
   
   /**
    * {@inheritDoc}
    * @see java.util.Collection#toArray()
    */
   public Object[] toArray() {
       Object[] result = new Object[_entries];
       int j = 0;
       for (int i = 0; i < _capacity; i++) {
           Entry entry = _buckets[i];
           while (entry != null) {
               result[j++] = entry.getKey();
               entry = entry.getNext();
           }
       }
       
       return result;
   }
   
   /**
    * {@inheritDoc}
    * @see java.util.Collection#toArray(java.lang.Object[])
    */
   public Object[] toArray(final Object[] a) {
       Object[] result = a;
       if (result.length < _entries) {
           result = (Object[]) java.lang.reflect.Array.newInstance(
                   result.getClass().getComponentType(), _entries);
       }
       
       int j = 0;
       for (int i = 0; i < _capacity; i++) {
           Entry entry = _buckets[i];
           while (entry != null) {
               result[j++] = entry.getKey();
               entry = entry.getNext();
           }
       }
       
       while (j < result.length) {
           result[j++] = null;
       }
       
       return result;
   }
   
   /**
    * In contrast with the design contract of the Set interface this method
    * has not been implemented and throws a UnsupportedOperationException.
    * 
    * {@inheritDoc}
    * @see java.util.Set#containsAll
    */
   public boolean containsAll(final Collection c) {
       throw new UnsupportedOperationException();
   }
   
   /**
    * This optional method has not been implemented for IdentitySet instead
    * it throws a UnsupportedOperationException as defined in the
    * Set interface.
    * 
    * {@inheritDoc}
    * @see java.util.Set#addAll
    */
   public boolean addAll(final Collection c) {
       throw new UnsupportedOperationException();
   }
   
   /**
    * This optional method has not been implemented for IdentitySet instead
    * it throws a UnsupportedOperationException as defined in the
    * Set interface.
    * 
    * {@inheritDoc}
    * @see java.util.Set#removeAll
    */
   public boolean removeAll(final Collection c) {
       throw new UnsupportedOperationException();
   }
   
   /**
    * This optional method has not been implemented for IdentitySet instead
    * it throws a UnsupportedOperationException as defined in the
    * Set interface.
    * 
    * {@inheritDoc}
    * @see java.util.Set#retainAll
    */
   public boolean retainAll(final Collection c) {
       throw new UnsupportedOperationException();
   }
   
   //--------------------------------------------------------------------------
   /**
    * An entry of the IdentitySet.
    */
   public final class Entry {
       /** Key of entry. */
       private Object  _key;
       
       /** Identity hashcode of key. */
       private int     _hash;
       
       /** Reference to next entry. */
       private Entry   _next = null;
       /**
        * Construct an entry.
        * 
        * @param key    Key of entry.
        * @param hash   Identity hashcode of key.
        */
       public Entry(final Object key, final int hash) {
           _key = key;
           _hash = hash;
       }
       /**
        * Get key of entry.
        *
        * @return Key of entry.
        */
       public Object getKey() { return _key; }
       /**
        * Get identity hashcode of key.
        *
        * @return Identity hashcode of key.
        */
       public int getHash() { return _hash; }
       /**
        * Set reference to next entry.
        *
        * @param  next     New reference to next entry.
        */
       public void setNext(final Entry next) { _next = next; }
       /**
        * Get reference to next entry.
        *
        * @return Reference to next entry.
        */
       public Entry getNext() { return _next; }
   }
   //--------------------------------------------------------------------------
   /**
    * An iterator over all entries of the IdentitySet.
    */
   private class IdentityIterator implements Iterator {
       /** Index of the current bucket. */
       private int     _index = 0; 
       
       /** The next entry to be returned. null when there is none. */
       private Entry   _next = _buckets[0];
       /**
        * Construct a iterator over all entries of the IdentitySet.
        */
       public IdentityIterator() {
           if (_entries > 0) {
               while ((_next == null) && (++_index < _capacity)) {
                   _next = _buckets[_index];
               }
           }
       }
       /**
        * {@inheritDoc}
        * @see java.util.Iterator#hasNext()
        */
       public boolean hasNext() {
           return (_next != null);
       }
       /**
        * {@inheritDoc}
        * @see java.util.Iterator#next()
        */
       public Object next() {
           Entry entry = _next;
           if (entry == null) { throw new NoSuchElementException(); }
           
           _next = entry.getNext();
           while ((_next == null) && (++_index < _capacity)) {
               _next = _buckets[_index];
           }
           
           return entry.getKey();
       }
       
       /**
        * This optional method is not implemented for IdentityIterator
        * instead it throws a UnsupportedOperationException as defined
        * in the Iterator interface.
        * 
        * @see java.util.Iterator#remove()
        */
       public void remove() {
           throw new UnsupportedOperationException();
       }
   }
   
   //--------------------------------------------------------------------------

}</source>

A simple hashmap from keys to integers

   <source lang="java">

/*

* Copyright (c) 2001-2008 Caucho Technology, Inc.  All rights reserved.
*
* The Apache Software License, Version 1.1
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in
*    the documentation and/or other materials provided with the
*    distribution.
*
* 3. The end-user documentation included with the redistribution, if
*    any, must include the following acknowlegement:
*       "This product includes software developed by the
*        Caucho Technology (http://www.caucho.ru/)."
*    Alternately, this acknowlegement may appear in the software itself,
*    if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "Burlap", "Resin", and "Caucho" must not be used to
*    endorse or promote products derived from this software without prior
*    written permission. For written permission, please contact
*    info@caucho.ru.
*
* 5. Products derived from this software may not be called "Resin"
*    nor may "Resin" appear in their names without prior written
*    permission of Caucho Technology.
*
* THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED.  IN NO EVENT SHALL CAUCHO TECHNOLOGY OR ITS CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
* OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
* OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
* IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* @author Scott Ferguson
*/

/**

* The IntMap provides a simple hashmap from keys to integers.  The API is
* an abbreviation of the HashMap collection API.
*
* The convenience of IntMap is avoiding all the silly wrapping of
* integers.
*/

public class IntMap {

 /**
  * Encoding of a null entry.  Since NULL is equal to Integer.MIN_VALUE, 
  * it"s impossible to distinguish between the two.
  */
 public final static int NULL = 0xdeadbeef; // Integer.MIN_VALUE + 1;
 private static final Object DELETED = new Object();
 private Object []_keys;
 private int []_values;
 private int _size;
 private int _mask;
 /**
  * Create a new IntMap.  Default size is 16.
  */
 public IntMap()
 {
   _keys = new Object[256];
   _values = new int[256];
   _mask = _keys.length - 1;
   _size = 0;
 }
 /**
  * Clear the hashmap.
  */
 public void clear()
 {
   Object []keys = _keys;
   int []values = _values;
   for (int i = keys.length - 1; i >= 0; i--) {
     keys[i] = null;
     values[i] = 0;
   }
   _size = 0;
 }
 /**
  * Returns the current number of entries in the map.
  */
 public int size()
 {
   return _size;
 }
 /**
  * Puts a new value in the property table with the appropriate flags
  */
 public int get(Object key)
 {
   int mask = _mask;
   int hash = key.hashCode() % mask & mask;
   Object []keys = _keys;
   while (true) {
     Object mapKey = keys[hash];
     if (mapKey == null)
       return NULL;
     else if (mapKey == key || mapKey.equals(key))
       return _values[hash];
     hash = (hash + 1) % mask;
   }
 }
 /**
  * Expands the property table
  */
 private void resize(int newSize)
 {
   Object []newKeys = new Object[newSize];
   int []newValues = new int[newSize];
   int mask = _mask = newKeys.length - 1;
   Object []keys = _keys;
   int values[] = _values;
   for (int i = keys.length - 1; i >= 0; i--) {
     Object key = keys[i];
     if (key == null || key == DELETED)
       continue;
     int hash = key.hashCode() % mask & mask;
     while (true) {
       if (newKeys[hash] == null) {
         newKeys[hash] = key;
         newValues[hash] = values[i];
         break;
       }
       hash = (hash + 1) % mask;
     }
   }
   _keys = newKeys;
   _values = newValues;
 }
 /**
  * Puts a new value in the property table with the appropriate flags
  */
 public int put(Object key, int value)
 {
   int mask = _mask;
   int hash = key.hashCode() % mask & mask;
   Object []keys = _keys;
   while (true) {
     Object testKey = keys[hash];
     if (testKey == null || testKey == DELETED) {
       keys[hash] = key;
       _values[hash] = value;
       _size++;
       if (keys.length <= 4 * _size)
         resize(4 * keys.length);
       return NULL;
     }
     else if (key != testKey && ! key.equals(testKey)) {
       hash = (hash + 1) % mask;
       continue;
     }
     else {
       int old = _values[hash];
       _values[hash] = value;
       return old;
     }
   }
 }
 /**
  * Deletes the entry.  Returns true if successful.
  */
 public int remove(Object key)
 {
   int mask = _mask;
   int hash = key.hashCode() % mask & mask;
   while (true) {
     Object mapKey = _keys[hash];
     if (mapKey == null)
       return NULL;
     else if (mapKey == key) {
       _keys[hash] = DELETED;
       _size--;
       return _values[hash];
     }
     hash = (hash + 1) % mask;
   }
 }
 public String toString()
 {
   StringBuffer sbuf = new StringBuffer();
   sbuf.append("IntMap[");
   boolean isFirst = true;
   for (int i = 0; i <= _mask; i++) {
     if (_keys[i] != null && _keys[i] != DELETED) {
       if (! isFirst)
         sbuf.append(", ");
       isFirst = false;
       sbuf.append(_keys[i]);
       sbuf.append(":");
       sbuf.append(_values[i]);
     }
   }
   sbuf.append("]");
   return sbuf.toString();
 }

}</source>

CaseBlindHashMap - a HashMap extension, using Strings as key values.

   <source lang="java">

/**********************************************************************************

*
* Copyright (c) 2003, 2004 The Regents of the University of Michigan, Trustees of Indiana University,
*                  Board of Trustees of the Leland Stanford, Jr., University, and The MIT Corporation
*
* Licensed under the Educational Community License Version 1.0 (the "License");
* By obtaining, using and/or copying this Original Work, you agree that you have read,
* understand, and will comply with the terms and conditions of the Educational Community License.
* You may obtain a copy of the License at:
*
*      http://cvs.sakaiproject.org/licenses/license_1_0.html
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
* INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
* AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
**********************************************************************************/

/*

Copyright (c) 2000-2003 Board of Trustees of Leland Stanford Jr. University,
all rights reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
STANFORD UNIVERSITY BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Except as contained in this notice, the name of Stanford University shall not
be used in advertising or otherwise to promote the sale, use or other dealings
in this Software without prior written authorization from Stanford University.
*/

import java.util.HashMap; import java.util.Iterator; import java.util.Set; /**

* CaseBlindHashMap - a HashMap extension, using Strings as key
* values.
* 
* Internally, keys are case insensitive: ABC = abc.
* 
* Two methods have been added to facilitate working with Sets of key strings.
* See stringKeySet() and stringKeyIterator().
*/

public class CaseBlindHashMap extends HashMap {

 /**
  * Constructors
  */
 public CaseBlindHashMap() {
   super();
 }
 public CaseBlindHashMap(CaseBlindHashMap map) {
   super(map);
 }
 public CaseBlindHashMap(int initCap) {
   super(initCap);
 }
 public CaseBlindHashMap(int initCap, float loadFactor) {
   super(initCap, loadFactor);
 }
 /*
  * Extensions
  */
 /**
  * Get the set of keys contained in this map. Keys values are returned as
  * simple Strings (not the CaseBlindStrings
  * used internally).
  * 
  * This is accopmlished by making a copy of the original map - modifications
  * made to this copy are not reflected in the original.
  * 
  * @return The set of keys
  */
 public Set stringKeySet() {
   Iterator iterator = super.keySet().iterator();
   HashMap stringKeys = new HashMap();
   while (iterator.hasNext()) {
     String key = ((CaseBlindString) iterator.next()).toString();
     stringKeys.put(key, get(key));
   }
   return stringKeys.keySet();
 }
 /**
  * Get an Iterator to the String based key set
  * 
  * @return An iterator to the key set
  */
 public Iterator stringKeyIterator() {
   return stringKeySet().iterator();
 }
 /*
  * Overridden HashMap methods
  */
 /**
  * Does the map contain this key?
  * 
  * @param key
  *          The key to look up
  * @return true If the key is present in the map
  */
 public boolean containsKey(String key) {
   return super.containsKey(new CaseBlindString(key));
 }
 /**
  * Fetch a value by name - null keys are not supported
  * 
  * @param key
  *          The key to look up
  * @return The associated value object
  */
 public Object get(String key) {
   return super.get(new CaseBlindString(key));
 }
 /**
  * Add the key/value pair to the map - null values are not supported
  * 
  * @param key
  *          The key name
  * @param value
  *          The object to store
  */
 public void put(String key, Object value) {
   super.put(new CaseBlindString(key), value);
 }
 /**
  * Remove a key/value pair from this map
  * 
  * @param key
  *          Non-null key to remove
  */
 public void remove(String key) {
   if (key == null) {
     throw new UnsupportedOperationException("null key");
   }
   super.remove(new CaseBlindString(key));
 }
 /**
  * A crude, case insensitive string - used internally to represent key values.
  * Preserve the originl case, but compare for equality in a case blind
  * fashion.
  */
 public static class CaseBlindString {
   String string;
   /**
    * Constructors
    */
   private CaseBlindString() {
   }
   public CaseBlindString(String string) {
     this.string = string;
   }
   /**
    * Fetch the original string
    * 
    * @return The original string
    */
   public String toString() {
     return string;
   }
   /**
    * Case insensitive compare
    * 
    * @return True if the two strings match
    */
   public boolean equals(Object object) {
     if (string == null) {
       return string == null;
     }
     return string.equalsIgnoreCase(((CaseBlindString) object).toString());
   }
   /**
    * Get a hash code for this case insensitive string
    * 
    * @return Hash code value
    */
   public int hashCode() {
     if (string == null) {
       return "null".hashCode();
     }
     return string.toUpperCase().hashCode();
   }
 }

}</source>

Clones a map and prefixes the keys in the clone

   <source lang="java">

import java.util.HashMap; import java.util.Iterator; import java.util.Map;

public class Main {

 /**
  * Clones a map and prefixes the keys in the clone, e.g.
  * for mapping "JAVA_HOME" to "env.JAVA_HOME" to simulate
  * the behaviour of ANT.
  *
  * @param source the source map
  * @param prefix the prefix used for all names
  * @return the clone of the source map
  */
 public static Map prefix(Map source, String prefix) {
     if(source == null) {
         return null;
     }
     Map result = new HashMap();
     Iterator iter = source.entrySet().iterator();
     while(iter.hasNext()) {
         Map.Entry entry = (Map.Entry) iter.next();
         Object key = entry.getKey();
         Object value = entry.getValue();
         result.put(prefix + "." + key.toString(), value);
     }
     return result;
 }

}</source>

Converts array into a java.util.Map.

   <source lang="java">

import java.util.HashMap; 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.
*
*
*/

/**

* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 // To map
 //-----------------------------------------------------------------------
 /**
  * Converts the given array into a {@link java.util.Map}. Each element of the array
  * must be either a {@link java.util.Map.Entry} or an Array, containing at least two
  * elements, where the first element is used as key and the second as
  * value.
  *
  * This method can be used to initialize:

*

   * // Create a Map mapping colors.
   * Map colorMap = MapUtils.toMap(new String[][] {{
   *     {"RED", "#FF0000"},
   *     {"GREEN", "#00FF00"},
   *     {"BLUE", "#0000FF"}});
   * 

  * 
  * This method returns null for a null input array.
  *
  * @param array  an array whose elements are either a {@link java.util.Map.Entry} or
  *  an Array containing at least two elements, may be null
  * @return a Map that was created from the array
  * @throws IllegalArgumentException  if one element of this Array is
  *  itself an Array containing less then two elements
  * @throws IllegalArgumentException  if the array contains elements other
  *  than {@link java.util.Map.Entry} and an Array
  */
 public static Map toMap(Object[] array) {
     if (array == null) {
         return null;
     }
     final Map map = new HashMap((int) (array.length * 1.5));
     for (int i = 0; i < array.length; i++) {
         Object object = array[i];
         if (object instanceof Map.Entry) {
             Map.Entry entry = (Map.Entry) object;
             map.put(entry.getKey(), entry.getValue());
         } else if (object instanceof Object[]) {
             Object[] entry = (Object[]) object;
             if (entry.length < 2) {
                 throw new IllegalArgumentException("Array element " + i + ", ""
                     + object
                     + "", has a length less than 2");
             }
             map.put(entry[0], entry[1]);
         } else {
             throw new IllegalArgumentException("Array element " + i + ", ""
                     + object
                     + "", is neither of type Map.Entry nor an Array");
         }
     }
     return map;
 }

}</source>

Creates a mutable map from two arrays with keys and values

   <source lang="java">

/**

* 
* The ObjectStyle Group Software License, version 1.1
* ObjectStyle Group - http://objectstyle.org/
* 
* Copyright (c) 2002-2005, Andrei (Andrus) Adamchik and individual authors
* of the software. All rights reserved.
* 
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
* 
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in
*    the documentation and/or other materials provided with the
*    distribution.
* 
* 3. The end-user documentation included with the redistribution, if any,
*    must include the following acknowlegement:
*    "This product includes software developed by independent contributors
*    and hosted on ObjectStyle Group web site (http://objectstyle.org/)."
*    Alternately, this acknowlegement may appear in the software itself,
*    if and wherever such third-party acknowlegements normally appear.
* 
* 4. The names "ObjectStyle Group" and "Cayenne" must not be used to endorse
*    or promote products derived from this software without prior written
*    permission. For written permission, email
*    "andrus at objectstyle dot org".
* 
* 5. Products derived from this software may not be called "ObjectStyle"
*    or "Cayenne", nor may "ObjectStyle" or "Cayenne" appear in their
*    names without prior written permission.
* 
* THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED.  IN NO EVENT SHALL THE OBJECTSTYLE GROUP OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* 
* This software consists of voluntary contributions made by many
* individuals and hosted on ObjectStyle Group web site.  For more
* information on the ObjectStyle Group, please see
* <http://objectstyle.org/>.
*/

import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.BufferedReader; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.FileReader; import java.io.IOException; import java.io.InputStream; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.OutputStream; import java.io.Serializable; import java.lang.reflect.Member; import java.lang.reflect.Modifier; import java.net.URL; import java.sql.SQLException; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.ruparator; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.regex.Pattern; import javax.xml.parsers.ParserConfigurationException; import javax.xml.parsers.SAXParser; import javax.xml.parsers.SAXParserFactory;

import org.xml.sax.SAXException; import org.xml.sax.XMLReader; /**

* Contains various unorganized static utility methods used across Cayenne.
* 
* @author Andrei Adamchik
*/

public class Util {

 /**
  * Creates a mutable map out of two arrays with keys and values.
  * 
  * @since 1.2
  */
 public static Map toMap(Object[] keys, Object[] values) {
     int keysSize = (keys != null) ? keys.length : 0;
     int valuesSize = (values != null) ? values.length : 0;
     if (keysSize == 0 && valuesSize == 0) {
         // return mutable map
         return new HashMap();
     }
     if (keysSize != valuesSize) {
         throw new IllegalArgumentException(
                 "The number of keys doesn"t match the number of values.");
     }
     Map map = new HashMap();
     for (int i = 0; i < keysSize; i++) {
         map.put(keys[i], values[i]);
     }
     return map;
 }

}</source>

Fixed size hash map using String values as keys mapped to primitive int values.

   <source lang="java">

/* Copyright (c) 2004-2005, Dennis M. Sosnoski. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
* Neither the name of JiBX nor the names of its contributors may be used
  to endorse or promote products derived from this software without specific
  prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

• /

/**

* Fixed size hash map using String values as keys mapped to
* primitive int values.
*
* @author Dennis M. Sosnoski
*/

public class StringIntSizedMap {

   /** Default fill fraction for sizing of tables. */
   public static final double DEFAULT_FILL_FRACTION = 0.4;
   
   /** Default value returned when key not found in table. */
   public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;
   
   /** Size of array used for keys. */
   protected final int m_arraySize;
   
 /** Array of key table slots. */
 protected final String[] m_keyTable;
 /** Array of value table slots. */
 protected final int[] m_valueTable;
   /** Value returned when key not found in table. */
   protected final int m_notFoundValue;
   /** Offset added (modulo table size) to slot number on collision. */
   protected final int m_hitOffset;
 /**
  * Constructor with full specification.
  *
  * @param count number of values to assume in sizing of table
  * @param fill fraction fill for table (maximum of 0.7, to
  * prevent excessive collisions)
    * @param miss value returned when key not found in table
  */
 public StringIntSizedMap(int count, double fill, int miss) {
       
       // make sure the fill fraction is in a reasonable range
       if (fill <= 0.0 || fill > 0.7) {
           throw new IllegalArgumentException("Fill fraction of " + fill +
               " is out of allowed range");
       }
       // compute initial table size (ensuring odd)
       int size = Math.max((int) (count / fill), 11);
       size += (size + 1) % 2;
       m_arraySize = size;
       // initialize the table information
       m_keyTable = new String[size];
       m_valueTable = new int[size];
       for (int i = 0; i < size; i++) {
           m_valueTable[i] = -1;
       }
       m_hitOffset = m_arraySize / 2;
       m_notFoundValue = miss;
 }
   /**
    * Constructor with value count and miss value specified. Uses default fill
    * fraction.
    *
    * @param count number of values to assume in initial sizing of table
    * @param miss value returned when key not found in table
    */
   public StringIntSizedMap(int count, int miss) {
       this(count, DEFAULT_FILL_FRACTION, miss);
   }
 /**
  * Constructor with only value count specified. Uses default fill fraction
  * and miss value.
  *
  * @param count number of values to assume in initial sizing of table
  */
 public StringIntSizedMap(int count) {
   this(count, DEFAULT_FILL_FRACTION, DEFAULT_NOT_FOUND);
 }
   /**
    * Step the slot number for an entry. Adds the collision offset (modulo
    * the table size) to the slot number.
    *
    * @param slot slot number to be stepped
    * @return stepped slot number
    */
   private final int stepSlot(int slot) {
       return (slot + m_hitOffset) % m_arraySize;
   }
   /**
    * Find free slot number for entry. Starts at the slot based directly
    * on the hashed key value. If this slot is already occupied, it adds
    * the collision offset (modulo the table size) to the slot number and
    * checks that slot, repeating until an unused slot is found.
    *
    * @param slot initial slot computed from key
    * @return slot at which entry was added
    */
   private final int freeSlot(int slot) {
       while (m_keyTable[slot] != null) {
           slot = stepSlot(slot);
       }
       return slot;
   }
   /**
    * Standard base slot computation for a key. This method may be used
    * directly for key lookup using either the hashCode() method
    * defined for the key objects or the System.identityHashCode()
    * method, as selected by the hash technique constructor parameter. To
    * implement a hash class based on some other methods of hashing and/or
    * equality testing, define a separate method in the subclass with a
    * different name and use that method instead. This avoids the overhead
    * caused by overrides of a very heavily used method.
    *
    * @param key key value to be computed
    * @return base slot for key
    */
   private final int standardSlot(String key) {
       return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
   }
   /**
    * Standard find key in table. This uses identity comparisons for the key
    * values.
    *
    * @param key to be found in table
    * @return index of matching key, or -index-1 of slot to be
    * used for inserting key in table if not already present (always negative)
    */
   private int standardFind(String key) {
       // find the starting point for searching table
       int slot = standardSlot(key);
       // scan through table to find target key
       while (m_keyTable[slot] != null) {
           // check if we have a match on target key
           if (m_keyTable[slot].equals(key)) {
               return slot;
           } else {
               slot = stepSlot(slot);
           }
       }
       return -slot-1;
   }
 /**
  * Add an entry to the table. If the key is already present in the table,
  * this replaces the existing value associated with the key.
  *
  * @param key key to be added to table (non-null)
  * @param value associated value for key
  * @return value previously associated with key, or reserved not found
  * value if key not previously present in table
  */
 public int add(String key, int value) {
   // first validate the parameters
   if (key == null) {
     throw new IllegalArgumentException("null key not supported");
   } else if (value == -1) {
     throw new IllegalArgumentException
       ("value matching not found return not supported");
   } else {
     // check space and duplicate key
     int offset = standardFind(key);
     if (offset >= 0) {
       // replace existing value for key
       int prior = m_valueTable[offset];
       m_valueTable[offset] = value;
       return prior;
     } else {
       // add new pair to table
       offset = -offset - 1;
       m_keyTable[offset] = key;
       m_valueTable[offset] = value;
       return m_notFoundValue;
     }
   }
 }
 /**
  * Check if an entry is present in the table. This method is supplied to
  * support the use of values matching the reserved not found value.
  *
  * @param key key for entry to be found
  * @return true if key found in table, false
  * if not
  */
 public final boolean containsKey(String key) {
   return standardFind(key) >= 0;
 }
 /**
  * Find an entry in the table.
  *
  * @param key key for entry to be returned
  * @return value for key, or reserved not found value if key not found
  */
 public final int get(String key) {
   int slot = standardFind(key);
   if (slot >= 0) {
     return m_valueTable[slot];
   } else {
     return m_notFoundValue;
   }
 }
   /**
    * Set the table to the empty state.
    */
   public void clear() {
       for (int i = 0; i < m_keyTable.length; i++) {
           m_keyTable[i] = null;
           m_valueTable[i] = m_notFoundValue;
       }
   }

}</source>

Hash map for counting references to Object keys.

   <source lang="java">

/*

* Copyright (c) 2006-2007, Dennis M. Sosnoski. All rights reserved.
* 
* Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
* following conditions are met:
* 
* Redistributions of source code must retain the above copyright notice, this list of conditions and the following
* disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
* following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of
* JiBX nor the names of its contributors may be used to endorse or promote products derived from this software without
* specific prior written permission.
* 
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

import java.util.Iterator;

/**

* Hash map for counting references to Object keys. The map implementation is not very efficient when
* resizing, but works well when the size of the map is known in advance or when accesses are substantially more common
* than adds.
* 
* @author Dennis M. Sosnoski
*/

public class ReferenceCountMap {

   /** Default fill fraction allowed before growing table. */
   private static final double DEFAULT_FILL = 0.3d;
   
   /** Minimum size used for hash table. */
   private static final int MINIMUM_SIZE = 63;
   
   /** Number of entries present in table. */
   private int m_entryCount;
   
   /** Entries allowed before growing table. */
   private int m_entryLimit;
   
   /** Size of array used for keys. */
   private int m_arraySize;
   
   /** Offset added (modulo table size) to slot number on collision. */
   private int m_hitOffset;
   
   /** Array of key table slots. */
   private Object[] m_keyTable;
   
   /** Array of value table slots. */
   private int[] m_valueTable;
   
   /**
    * Constructor with count.
    * 
    * @param count number of values to assume in initial sizing of table
    */
   public ReferenceCountMap(int count) {
       
       // compute initial table size (ensuring odd)
       m_arraySize = Math.max((int)(count / DEFAULT_FILL), MINIMUM_SIZE);
       m_arraySize += (m_arraySize + 1) % 2;
       
       // initialize the table information
       m_entryLimit = (int)(m_arraySize * DEFAULT_FILL);
       m_hitOffset = m_arraySize / 2;
       m_keyTable = new Object[m_arraySize];
       m_valueTable = new int[m_arraySize];
   }
   
   /**
    * Default constructor.
    */
   public ReferenceCountMap() {
       this(0);
   }
   
   /**
    * Copy (clone) constructor.
    * 
    * @param base instance being copied
    */
   public ReferenceCountMap(ReferenceCountMap base) {
       
       // copy the basic occupancy information
       m_entryCount = base.m_entryCount;
       m_entryLimit = base.m_entryLimit;
       m_arraySize = base.m_arraySize;
       m_hitOffset = base.m_hitOffset;
       
       // copy table of items
       m_keyTable = new Object[m_arraySize];
       System.arraycopy(base.m_keyTable, 0, m_keyTable, 0, m_arraySize);
       m_valueTable = new int[m_arraySize];
       System.arraycopy(base.m_valueTable, 0, m_valueTable, 0, m_arraySize);
   }
   
   /**
    * Step the slot number for an entry. Adds the collision offset (modulo the table size) to the slot number.
    * 
    * @param slot slot number to be stepped
    * @return stepped slot number
    */
   private final int stepSlot(int slot) {
       return (slot + m_hitOffset) % m_arraySize;
   }
   
   /**
    * Find free slot number for entry. Starts at the slot based directly on the hashed key value. If this slot is
    * already occupied, it adds the collision offset (modulo the table size) to the slot number and checks that slot,
    * repeating until an unused slot is found.
    * 
    * @param slot initial slot computed from key
    * @return slot at which entry was added
    */
   private final int freeSlot(int slot) {
       while (m_keyTable[slot] != null) {
           slot = stepSlot(slot);
       }
       return slot;
   }
   
   /**
    * Standard base slot computation for a key.
    * 
    * @param key key value to be computed
    * @return base slot for key
    */
   private final int standardSlot(Object key) {
       return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
   }
   
   /**
    * Standard find key in table. This method may be used directly for key lookup using either the
    * hashCode() method defined for the key objects or the System.identityHashCode()
    * method, and either the equals() method defined for the key objects or the ==
    * operator, as selected by the hash technique constructor parameter. To implement a hash class based on some other
    * methods of hashing and/or equality testing, define a separate method in the subclass with a different name and
    * use that method instead. This avoids the overhead caused by overrides of a very heavily used method.
    * 
    * @param key to be found in table
    * @return index of matching key, or -index-1 of slot to be used for inserting key in table if not
    * already present (always negative)
    */
   private int standardFind(Object key) {
       
       // find the starting point for searching table
       int slot = standardSlot(key);
       
       // scan through table to find target key
       while (m_keyTable[slot] != null) {
           
           // check if we have a match on target key
           if (m_keyTable[slot].equals(key)) {
               return slot;
           } else {
               slot = stepSlot(slot);
           }
           
       }
       return -slot - 1;
   }
   
   /**
    * Reinsert an entry into the hash map. This is used when the table is being directly modified, and does not adjust
    * the count present or check the table capacity.
    * 
    * @param slot position of entry to be reinserted into hash map
    * @return true if the slot number used by the entry has has changed, false if not
    */
   private boolean reinsert(int slot) {
       Object key = m_keyTable[slot];
       m_keyTable[slot] = null;
       return assignSlot(key, m_valueTable[slot]) != slot;
   }
   
   /**
    * Internal remove pair from the table. Removes the pair from the table by setting the key entry to
    * null and adjusting the count present, then chains through the table to reinsert any other pairs
    * which may have collided with the removed pair. If the associated value is an object reference, it should be set
    * to null before this method is called.
    * 
    * @param slot index number of pair to be removed
    */
   private void internalRemove(int slot) {
       
       // delete pair from table
       m_keyTable[slot] = null;
       m_entryCount--;
       while (m_keyTable[(slot = stepSlot(slot))] != null) {
           
           // reinsert current entry in table to fill holes
           reinsert(slot);
           
       }
   }
   
   /**
    * Restructure the table. This is used when the table is increasing or decreasing in size, and works directly with
    * the old table representation arrays. It inserts pairs from the old arrays directly into the table without
    * adjusting the count present or checking the table size.
    * 
    * @param keys array of keys
    * @param values array of values
    */
   private void restructure(Object[] keys, int[] values) {
       for (int i = 0; i < keys.length; i++) {
           if (keys[i] != null) {
               assignSlot(keys[i], values[i]);
           }
       }
   }
   
   /**
    * Assign slot for entry. Starts at the slot found by the hashed key value. If this slot is already occupied, it
    * steps the slot number and checks the resulting slot, repeating until an unused slot is found. This method does
    * not check for duplicate keys, so it should only be used for internal reordering of the tables.
    * 
    * @param key to be added to table
    * @param value associated value for key
    * @return slot at which entry was added
    */
   private int assignSlot(Object key, int value) {
       int offset = freeSlot(standardSlot(key));
       m_keyTable[offset] = key;
       m_valueTable[offset] = value;
       return offset;
   }
   
   /**
    * Increment a use count in the table. If the key object is already present in the table this adds one to the
    * reference count; if not present, this adds the key with an initial reference count of one.
    * 
    * @param key referenced object (non-null)
    * @return incremented use count
    */
   public int incrementCount(Object key) {
       
       // first validate the parameters
       if (key == null) {
           throw new IllegalArgumentException("null key not supported");
       } else {
           
           // check space available
           int min = m_entryCount + 1;
           if (min > m_entryLimit) {
               
               // find the array size required
               int size = m_arraySize;
               int limit = m_entryLimit;
               while (limit < min) {
                   size = size * 2 + 1;
                   limit = (int)(size * DEFAULT_FILL);
               }
               
               // set parameters for new array size
               m_arraySize = size;
               m_entryLimit = limit;
               m_hitOffset = size / 2;
               
               // restructure for larger arrays
               Object[] keys = m_keyTable;
               m_keyTable = new Object[m_arraySize];
               int[] values = m_valueTable;
               m_valueTable = new int[m_arraySize];
               restructure(keys, values);
           }
           
           // find slot of table
           int offset = standardFind(key);
           if (offset >= 0) {
               
               // replace existing value for key
               return ++m_valueTable[offset];
               
           } else {
               
               // add new pair to table
               m_entryCount++;
               offset = -offset - 1;
               m_keyTable[offset] = key;
               m_valueTable[offset] = 1;
               return 1;
               
           }
       }
   }
   
   /**
    * Find an entry in the table.
    * 
    * @param key key for entry to be returned
    * @return value for key, or zero if key not found
    */
   public final int getCount(Object key) {
       int slot = standardFind(key);
       if (slot >= 0) {
           return m_valueTable[slot];
       } else {
           return 0;
       }
   }
   
   /**
    * Get number of entries in map.
    * 
    * @return entry count
    */
   public int size() {
       return m_entryCount;
   }
   
   /**
    * Get iterator for keys in map. The returned iterator is not safe, so the iterator behavior is undefined if the map
    * is modified.
    * 
    * @return iterator
    */
   public Iterator iterator() {
       return SparseArrayIterator.buildIterator(m_keyTable);
   }
   
   /**
    * Get array of keys in map.
    * 
    * @return key array
    */
   public Object[] keyArray() {
       Object[] keys = new Object[m_entryCount];
       int fill = 0;
       for (int i = 0; i < m_arraySize; i++) {
           if (m_keyTable[i] != null) {
               keys[fill++] = m_keyTable[i];
           }
       }
       return keys;
   }
   
   /**
    * Construct a copy of the table.
    * 
    * @return shallow copy of table
    */
   public Object clone() {
       return new ReferenceCountMap(this);
   }
   
   /**
    * Clear all keys and counts.
    */
   public void clear() {
       for (int i = 0; i < m_keyTable.length; i++) {
           if (m_keyTable[i] != null) {
               m_keyTable[i] = null;
               m_valueTable[i] = 0;
           }
       }
   }

} /*

* Copyright (c) 2000-2007, Dennis M. Sosnoski. All rights reserved.
* 
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
* 
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer. Redistributions in binary
* form must reproduce the above copyright notice, this list of conditions and
* the following disclaimer in the documentation and/or other materials provided
* with the distribution. Neither the name of JiBX nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
* 
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/

/**

* Iterator class for sparse values in an array. This type of iterator
* can be used for an object array which has references interspersed with
* nulls.
*
* @author Dennis M. Sosnoski
*/
class SparseArrayIterator implements Iterator

{

   /** Empty iterator. */
   public static final SparseArrayIterator EMPTY_ITERATOR =
       new SparseArrayIterator(new Object[0]);
   
   /** Array supplying values for iteration. */
   private Object[] m_array;
   /** Offset of next iteration value. */
   private int m_offset;
   /**
    * Internal constructor.
    *
    * @param array array containing values to be iterated
    */
   private SparseArrayIterator(Object[] array) {
       m_array = array;
       m_offset = -1;
       advance();
   }
   /**
    * Advance to next iteration value. This advances the current position in
    * the array to the next non-null value.
    *
    * @return true if element available, false if
    * not
    */
   protected boolean advance() {
       while (++m_offset < m_array.length) {
           if (m_array[m_offset] != null) {
               return true;
           }
       }
       return false;
   }
   /**
    * Check for iteration element available.
    *
    * @return true if element available, false if
    * not
    */
   public boolean hasNext() {
       return m_offset < m_array.length;
   }
   /**
    * Get next iteration element.
    *
    * @return next iteration element
    * @exception NoSuchElementException if past end of iteration
    */
   public Object next() {
       if (m_offset < m_array.length) {
           Object result = m_array[m_offset];
           advance();
           return result;
       } else {
           throw new RuntimeException("No such method");
       }
   }
   /**
    * Remove element from iteration. This optional operation is not supported
    * and always throws an exception.
    *
    * @exception UnsupportedOperationException for unsupported operation
    */
   public void remove() {
       throw new UnsupportedOperationException();
   }
   /**
    * Build iterator.
    *
    * @param array array containing values to be iterated (may be
    * null)
    * @return constructed iterator
    */
   public static Iterator buildIterator(Object[] array) {
       if (array == null || array.length == 0) {
           return EMPTY_ITERATOR;
       } else {
           return new SparseArrayIterator(array);
       }
   }

}</source>

Hash map using String values as keys mapped to primitive int values.

   <source lang="java">

/*

* Copyright (c) 2000-2005, Dennis M. Sosnoski. All rights reserved.
* 
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
* 
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer. Redistributions in binary
* form must reproduce the above copyright notice, this list of conditions and
* the following disclaimer in the documentation and/or other materials provided
* with the distribution. Neither the name of JiBX nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
* 
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/

/**

* Hash map using String values as keys mapped to primitive
* int values. This implementation is unsynchronized in order to
* provide the best possible performance for typical usage scenarios, so
* explicit synchronization must be implemented by a wrapper class or directly
* by the application in cases where instances are modified in a multithreaded
* environment. The map implementation is not very efficient when resizing, but
* works well when the size of the map is known in advance.
* 
* @author Dennis M. Sosnoski
* @version 1.1
*/

public class StringIntHashMap {

   /** Default value returned when key not found in table. */
   public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;
   /** Default fill fraction allowed before growing table. */
   protected static final double DEFAULT_FILL = 0.3d;
   /** Minimum size used for hash table. */
   protected static final int MINIMUM_SIZE = 31;
   /** Fill fraction allowed for this hash table. */
   protected final double m_fillFraction;
   /** Number of entries present in table. */
   protected int m_entryCount;
   /** Entries allowed before growing table. */
   protected int m_entryLimit;
   /** Size of array used for keys. */
   protected int m_arraySize;
   /** Offset added (modulo table size) to slot number on collision. */
   protected int m_hitOffset;
   /** Array of key table slots. */
   protected String[] m_keyTable;
   /** Array of value table slots. */
   protected int[] m_valueTable;
   /** Value returned when key not found in table. */
   protected int m_notFoundValue;
   /**
    * Constructor with full specification.
    * 
    * @param count number of values to assume in initial sizing of table
    * @param fill fraction full allowed for table before growing
    * @param miss value returned when key not found in table
    */
   public StringIntHashMap(int count, double fill, int miss) {
       // check the passed in fill fraction
       if (fill <= 0.0d || fill >= 1.0d) {
           throw new IllegalArgumentException("fill value out of range");
       }
       m_fillFraction = fill;
       // compute initial table size (ensuring odd)
       m_arraySize = Math.max((int)(count / m_fillFraction), MINIMUM_SIZE);
       m_arraySize += (m_arraySize + 1) % 2;
       // initialize the table information
       m_entryLimit = (int)(m_arraySize * m_fillFraction);
       m_hitOffset = m_arraySize / 2;
       m_keyTable = new String[m_arraySize];
       m_valueTable = new int[m_arraySize];
       m_notFoundValue = miss;
   }
   /**
    * Constructor with size and fill fraction specified. Uses default hash
    * technique and value returned when key not found in table.
    * 
    * @param count number of values to assume in initial sizing of table
    * @param fill fraction full allowed for table before growing
    */
   public StringIntHashMap(int count, double fill) {
       this(count, fill, DEFAULT_NOT_FOUND);
   }
   /**
    * Constructor with only size supplied. Uses default hash technique and
    * values for fill fraction and value returned when key not found in table.
    * 
    * @param count number of values to assume in initial sizing of table
    */
   public StringIntHashMap(int count) {
       this(count, DEFAULT_FILL);
   }
   /**
    * Default constructor.
    */
   public StringIntHashMap() {
       this(0, DEFAULT_FILL);
   }
   /**
    * Copy (clone) constructor.
    * 
    * @param base instance being copied
    */
   public StringIntHashMap(StringIntHashMap base) {
       // copy the basic occupancy information
       m_fillFraction = base.m_fillFraction;
       m_entryCount = base.m_entryCount;
       m_entryLimit = base.m_entryLimit;
       m_arraySize = base.m_arraySize;
       m_hitOffset = base.m_hitOffset;
       m_notFoundValue = base.m_notFoundValue;
       // copy table of items
       m_keyTable = new String[m_arraySize];
       System.arraycopy(base.m_keyTable, 0, m_keyTable, 0, m_arraySize);
       m_valueTable = new int[m_arraySize];
       System.arraycopy(base.m_valueTable, 0, m_valueTable, 0, m_arraySize);
   }
   /**
    * Step the slot number for an entry. Adds the collision offset (modulo
    * the table size) to the slot number.
    *
    * @param slot slot number to be stepped
    * @return stepped slot number
    */
   private final int stepSlot(int slot) {
       return (slot + m_hitOffset) % m_arraySize;
   }
   /**
    * Find free slot number for entry. Starts at the slot based directly
    * on the hashed key value. If this slot is already occupied, it adds
    * the collision offset (modulo the table size) to the slot number and
    * checks that slot, repeating until an unused slot is found.
    *
    * @param slot initial slot computed from key
    * @return slot at which entry was added
    */
   private final int freeSlot(int slot) {
       while (m_keyTable[slot] != null) {
           slot = stepSlot(slot);
       }
       return slot;
   }
   /**
    * Standard base slot computation for a key.
    *
    * @param key key value to be computed
    * @return base slot for key
    */
   private final int standardSlot(Object key) {
       return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
   }
   /**
    * Standard find key in table. This method may be used directly for key
    * lookup using either the hashCode() method defined for the
    * key objects or the System.identityHashCode() method, and
    * either the equals() method defined for the key objects or
    * the == operator, as selected by the hash technique
    * constructor parameter. To implement a hash class based on some other
    * methods of hashing and/or equality testing, define a separate method in
    * the subclass with a different name and use that method instead. This
    * avoids the overhead caused by overrides of a very heavily used method.
    *
    * @param key to be found in table
    * @return index of matching key, or -index-1 of slot to be
    * used for inserting key in table if not already present (always negative)
    */
   private int standardFind(Object key) {
       // find the starting point for searching table
       int slot = standardSlot(key);
       // scan through table to find target key
       while (m_keyTable[slot] != null) {
           // check if we have a match on target key
           if (m_keyTable[slot].equals(key)) {
               return slot;
           } else {
               slot = stepSlot(slot);
           }
       }
       return -slot-1;
   }
   /**
    * Reinsert an entry into the hash map. This is used when the table is being
    * directly modified, and does not adjust the count present or check the
    * table capacity.
    * 
    * @param slot position of entry to be reinserted into hash map
    * @return true if the slot number used by the entry has has
    * changed, false if not
    */
   private boolean reinsert(int slot) {
       String key = m_keyTable[slot];
       m_keyTable[slot] = null;
       return assignSlot(key, m_valueTable[slot]) != slot;
   }
   /**
    * Internal remove pair from the table. Removes the pair from the table
    * by setting the key entry to null and adjusting the count
    * present, then chains through the table to reinsert any other pairs
    * which may have collided with the removed pair. If the associated value
    * is an object reference, it should be set to null before
    * this method is called.
    *
    * @param slot index number of pair to be removed
    */
   protected void internalRemove(int slot) {
       // delete pair from table
       m_keyTable[slot] = null;
       m_entryCount--;
       while (m_keyTable[(slot = stepSlot(slot))] != null) {
           // reinsert current entry in table to fill holes
           reinsert(slot);
       }
   }
   /**
    * Restructure the table. This is used when the table is increasing or
    * decreasing in size, and works directly with the old table representation
    * arrays. It inserts pairs from the old arrays directly into the table
    * without adjusting the count present or checking the table size.
    * 
    * @param keys array of keys
    * @param values array of values
    */
   private void restructure(String[] keys, int[] values) {
       for (int i = 0; i < keys.length; i++) {
           if (keys[i] != null) {
               assignSlot(keys[i], values[i]);
           }
       }
   }
   /**
    * Assign slot for entry. Starts at the slot found by the hashed key value.
    * If this slot is already occupied, it steps the slot number and checks the
    * resulting slot, repeating until an unused slot is found. This method does
    * not check for duplicate keys, so it should only be used for internal
    * reordering of the tables.
    * 
    * @param key to be added to table
    * @param value associated value for key
    * @return slot at which entry was added
    */
   private int assignSlot(String key, int value) {
       int offset = freeSlot(standardSlot(key));
       m_keyTable[offset] = key;
       m_valueTable[offset] = value;
       return offset;
   }
   /**
    * Add an entry to the table. If the key is already present in the table,
    * this replaces the existing value associated with the key.
    * 
    * @param key key to be added to table (non- null)
    * @param value associated value for key
    * @return value previously associated with key, or reserved not found value
    * if key not previously present in table
    */
   public int add(String key, int value) {
       // first validate the parameters
       if (key == null) {
           throw new IllegalArgumentException("null key not supported");
       } else if (value == m_notFoundValue) {
           throw new IllegalArgumentException(
               "value matching not found return not supported");
       } else {
           // check space available
           int min = m_entryCount + 1;
           if (min > m_entryLimit) {
               
               // find the array size required
               int size = m_arraySize;
               int limit = m_entryLimit;
               while (limit < min) {
                   size = size * 2 + 1;
                   limit = (int) (size * m_fillFraction);
               }
           
               // set parameters for new array size
               m_arraySize = size;
               m_entryLimit = limit;
               m_hitOffset = size / 2;
               
               // restructure for larger arrays
               String[] keys = m_keyTable;
               m_keyTable = new String[m_arraySize];
               int[] values = m_valueTable;
               m_valueTable = new int[m_arraySize];
               restructure(keys, values);
           }
           
           // find slot of table
           int offset = standardFind(key);
           if (offset >= 0) {
               // replace existing value for key
               int prior = m_valueTable[offset];
               m_valueTable[offset] = value;
               return prior;
           } else {
               // add new pair to table
               m_entryCount++;
               offset = -offset - 1;
               m_keyTable[offset] = key;
               m_valueTable[offset] = value;
               return m_notFoundValue;
           }
       }
   }
   /**
    * Check if an entry is present in the table. This method is supplied to
    * support the use of values matching the reserved not found value.
    * 
    * @param key key for entry to be found
    * @return true if key found in table, false
    * if not
    */
   public final boolean containsKey(String key) {
       return standardFind(key) >= 0;
   }
   /**
    * Find an entry in the table.
    * 
    * @param key key for entry to be returned
    * @return value for key, or reserved not found value if key not found
    */
   public final int get(String key) {
       int slot = standardFind(key);
       if (slot >= 0) {
           return m_valueTable[slot];
       } else {
           return m_notFoundValue;
       }
   }
   /**
    * Remove an entry from the table. If multiple entries are present with the
    * same key value, only the first one found will be removed.
    * 
    * @param key key to be removed from table
    * @return value associated with removed key, or reserved not found value if
    * key not found in table
    */
   public int remove(String key) {
       int slot = standardFind(key);
       if (slot >= 0) {
           int value = m_valueTable[slot];
           internalRemove(slot);
           return value;
       } else {
           return m_notFoundValue;
       }
   }
   /**
    * Construct a copy of the table.
    * 
    * @return shallow copy of table
    */
   public Object clone() {
       return new StringIntHashMap(this);
   }

}</source>

HashNMap stores multiple values by a single key value. Values can be retrieved using a direct query or by creating an enumeration over the stored elements.

   <source lang="java">

/*

* JCommon : a free general purpose class library for the Java(tm) platform
* 
*
* (C) Copyright 2000-2005, by Object Refinery Limited and Contributors.
* 
* Project Info:  http://www.jfree.org/jcommon/index.html
*
* This library is free software; you can redistribute it and/or modify it 
* under the terms of the GNU Lesser General Public License as published by 
* the Free Software Foundation; either version 2.1 of the License, or 
* (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but 
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
* USA.  
*
* [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
* in the United States and other countries.]
*
* -------------
* HashNMap.java
* -------------
* (C)opyright 2002-2005, by Thomas Morgner and Contributors.
*
* Original Author:  Thomas Morgner;
* Contributor(s):   David Gilbert (for Object Refinery Limited);
*
* $Id: HashNMap.java,v 1.7 2005/10/18 13:24:19 mungady Exp $
*
* Changes
* -------
* 20-May-2002 : Initial version
* 10-Dec-2002 : Minor Javadoc updates (DG);
* 29-Jul-2004 : Replaced "enum" variable name (reserved word in JDK 1.5) (DG);
* 12-Mar-2005 : Some performance improvements, this implementation is no 
*               longer forced to use ArrayLists, add/put behaviour changed to 
*               fit the common behaviour of collections.
*
*/

import java.io.Serializable; import java.lang.reflect.Method; import java.lang.reflect.Modifier; import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException; import java.util.Set; /**

* The HashNMap can be used to store multiple values by a single key value. The
* values stored can be retrieved using a direct query or by creating an
* enumeration over the stored elements.
* 
* @author Thomas Morgner
*/

public class HashNMap implements Serializable, Cloneable {

 /** Serialization support. */
 private static final long serialVersionUID = -670924844536074826L;
 /**
  * An helper class to implement an empty iterator. This iterator will always
  * return false when hasNext is called.
  */
 private static final class EmptyIterator implements Iterator {
   /**
    * DefaultConstructor.
    */
   private EmptyIterator() {
     super();
   }
   /**
    * Returns true if the iteration has more elements. (In other
    * words, returns true if next would return an element
    * rather than throwing an exception.)
    * 
    * @return true if the iterator has more elements.
    */
   public boolean hasNext() {
     return false;
   }
   /**
    * Returns the next element in the iteration.
    * 
    * @return the next element in the iteration.
    * @throws NoSuchElementException
    *           iteration has no more elements.
    */
   public Object next() {
     throw new NoSuchElementException("This iterator is empty.");
   }
   /**
    * Removes from the underlying collection the last element returned by the
    * iterator (optional operation). This method can be called only once per
    * call to next. The behavior of an iterator is unspecified if
    * the underlying collection is modified while the iteration is in progress
    * in any way other than by calling this method.
    * 
    * @throws UnsupportedOperationException
    *           if the remove operation is not supported by this
    *           Iterator.
    * @throws IllegalStateException
    *           if the next method has not yet been called, or the
    *           remove method has already been called after the last
    *           call to the next method.
    */
   public void remove() {
     throw new UnsupportedOperationException("This iterator is empty, no remove supported.");
   }
 }
 /**
  * A singleton instance of the empty iterator. This object can be safely
  * shared.
  */
 private static final Iterator EMPTY_ITERATOR = new EmptyIterator();
 /**
  * The underlying storage.
  */
 private HashMap table;
 /**
  * An empty array.
  */
 private static final Object[] EMPTY_ARRAY = new Object[0];
 /**
  * Default constructor.
  */
 public HashNMap() {
   this.table = new HashMap();
 }
 /**
  * Returns a new empty list.
  * 
  * @return A new empty list.
  */
 protected List createList() {
   return new ArrayList();
 }
 /**
  * Inserts a new key/value pair into the map. If such a pair already exists,
  * it gets replaced with the given values.
  * 
  * @param key
  *          the key.
  * @param val
  *          the value.
  * @return A boolean.
  */
 public boolean put(final Object key, final Object val) {
   final List v = (List) this.table.get(key);
   if (v == null) {
     final List newList = createList();
     newList.add(val);
     this.table.put(key, newList);
     return true;
   } else {
     v.clear();
     return v.add(val);
   }
 }
 /**
  * Adds a new key/value pair into this map. If the key is not yet in the map,
  * it gets added to the map and the call is equal to put(Object,Object).
  * 
  * @param key
  *          the key.
  * @param val
  *          the value.
  * @return true, if the value has been added, false otherwise
  */
 public boolean add(final Object key, final Object val) {
   final List v = (List) this.table.get(key);
   if (v == null) {
     put(key, val);
     return true;
   } else {
     return v.add(val);
   }
 }
 /**
  * Retrieves the first value registered for an key or null if there was no
  * such key in the list.
  * 
  * @param key
  *          the key.
  * @return the value.
  */
 public Object getFirst(final Object key) {
   return get(key, 0);
 }
 /**
  * Retrieves the n-th value registered for an key or null if there was no such
  * key in the list. An index out of bounds exception is thrown if there are
  * less than n elements registered to this key.
  * 
  * @param key
  *          the key.
  * @param n
  *          the index.
  * @return the object.
  */
 public Object get(final Object key, final int n) {
   final List v = (List) this.table.get(key);
   if (v == null) {
     return null;
   }
   return v.get(n);
 }
 /**
  * Returns an iterator over all elements registered to the given key.
  * 
  * @param key
  *          the key.
  * @return an iterator.
  */
 public Iterator getAll(final Object key) {
   final List v = (List) this.table.get(key);
   if (v == null) {
     return EMPTY_ITERATOR;
   }
   return v.iterator();
 }
 /**
  * Returns all registered keys as an enumeration.
  * 
  * @return an enumeration of the keys.
  */
 public Iterator keys() {
   return this.table.keySet().iterator();
 }
 /**
  * Returns all registered keys as set.
  * 
  * @return a set of keys.
  */
 public Set keySet() {
   return this.table.keySet();
 }
 /**
  * Removes the key/value pair from the map. If the removed entry was the last
  * entry for this key, the key gets also removed.
  * 
  * @param key
  *          the key.
  * @param value
  *          the value.
  * @return true, if removing the element was successfull, false otherwise.
  */
 public boolean remove(final Object key, final Object value) {
   final List v = (List) this.table.get(key);
   if (v == null) {
     return false;
   }
   if (!v.remove(value)) {
     return false;
   }
   if (v.size() == 0) {
     this.table.remove(key);
   }
   return true;
 }
 /**
  * Removes all elements for the given key.
  * 
  * @param key
  *          the key.
  */
 public void removeAll(final Object key) {
   this.table.remove(key);
 }
 /**
  * Clears all keys and values of this map.
  */
 public void clear() {
   this.table.clear();
 }
 /**
  * Tests whether this map contains the given key.
  * 
  * @param key
  *          the key.
  * @return true if the key is contained in the map
  */
 public boolean containsKey(final Object key) {
   return this.table.containsKey(key);
 }
 /**
  * Tests whether this map contains the given value.
  * 
  * @param value
  *          the value.
  * @return true if the value is registered in the map for an key.
  */
 public boolean containsValue(final Object value) {
   final Iterator e = this.table.values().iterator();
   boolean found = false;
   while (e.hasNext() && !found) {
     final List v = (List) e.next();
     found = v.contains(value);
   }
   return found;
 }
 /**
  * Tests whether this map contains the given value.
  * 
  * @param value
  *          the value.
  * @param key
  *          the key under which to find the value
  * @return true if the value is registered in the map for an key.
  */
 public boolean containsValue(final Object key, final Object value) {
   final List v = (List) this.table.get(key);
   if (v == null) {
     return false;
   }
   return v.contains(value);
 }
 /**
  * Tests whether this map contains the given key or value.
  * 
  * @param value
  *          the value.
  * @return true if the key or value is contained in the map
  */
 public boolean contains(final Object value) {
   if (containsKey(value)) {
     return true;
   }
   return containsValue(value);
 }
 /**
  * Returns a clone of the specified object, if it can be cloned, otherwise
  * throws a CloneNotSupportedException.
  * 
  * @param object
  *          the object to clone (null not permitted).
  * @return A clone of the specified object.
  * @throws CloneNotSupportedException
  *           if the object cannot be cloned.
  */
 public static Object clone(final Object object) throws CloneNotSupportedException {
   if (object == null) {
     throw new IllegalArgumentException("Null "object" argument.");
   }
   else {
     try {
       final Method method = object.getClass().getMethod("clone", (Class[]) null);
       if (Modifier.isPublic(method.getModifiers())) {
         return method.invoke(object, (Object[]) null);
       }
     } catch (Exception e) {
     }
   }
   throw new CloneNotSupportedException("Failed to clone.");
 }
 /**
  * Creates a deep copy of this HashNMap.
  * 
  * @return a clone.
  * @throws CloneNotSupportedException
  *           this should never happen.
  */
 public Object clone() throws CloneNotSupportedException {
   final HashNMap map = (HashNMap) super.clone();
   map.table = new HashMap();
   final Iterator iterator = keys();
   while (iterator.hasNext()) {
     final Object key = iterator.next();
     final List list = (List) map.table.get(key);
     if (list != null) {
       map.table.put(key,clone(list));
     }
   }
   return map;
 }
 /**
  * Returns the contents for the given key as object array. If there were no
  * objects registered with that key, an empty object array is returned.
  * 
  * @param key
  *          the key.
  * @param data
  *          the object array to receive the contents.
  * @return the contents.
  */
 public Object[] toArray(final Object key, final Object[] data) {
   if (key == null) {
     throw new NullPointerException("Key must not be null.");
   }
   final List list = (List) this.table.get(key);
   if (list != null) {
     return list.toArray(data);
   }
   if (data.length > 0) {
     data[0] = null;
   }
   return data;
 }
 /**
  * Returns the contents for the given key as object array. If there were no
  * objects registered with that key, an empty object array is returned.
  * 
  * @param key
  *          the key.
  * @return the contents.
  */
 public Object[] toArray(final Object key) {
   if (key == null) {
     throw new NullPointerException("Key must not be null.");
   }
   final List list = (List) this.table.get(key);
   if (list != null) {
     return list.toArray();
   }
   return EMPTY_ARRAY;
 }
 /**
  * Returns the number of elements registered with the given key.
  * 
  * @param key
  *          the key.
  * @return the number of element for this key, or 0 if there are no elements
  *         registered.
  */
 public int getValueCount(final Object key) {
   if (key == null) {
     throw new NullPointerException("Key must not be null.");
   }
   final List list = (List) this.table.get(key);
   if (list != null) {
     return list.size();
   }
   return 0;
 }

}</source>

Implementation of a bit map of any size, together with static methods to manipulate int, byte and byte[] values as bit maps

   <source lang="java">

/* Copyright (c) 2001-2009, The HSQL Development Group

* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/**

* Implementation of a bit map of any size, together with static methods to
* manipulate int, byte and byte[] values as bit maps.
*
* @author Fred Toussi (fredt@users dot sourceforge.net)
* @version 1.9.0
* @since 1.8.0

• /

public class BitMap {

   int   defaultCapacity;
   int   capacity;
   int[] map;
   int   limitPos;
   public BitMap(int initialCapacity) {
       int words = initialCapacity / 32;
       if (initialCapacity % 32 != 0) {
           words++;
       }
       defaultCapacity = capacity = words * 32;
       map             = new int[words];
       limitPos        = 0;
   }
   public int size() {
       return limitPos;
   }
   public void setSize(int size) {
       limitPos = size;
   }
   /**
    * Resets to blank with original capacity
    */
   public void reset() {
       map      = new int[defaultCapacity / 32];
       capacity = defaultCapacity;
       limitPos = 0;
   }
   /**
    * Sets pos and returns old value
    */
   public int set(int pos) {
       while (pos >= capacity) {
           doubleCapacity();
       }
       if (pos >= limitPos) {
           limitPos = pos + 1;
       }
       int windex = pos >> 5;
       int mask   = 0x80000000 >>> (pos & 0x1F);
       int word   = map[windex];
       int result = (word & mask) == 0 ? 0
                                       : 1;
       map[windex] = (word | mask);
       return result;
   }
   /**
    * Unsets pos and returns old value
    */
   public int unset(int pos) {
       while (pos >= capacity) {
           doubleCapacity();
       }
       if (pos >= limitPos) {
           limitPos = pos + 1;
           return 0;
       }
       int windex = pos >> 5;
       int mask   = 0x80000000 >>> (pos & 0x1F);
       int word   = map[windex];
       int result = (word & mask) == 0 ? 0
                                       : 1;
       mask        = ~mask;
       map[windex] = (word & mask);
       return result;
   }
   public int get(int pos) {
       while (pos >= capacity) {
           doubleCapacity();
       }
       if (pos >= limitPos) {
           limitPos = pos + 1;
           return 0;
       }
       int windex = pos >> 5;
       int mask   = 0x80000000 >>> (pos & 0x1F);
       int word   = map[windex];
       return (word & mask) == 0 ? 0
                                 : 1;
   }
   public boolean isSet(int pos) {
       return get(pos) == 1;
   }
   public byte[] getBytes() {
       byte[] buf = new byte[(limitPos + 7) / 8];
       if (buf.length == 0) {
           return buf;
       }
       for (int i = 0; ; ) {
           int v = map[i / 4];
           buf[i++] = (byte) (v >>> 24);
           if (i == buf.length) {
               break;
           }
           buf[i++] = (byte) (v >>> 16);
           if (i == buf.length) {
               break;
           }
           buf[i++] = (byte) (v >>> 8);
           if (i == buf.length) {
               break;
           }
           buf[i++] = (byte) v;
           if (i == buf.length) {
               break;
           }
       }
       return buf;
   }
   private void doubleCapacity() {
       int[] newmap = new int[map.length * 2];
       capacity *= 2;
       System.arraycopy(map, 0, newmap, 0, map.length);
       map = newmap;
   }
   /**
    * copy the byte value into the map at given position (0, 24)
    */
   public static int setByte(int map, byte value, int pos) {
       int intValue = (value & 0xff) << (24 - pos);
       int mask     = 0xff000000 >>> pos;
       mask = ~mask;
       map  &= mask;
       return (map | intValue);
   }
   public static int set(int map, int pos) {
       int mask = 0x80000000 >>> pos;
       return (map | mask);
   }
   public static byte set(byte map, int pos) {
       int mask = 0x00000080 >>> pos;
       return (byte) (map | mask);
   }
   public static int unset(int map, int pos) {
       int mask = 0x80000000 >>> pos;
       mask = ~mask;
       return (map & mask);
   }
   public static boolean isSet(int map, int pos) {
       int mask = 0x80000000 >>> pos;
       return (map & mask) == 0 ? false
                                : true;
   }
   public static boolean isSet(byte map, int pos) {
       int mask = 0x00000080 >>> pos;
       return (map & mask) == 0 ? false
                                : true;
   }
   public static boolean isSet(byte[] map, int pos) {
       int mask  = 0x00000080 >>> (pos & 0x07);;
       int index = pos / 8;
       if (index >= map.length) {
           return false;
       }
       byte b = map[index];
       return (b & mask) == 0 ? false
                              : true;
   }
   public static void unset(byte[] map, int pos) {
       int mask = 0x00000080 >>> (pos & 0x07);
       mask = ~mask;
       int index = pos / 8;
       if (index >= map.length) {
           return;
       }
       byte b = map[index];
       map[index] = (byte) (b & mask);
   }
   public static void set(byte[] map, int pos) {
       int mask  = 0x00000080 >>> (pos & 0x07);
       int index = pos / 8;
       if (index >= map.length) {
           return;
       }
       byte b = map[index];
       map[index] = (byte) (b | mask);
   }
   /**
    * AND count bits from source with map contents starting at pos
    */
   public static void and(byte[] map, int pos, byte source, int count) {
       int shift     = pos & 0x07;
       int mask      = (source & 0xff) >>> shift;
       int innermask = 0xff >> shift;
       int index     = pos / 8;
       if (count < 8) {
           innermask = innermask >>> (8 - count);
           innermask = innermask << (8 - count);
       }
       mask      &= innermask;
       innermask = ~innermask;
       if (index >= map.length) {
           return;
       }
       byte b = map[index];
       map[index] = (byte) (b & innermask);
       b          = (byte) (b & mask);
       map[index] = (byte) (map[index] | b);
       if (shift == 0) {
           return;
       }
       shift = 8 - shift;
       if (count > shift) {
           mask           = ((source & 0xff) << 8) >>> shift;
           innermask      = 0xff00 >>> shift;
           innermask      = ~innermask;
           b              = map[index + 1];
           map[index + 1] = (byte) (b & innermask);
           b              = (byte) (b & mask);
           map[index + 1] = (byte) (map[index + 1] | b);
       }
   }
   /**
    * OR count bits from source with map contents starting at pos
    */
   public static void or(byte[] map, int pos, byte source, int count) {
       int shift = pos & 0x07;
       int mask  = (source & 0xff) >>> shift;
       int index = pos / 8;
       if (index >= map.length) {
           return;
       }
       byte b = (byte) (map[index] | mask);
       map[index] = b;
       if (shift == 0) {
           return;
       }
       shift = 8 - shift;
       if (count > shift) {
           mask           = ((source & 0xff) << 8) >>> shift;
           b              = (byte) (map[index + 1] | mask);
           map[index + 1] = b;
       }
   }
   /**
    * overlay count bits from source on map contents starting at pos
    */
   public static void overlay(byte[] map, int pos, byte source, int count) {
       int shift     = pos & 0x07;
       int mask      = (source & 0xff) >>> shift;
       int innermask = 0xff >> shift;
       int index     = pos / 8;
       if (count < 8) {
           innermask = innermask >>> (8 - count);
           innermask = innermask << (8 - count);
       }
       mask      &= innermask;
       innermask = ~innermask;
       if (index >= map.length) {
           return;
       }
       byte b = map[index];
       b          = (byte) (b & innermask);
       map[index] = (byte) (b | mask);
       if (shift == 0) {
           return;
       }
       shift = 8 - shift;
       if (count > shift) {
           mask           = ((source & 0xff) << 8) >>> shift;
           innermask      = 0xff00 >>> shift;
           innermask      = ~innermask;
           b              = map[index + 1];
           b              = (byte) (b & innermask);
           map[index + 1] = (byte) (b | mask);
       }
   }
   public static int compare(byte[] a, byte[] b) {
       int shortLength = a.length > b.length ? b.length
                                             : a.length;
       for (int i = 0; i < shortLength; i++) {
           if (a[i] == b[i]) {
               continue;
           }
           return (((int) a[i]) & 0xff) > (((int) b[i]) & 0xff) ? 1
                                                                : -1;
       }
       if (a.length == b.length) {
           return 0;
       }
       return a.length > b.length ? 1
                                  : -1;
   }
   public static byte[] and(byte[] a, byte[] b) {
       int    length      = a.length > b.length ? a.length
                                                : b.length;
       int    shortLength = a.length > b.length ? b.length
                                                : a.length;
       byte[] map         = new byte[length];
       for (int i = 0; i < shortLength; i++) {
           map[i] = (byte) (a[i] & b[i]);
       }
       return map;
   }
   public static byte[] or(byte[] a, byte[] b) {
       int    length      = a.length > b.length ? a.length
                                                : b.length;
       int    shortLength = a.length > b.length ? b.length
                                                : a.length;
       byte[] map         = new byte[length];
       if (length != shortLength) {
           byte[] source = a.length > b.length ? a
                                               : b;
           System.arraycopy(source, shortLength, map, shortLength,
                            length - shortLength);
       }
       for (int i = 0; i < shortLength; i++) {
           map[i] = (byte) (a[i] | b[i]);
       }
       return map;
   }
   public static byte[] xor(byte[] a, byte[] b) {
       int    length      = a.length > b.length ? a.length
                                                : b.length;
       int    shortLength = a.length > b.length ? b.length
                                                : a.length;
       byte[] map         = new byte[length];
       if (length != shortLength) {
           byte[] source = a.length > b.length ? a
                                               : b;
           System.arraycopy(source, shortLength, map, shortLength,
                            length - shortLength);
       }
       for (int i = 0; i < shortLength; i++) {
           map[i] = (byte) (a[i] ^ b[i]);
       }
       return map;
   }
   public static byte[] not(byte[] a) {
       byte[] map = new byte[a.length];
       for (int i = 0; i < a.length; i++) {
           map[i] = (byte) ~a[i];
       }
       return map;
   }
   public static boolean hasAnyBitSet(byte[] map) {
       for (int i = 0; i < map.length; i++) {
           if (map[i] != 0) {
               return true;
           }
       }
       return false;
   }
   public static byte[] leftShift(byte[] map, int shiftBits) {
       byte[] newMap     = new byte[map.length];
       int    shiftBytes = shiftBits / 8;
       if (shiftBytes >= map.length) {
           return newMap;
       }
       shiftBits = shiftBits % 8;
       if (shiftBits == 0) {
           for (int i = 0, j = shiftBytes; j < map.length; i++, j++) {
               newMap[i] = map[j];
           }
       } else {
           for (int i = 0, j = shiftBytes; j < map.length; i++, j++) {
               int shifted = (map[j] & 0xff) << shiftBits;
               newMap[i] = (byte) shifted;
               if (i > 0) {
                   newMap[i - 1] |= (byte) (shifted >>> 8);
               }
           }
       }
       return newMap;
   }

}</source>

IntMap provides a simple hashmap from keys to integers

   <source lang="java">

/*

* Copyright (c) 2001-2008 Caucho Technology, Inc.  All rights reserved.
*
* The Apache Software License, Version 1.1
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in
*    the documentation and/or other materials provided with the
*    distribution.
*
* 3. The end-user documentation included with the redistribution, if
*    any, must include the following acknowlegement:
*       "This product includes software developed by the
*        Caucho Technology (http://www.caucho.ru/)."
*    Alternately, this acknowlegement may appear in the software itself,
*    if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "Burlap", "Resin", and "Caucho" must not be used to
*    endorse or promote products derived from this software without prior
*    written permission. For written permission, please contact
*    info@caucho.ru.
*
* 5. Products derived from this software may not be called "Resin"
*    nor may "Resin" appear in their names without prior written
*    permission of Caucho Technology.
*
* THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED.  IN NO EVENT SHALL CAUCHO TECHNOLOGY OR ITS CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
* OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
* OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
* IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* @author Scott Ferguson
*/

/**

* The IntMap provides a simple hashmap from keys to integers.  The API is
* an abbreviation of the HashMap collection API.
*
* The convenience of IntMap is avoiding all the silly wrapping of
* integers.
*/

public class IdentityIntMap {

 /**
  * Encoding of a null entry.  Since NULL is equal to Integer.MIN_VALUE, 
  * it"s impossible to distinguish between the two.
  */
 public final static int NULL = 0xdeadbeef; // Integer.MIN_VALUE + 1;
 private static final Object DELETED = new Object();
 private Object []_keys;
 private int []_values;
 private int _size;
 private int _mask;
 /**
  * Create a new IntMap.  Default size is 16.
  */
 public IdentityIntMap()
 {
   _keys = new Object[256];
   _values = new int[256];
   _mask = _keys.length - 1;
   _size = 0;
 }
 /**
  * Clear the hashmap.
  */
 public void clear()
 {
   Object []keys = _keys;
   int []values = _values;
   for (int i = keys.length - 1; i >= 0; i--) {
     keys[i] = null;
     values[i] = 0;
   }
   _size = 0;
 }
 /**
  * Returns the current number of entries in the map.
  */
 public int size()
 {
   return _size;
 }
 /**
  * Puts a new value in the property table with the appropriate flags
  */
 public int get(Object key)
 {
   int mask = _mask;
   int hash = System.identityHashCode(key) % mask & mask;
   Object []keys = _keys;
   while (true) {
     Object mapKey = keys[hash];
     if (mapKey == null)
       return NULL;
     else if (mapKey == key)
       return _values[hash];
     hash = (hash + 1) % mask;
   }
 }
 /**
  * Expands the property table
  */
 private void resize(int newSize)
 {
   Object []newKeys = new Object[newSize];
   int []newValues = new int[newSize];
   int mask = _mask = newKeys.length - 1;
   Object []keys = _keys;
   int values[] = _values;
   for (int i = keys.length - 1; i >= 0; i--) {
     Object key = keys[i];
     if (key == null || key == DELETED)
       continue;
     int hash = System.identityHashCode(key) % mask & mask;
     while (true) {
       if (newKeys[hash] == null) {
         newKeys[hash] = key;
         newValues[hash] = values[i];
         break;
       }
       hash = (hash + 1) % mask;
     }
   }
   _keys = newKeys;
   _values = newValues;
 }
 /**
  * Puts a new value in the property table with the appropriate flags
  */
 public int put(Object key, int value)
 {
   int mask = _mask;
   int hash = System.identityHashCode(key) % mask & mask;
   Object []keys = _keys;
   while (true) {
     Object testKey = keys[hash];
     if (testKey == null || testKey == DELETED) {
       keys[hash] = key;
       _values[hash] = value;
       _size++;
       if (keys.length <= 4 * _size)
         resize(4 * keys.length);
       return NULL;
     }
     else if (key != testKey) {
       hash = (hash + 1) % mask;
       continue;
     }
     else {
       int old = _values[hash];
       _values[hash] = value;
       return old;
     }
   }
 }
 /**
  * Deletes the entry.  Returns true if successful.
  */
 public int remove(Object key)
 {
   int mask = _mask;
   int hash = System.identityHashCode(key) % mask & mask;
   while (true) {
     Object mapKey = _keys[hash];
     if (mapKey == null)
       return NULL;
     else if (mapKey == key) {
       _keys[hash] = DELETED;
       _size--;
       return _values[hash];
     }
     hash = (hash + 1) % mask;
   }
 }
 public String toString()
 {
   StringBuffer sbuf = new StringBuffer();
   sbuf.append("IntMap[");
   boolean isFirst = true;
   for (int i = 0; i <= _mask; i++) {
     if (_keys[i] != null && _keys[i] != DELETED) {
       if (! isFirst)
         sbuf.append(", ");
       isFirst = false;
       sbuf.append(_keys[i]);
       sbuf.append(":");
       sbuf.append(_values[i]);
     }
   }
   sbuf.append("]");
   return sbuf.toString();
 }

}</source>

List ordered map

   <source lang="java">

/*

* Copyright 2004, 2005, 2006 Odysseus Software GmbH
*
* 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.
*/

import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set; /**

* 
* List ordered map.
* The iterators returned by keySet(), values()
* and entrySet() methods reflect the order in which keys have
* been added to the map.
*
* @author Christoph Beck
*/

public class ListOrderedMap implements Map {

 private final Map map;
 private final List lst; 
 public static Map decorate(Map map) {
   return new ListOrderedMap(map, new ArrayList());
 }
 
 protected ListOrderedMap(Map map, List lst) {
   super();
   
   this.map = map;
   this.lst = lst;
   lst.addAll(map.keySet());
 }
   public boolean containsKey(Object key) {
       return map.containsKey(key);
   }
   public boolean containsValue(Object value) {
       return map.containsValue(value);
   }
   public Object get(Object key) {
       return map.get(key);
   }
   public boolean isEmpty() {
       return map.isEmpty();
   }
   public int size() {
       return map.size();
   }
  
   public boolean equals(Object object) {
     return object == this ? true : map.equals(object); 
   }
   public int hashCode() {
       return map.hashCode();
   }
 public Object put(Object key, Object value) {
   if (!map.containsKey(key)) {
     lst.add(key);
   }
   return map.put(key, value);
 }
 public void putAll(Map map) {
   Iterator it = map.entrySet().iterator();
   while (it.hasNext()) {
     Map.Entry entry = (Map.Entry) it.next();
     put(entry.getKey(), entry.getValue());
   }
 }
 public Object remove(Object key) {
   if (map.containsKey(key)) {
     lst.remove(key);
     return map.remove(key);
   }
   return null;
 }
 public void clear() {
   map.clear();
   lst.clear();
 }
 public Collection values() {
   return new AbstractCollection() {
     public int size() {
       return map.size();
     }
     public boolean contains(Object value) {
       return map.containsValue(value);
     }
     public void clear() {
       ListOrderedMap.this.clear();
     }
     public Iterator iterator() {
       return new Iterator() {
         Object last = null;
         Iterator keys = lst.iterator();
         public Object next() {
           return map.get(last = keys.next());
         }
         public boolean hasNext() {
           return keys.hasNext();
         }
         public void remove() {
           keys.remove();
           map.remove(last);
         }
       };
     }
   };
 }
 public Set keySet() {
   return new AbstractSet() {
     public int size() {
       return map.size();
     }
     public boolean contains(Object value) {
       return map.containsKey(value);
     }
     public void clear() {
       ListOrderedMap.this.clear();
     }
     public Iterator iterator() {
       return new Iterator() {
         Object last = null;
         Iterator keys = lst.iterator();
         public Object next() {
           return last = keys.next();
         }
         public boolean hasNext() {
           return keys.hasNext();
         }
         public void remove() {
           keys.remove();
           map.remove(last);
         }
       };
     }
   };
 }
 
 public Set entrySet() {
   return new AbstractSet() {
     Set delegate = ListOrderedMap.this.map.entrySet();
     public int size() {
       return ListOrderedMap.this.size();
     }
     public boolean contains(Object obj) {
       return delegate.contains(obj);
     }
     public boolean remove(Object obj) {
       boolean result = contains(obj);
       if (result) {
         ListOrderedMap.this.remove(((Map.Entry)obj).getKey());
       }
       return result;
     }
     public void clear() {
       ListOrderedMap.this.clear();
     }
     public boolean equals(Object obj) {
       return obj == this ? true : delegate.equals(obj);
     }
     public int hashCode() {
       return delegate.hashCode();
     }
     public String toString() {
       return delegate.toString();
     }
     public Iterator iterator() {
       return new Iterator() {
         Iterator keys = lst.iterator();
         Object last = null;
         public Object next() {
           last = keys.next();
           return new Map.Entry() {
             Object key = last;
             public Object getKey() {
               return key;
             }
             public Object getValue() {
               return map.get(key);
             }
             public Object setValue(Object value) {
               return map.put(key, value);
             }
           };
         }
         public boolean hasNext() {
           return keys.hasNext();
         }
         public void remove() {
           keys.remove();
           map.remove(last);
         }
       };
     }
   };
 }
 public String toString() {
   StringBuffer buf = new StringBuffer();
   buf.append("{");
   Iterator keys = keySet().iterator();
   while (keys.hasNext()) {
     Object key = keys.next();
     buf.append(key);
     buf.append("=");
     buf.append(get(key));
     if (keys.hasNext()) {
       buf.append(", ");
     }
   }
   buf.append("}");
   return buf.toString();
 }

}</source>

Lookup table that stores a list of strings

   <source lang="java">

/*

* 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.
*/

/*

* $Id: StringToIntTable.java 468655 2006-10-28 07:12:06Z minchau $
*/

/**

* A very simple lookup table that stores a list of strings, the even
* number strings being keys, and the odd number strings being values.
* @xsl.usage internal
*/

public class StringToIntTable {

 public static final int INVALID_KEY = -10000;
 
 /** Block size to allocate          */
 private int m_blocksize;
 /** Array of strings this table points to. Associated with ints
  * in m_values         */
 private String m_map[];
 /** Array of ints this table points. Associated with strings from
  * m_map.         */
 private int m_values[];
 /** Number of ints in the table          */
 private int m_firstFree = 0;
 /** Size of this table         */
 private int m_mapSize;
 /**
  * Default constructor.  Note that the default
  * block size is very small, for small lists.
  */
 public StringToIntTable()
 {
   m_blocksize = 8;
   m_mapSize = m_blocksize;
   m_map = new String[m_blocksize];
   m_values = new int[m_blocksize];
 }
 /**
  * Construct a StringToIntTable, using the given block size.
  *
  * @param blocksize Size of block to allocate
  */
 public StringToIntTable(int blocksize)
 {
   m_blocksize = blocksize;
   m_mapSize = blocksize;
   m_map = new String[blocksize];
   m_values = new int[m_blocksize];
 }
 /**
  * Get the length of the list.
  *
  * @return the length of the list 
  */
 public final int getLength()
 {
   return m_firstFree;
 }
 /**
  * Append a string onto the vector.
  *
  * @param key String to append
  * @param value The int value of the string
  */
 public final void put(String key, int value)
 {
   if ((m_firstFree + 1) >= m_mapSize)
   {
     m_mapSize += m_blocksize;
     String newMap[] = new String[m_mapSize];
     System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
     m_map = newMap;
     int newValues[] = new int[m_mapSize];
     System.arraycopy(m_values, 0, newValues, 0, m_firstFree + 1);
     m_values = newValues;
   }
   m_map[m_firstFree] = key;
   m_values[m_firstFree] = value;
   m_firstFree++;
 }
 /**
  * Tell if the table contains the given string.
  *
  * @param key String to look for
  *
  * @return The String"s int value
  * 
  */
 public final int get(String key)
 {
   for (int i = 0; i < m_firstFree; i++)
   {
     if (m_map[i].equals(key))
       return m_values[i];
   }
 return INVALID_KEY;
 }
 /**
  * Tell if the table contains the given string. Ignore case.
  *
  * @param key String to look for
  *
  * @return The string"s int value
  */
 public final int getIgnoreCase(String key)
 {
   if (null == key)
       return INVALID_KEY;
   for (int i = 0; i < m_firstFree; i++)
   {
     if (m_map[i].equalsIgnoreCase(key))
       return m_values[i];
   }
   return INVALID_KEY;
 }
 /**
  * Tell if the table contains the given string.
  *
  * @param key String to look for
  *
  * @return True if the string is in the table
  */
 public final boolean contains(String key)
 {
   for (int i = 0; i < m_firstFree; i++)
   {
     if (m_map[i].equals(key))
       return true;
   }
   return false;
 }
 
 /**
  * Return array of keys in the table.
  * 
  * @return Array of strings
  */
 public final String[] keys()
 {
   String [] keysArr = new String[m_firstFree];
   for (int i = 0; i < m_firstFree; i++)
   {
     keysArr[i] = m_map[i];
   }
   return keysArr;
 }  

}</source>

Map implementation Optimized for Strings keys

   <source lang="java">

// Copyright 2004-2005 Mort Bay Consulting Pty. Ltd. // ------------------------------------------------------------------------ // 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.

import java.io.Externalizable; import java.util.AbstractMap; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; /* ------------------------------------------------------------ */ /** Map implementation Optimized for Strings keys..

* This String Map has been optimized for mapping small sets of
* Strings where the most frequently accessed Strings have been put to
* the map first.
*
* It also has the benefit that it can look up entries by substring or
* sections of char and byte arrays.  This can prevent many String
* objects from being created just to look up in the map.
*
* This map is NOT synchronized.
*
* @author Greg Wilkins (gregw)
*/

public class StringMap extends AbstractMap implements Externalizable {

   public static final boolean CASE_INSENSTIVE=true;
   protected static final int __HASH_WIDTH=17;
   
   /* ------------------------------------------------------------ */
   protected int _width=__HASH_WIDTH;
   protected Node _root=new Node();
   protected boolean _ignoreCase=false;
   protected NullEntry _nullEntry=null;
   protected Object _nullValue=null;
 protected HashSet _entrySet=new HashSet(3);
 protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet);
   
   /* ------------------------------------------------------------ */
   /** Constructor. 
    */
   public StringMap()
   {}
   
   /* ------------------------------------------------------------ */
   /** Constructor. 
    * @param ignoreCase 
    */
   public StringMap(boolean ignoreCase)
   {
       this();
       _ignoreCase=ignoreCase;
   }
   
   /* ------------------------------------------------------------ */
   /** Constructor. 
    * @param ignoreCase 
    * @param width Width of hash tables, larger values are faster but
    * use more memory.
    */
   public StringMap(boolean ignoreCase,int width)
   {
       this();
       _ignoreCase=ignoreCase;
       _width=width;
   }
   
   /* ------------------------------------------------------------ */
   /** Set the ignoreCase attribute.
    * @param ic If true, the map is case insensitive for keys.
    */
   public void setIgnoreCase(boolean ic)
   {
       if (_root._children!=null)
           throw new IllegalStateException("Must be set before first put");
       _ignoreCase=ic;
   }
   /* ------------------------------------------------------------ */
   public boolean isIgnoreCase()
   {
       return _ignoreCase;
   }
   /* ------------------------------------------------------------ */
   /** Set the hash width.
    * @param width Width of hash tables, larger values are faster but
    * use more memory.
    */
   public void setWidth(int width)
   {
       _width=width;
   }
   /* ------------------------------------------------------------ */
   public int getWidth()
   {
       return _width;
   }
   
   /* ------------------------------------------------------------ */
   public Object put(Object key, Object value)
   {
       if (key==null)
           return put(null,value);
       return put(key.toString(),value);
   }
       
   /* ------------------------------------------------------------ */
   public Object put(String key, Object value)
   {
       if (key==null)
       {
           Object oldValue=_nullValue;
           _nullValue=value;
           if (_nullEntry==null)
           {   
               _nullEntry=new NullEntry();
               _entrySet.add(_nullEntry);
           }
           return oldValue;
       }
       
       Node node = _root;
       int ni=-1;
       Node prev = null;
       Node parent = null;
       // look for best match
   charLoop:
       for (int i=0;i<key.length();i++)
       {
           char c=key.charAt(i);
           
           // Advance node
           if (ni==-1)
           {
               parent=node;
               prev=null;
               ni=0;
               node=(node._children==null)?null:node._children[c%_width];
           }
           
           // Loop through a node chain at the same level
           while (node!=null) 
           {
               // If it is a matching node, goto next char
               if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
               {
                   prev=null;
                   ni++;
                   if (ni==node._char.length)
                       ni=-1;
                   continue charLoop;
               }
               // no char match
               // if the first char,
               if (ni==0)
               {
                   // look along the chain for a char match
                   prev=node;
                   node=node._next;
               }
               else
               {
                   // Split the current node!
                   node.split(this,ni);
                   i--;
                   ni=-1;
                   continue charLoop;
               }
           }
           // We have run out of nodes, so as this is a put, make one
           node = new Node(_ignoreCase,key,i);
           if (prev!=null) // add to end of chain
               prev._next=node;
           else if (parent!=null) // add new child
           {
               if (parent._children==null)
                   parent._children=new Node[_width];
               parent._children[c%_width]=node;
               int oi=node._ochar[0]%_width;
               if (node._ochar!=null && node._char[0]%_width!=oi)
               {
                   if (parent._children[oi]==null)
                       parent._children[oi]=node;
                   else
                   {
                       Node n=parent._children[oi];
                       while(n._next!=null)
                           n=n._next;
                       n._next=node;
                   }
               }
           }
           else // this is the root.
               _root=node;
           break;
       }
       
       // Do we have a node
       if (node!=null)
       {
           // Split it if we are in the middle
           if(ni>0)
               node.split(this,ni);
       
           Object old = node._value;
           node._key=key;
           node._value=value;
           _entrySet.add(node);
           return old;
       }
       return null;
   }
   
   /* ------------------------------------------------------------ */
   public Object get(Object key)
   {
       if (key==null)
           return _nullValue;
       if (key instanceof String)
           return get((String)key);
       return get(key.toString());
   }
   
   /* ------------------------------------------------------------ */
   public Object get(String key)
   {
       if (key==null)
           return _nullValue;
       
       Map.Entry entry = getEntry(key,0,key.length());
       if (entry==null)
           return null;
       return entry.getValue();
   }
   
   /* ------------------------------------------------------------ */
   /** Get a map entry by substring key.
    * @param key String containing the key
    * @param offset Offset of the key within the String.
    * @param length The length of the key 
    * @return The Map.Entry for the key or null if the key is not in
    * the map.
    */
   public Map.Entry getEntry(String key,int offset, int length)
   {
       if (key==null)
           return _nullEntry;
       
       Node node = _root;
       int ni=-1;
       // look for best match
   charLoop:
       for (int i=0;i<length;i++)
       {
           char c=key.charAt(offset+i);
           // Advance node
           if (ni==-1)
           {
               ni=0;
               node=(node._children==null)?null:node._children[c%_width];
           }
           
           // Look through the node chain
           while (node!=null) 
           {
               // If it is a matching node, goto next char
               if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
               {
                   ni++;
                   if (ni==node._char.length)
                       ni=-1;
                   continue charLoop;
               }
               // No char match, so if mid node then no match at all.
               if (ni>0) return null;
               // try next in chain
               node=node._next;                
           }
           return null;
       }
       
       if (ni>0) return null;
       if (node!=null && node._key==null)
           return null;
       return node;
   }
   
   /* ------------------------------------------------------------ */
   /** Get a map entry by char array key.
    * @param key char array containing the key
    * @param offset Offset of the key within the array.
    * @param length The length of the key 
    * @return The Map.Entry for the key or null if the key is not in
    * the map.
    */
   public Map.Entry getEntry(char[] key,int offset, int length)
   {
       if (key==null)
           return _nullEntry;
       
       Node node = _root;
       int ni=-1;
       // look for best match
   charLoop:
       for (int i=0;i<length;i++)
       {
           char c=key[offset+i];
           // Advance node
           if (ni==-1)
           {
               ni=0;
               node=(node._children==null)?null:node._children[c%_width];
           }
           
           // While we have a node to try
           while (node!=null) 
           {
               // If it is a matching node, goto next char
               if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
               {
                   ni++;
                   if (ni==node._char.length)
                       ni=-1;
                   continue charLoop;
               }
               // No char match, so if mid node then no match at all.
               if (ni>0) return null;
               // try next in chain
               node=node._next;                
           }
           return null;
       }
       
       if (ni>0) return null;
       if (node!=null && node._key==null)
           return null;
       return node;
   }
   /* ------------------------------------------------------------ */
   /** Get a map entry by byte array key, using as much of the passed key as needed for a match.
    * A simple 8859-1 byte to char mapping is assumed.
    * @param key char array containing the key
    * @param offset Offset of the key within the array.
    * @param maxLength The length of the key 
    * @return The Map.Entry for the key or null if the key is not in
    * the map.
    */
   public Map.Entry getBestEntry(byte[] key,int offset, int maxLength)
   {
       if (key==null)
           return _nullEntry;
       
       Node node = _root;
       int ni=-1;
       // look for best match
   charLoop:
       for (int i=0;i<maxLength;i++)
       {
           char c=(char)key[offset+i];
           // Advance node
           if (ni==-1)
           {
               ni=0;
               
               Node child = (node._children==null)?null:node._children[c%_width];
               
               if (child==null && i>0)
                   return node; // This is the best match
               node=child;           
           }
           
           // While we have a node to try
           while (node!=null) 
           {
               // If it is a matching node, goto next char
               if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
               {
                   ni++;
                   if (ni==node._char.length)
                       ni=-1;
                   continue charLoop;
               }
               // No char match, so if mid node then no match at all.
               if (ni>0) return null;
               // try next in chain
               node=node._next;                
           }
           return null;
       }
       
       if (ni>0) return null;
       if (node!=null && node._key==null)
           return null;
       return node;
   }
   
   
   /* ------------------------------------------------------------ */
   public Object remove(Object key)
   {
       if (key==null)
           return remove(null);
       return remove(key.toString());
   }
   
   /* ------------------------------------------------------------ */
   public Object remove(String key)
   {
       if (key==null)
       {
           Object oldValue=_nullValue;
           if (_nullEntry!=null)
           {
               _entrySet.remove(_nullEntry);   
               _nullEntry=null;
               _nullValue=null;
           }
           return oldValue;
       }
       
       Node node = _root;
       int ni=-1;
       // look for best match
   charLoop:
       for (int i=0;i<key.length();i++)
       {
           char c=key.charAt(i);
           // Advance node
           if (ni==-1)
           {
               ni=0;
               node=(node._children==null)?null:node._children[c%_width];
           }
           
           // While we have a node to try
           while (node!=null) 
           {
               // If it is a matching node, goto next char
               if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
               {
                   ni++;
                   if (ni==node._char.length)
                       ni=-1;
                   continue charLoop;
               }
               // No char match, so if mid node then no match at all.
               if (ni>0) return null;
               // try next in chain
               node=node._next;         
           }
           return null;
       }
       if (ni>0) return null;
       if (node!=null && node._key==null)
           return null;
       
       Object old = node._value;
       _entrySet.remove(node);
       node._value=null;
       node._key=null;
       
       return old; 
   }
   /* ------------------------------------------------------------ */
   public Set entrySet()
   {
       return _umEntrySet;
   }
   
   /* ------------------------------------------------------------ */
   public int size()
   {
       return _entrySet.size();
   }
   /* ------------------------------------------------------------ */
   public boolean isEmpty()
   {
       return _entrySet.isEmpty();
   }
   /* ------------------------------------------------------------ */
   public boolean containsKey(Object key)
   {
       if (key==null)
           return _nullEntry!=null;
       return
           getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
   }
   
   /* ------------------------------------------------------------ */
   public void clear()
   {
       _root=new Node();
       _nullEntry=null;
       _nullValue=null;
       _entrySet.clear();
   }
   
   /* ------------------------------------------------------------ */
   /* ------------------------------------------------------------ */
   /* ------------------------------------------------------------ */
   private static class Node implements Map.Entry
   {
       char[] _char;
       char[] _ochar;
       Node _next;
       Node[] _children;
       String _key;
       Object _value;
       
       Node(){}
       
       Node(boolean ignoreCase,String s, int offset)
       {
           int l=s.length()-offset;
           _char=new char[l];
           _ochar=new char[l];
           for (int i=0;i<l;i++)
           {
               char c=s.charAt(offset+i);
               _char[i]=c;
               if (ignoreCase)
               {
                   char o=c;
                   if (Character.isUpperCase(c))
                       o=Character.toLowerCase(c);
                   else if (Character.isLowerCase(c))
                       o=Character.toUpperCase(c);
                   _ochar[i]=o;
               }
           }
       }
       Node split(StringMap map,int offset)
       {
           Node split = new Node();
           int sl=_char.length-offset;
           
           char[] tmp=this._char;
           this._char=new char[offset];
           split._char = new char[sl];
           System.arraycopy(tmp,0,this._char,0,offset);
           System.arraycopy(tmp,offset,split._char,0,sl);
           if (this._ochar!=null)
           {
               tmp=this._ochar;
               this._ochar=new char[offset];
               split._ochar = new char[sl];
               System.arraycopy(tmp,0,this._ochar,0,offset);
               System.arraycopy(tmp,offset,split._ochar,0,sl);
           }
           
           split._key=this._key;
           split._value=this._value;
           this._key=null;
           this._value=null;
           if (map._entrySet.remove(this))
               map._entrySet.add(split);
           split._children=this._children;            
           this._children=new Node[map._width];
           this._children[split._char[0]%map._width]=split;
           if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
               this._children[split._ochar[0]%map._width]=split;
           return split;
       }
       
       public Object getKey(){return _key;}
       public Object getValue(){return _value;}
       public Object setValue(Object o){Object old=_value;_value=o;return old;}
       public String toString()
       {
           StringBuffer buf=new StringBuffer();
           synchronized(buf)
           {
               toString(buf);
           }
           return buf.toString();
       }
       private void toString(StringBuffer buf)
       {
           buf.append("{[");
           if (_char==null)
               buf.append("-");
           else
               for (int i=0;i<_char.length;i++)
                   buf.append(_char[i]);
           buf.append(":");
           buf.append(_key);
           buf.append("=");
           buf.append(_value);
           buf.append("]");
           if (_children!=null)
           {
               for (int i=0;i<_children.length;i++)
               {
                   buf.append("|");
                   if (_children[i]!=null)
                       _children[i].toString(buf);
                   else
                       buf.append("-");
               }
           }
           buf.append("}");
           if (_next!=null)
           {
               buf.append(",\n");
               _next.toString(buf);
           }
       }
   }
   /* ------------------------------------------------------------ */
   /* ------------------------------------------------------------ */
   private class NullEntry implements Map.Entry
   {
       public Object getKey(){return null;}
       public Object getValue(){return _nullValue;}
       public Object setValue(Object o)
           {Object old=_nullValue;_nullValue=o;return old;}
       public String toString(){return "[:null="+_nullValue+"]";}
   }
   /* ------------------------------------------------------------ */
   public void writeExternal(java.io.ObjectOutput out)
       throws java.io.IOException
   {
       HashMap map = new HashMap(this);
       out.writeBoolean(_ignoreCase);
       out.writeObject(map);
   }
   
   /* ------------------------------------------------------------ */
   public void readExternal(java.io.ObjectInput in)
       throws java.io.IOException, ClassNotFoundException
   {
       boolean ic=in.readBoolean();
       HashMap map = (HashMap)in.readObject();
       setIgnoreCase(ic);
       this.putAll(map);
   }

}</source>

Map with keys iterated in insertion order

   <source lang="java">

/* Copyright (c) 2007, Dennis M. Sosnoski All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
* Neither the name of JiBX nor the names of its contributors may be used
  to endorse or promote products derived from this software without specific
  prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

• /

import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**

* Map with keys iterated in insertion order. This is similar to the Java 1.4
* java.util.LinkedHashMap class, but compatible with earlier JVM versions. It
* also guarantees insertion ordering only for iterating through the key values,
* not for other iterations. This implementation is optimized for insert-only
* maps.
*/

public class InsertionOrderedMap implements Map {

   private final Map m_baseMap;
   private final ArrayList m_insertList;
   
   public InsertionOrderedMap() {
       m_baseMap = new HashMap();
       m_insertList = new ArrayList();
   }
   
   /* (non-Javadoc)
    * @see java.util.Map#clear()
    */
   public void clear() {
       m_baseMap.clear();
       m_insertList.clear();
   }
   /* (non-Javadoc)
    * @see java.util.Map#containsKey(java.lang.Object)
    */
   public boolean containsKey(Object key) {
       return m_baseMap.containsKey(key);
   }
   /* (non-Javadoc)
    * @see java.util.Map#containsValue(java.lang.Object)
    */
   public boolean containsValue(Object value) {
       return m_baseMap.containsValue(value);
   }
   /* (non-Javadoc)
    * @see java.util.Map#entrySet()
    */
   public Set entrySet() {
       return m_baseMap.entrySet();
   }
   /* (non-Javadoc)
    * @see java.util.Map#get(java.lang.Object)
    */
   public Object get(Object key) {
       return m_baseMap.get(key);
   }
   /* (non-Javadoc)
    * @see java.util.Map#isEmpty()
    */
   public boolean isEmpty() {
       return m_baseMap.isEmpty();
   }
   /* (non-Javadoc)
    * @see java.util.Map#keySet()
    */
   public Set keySet() {
       return new ListSet(m_insertList);
   }
   /* (non-Javadoc)
    * @see java.util.Map#put(java.lang.Object, java.lang.Object)
    */
   public Object put(Object key, Object value) {
       if (!m_baseMap.containsKey(key)) {
           m_insertList.add(key);
       }
       return m_baseMap.put(key, value);
   }
   /* (non-Javadoc)
    * @see java.util.Map#putAll(java.util.Map)
    */
   public void putAll(Map t) {
       for (Iterator iter = t.entrySet().iterator(); iter.hasNext();) {
           Entry entry = (Entry)iter.next();
           put(entry.getKey(), entry.getValue());
       }
   }
   /* (non-Javadoc)
    * @see java.util.Map#remove(java.lang.Object)
    */
   public Object remove(Object key) {
       if (m_baseMap.containsKey(key)) {
           m_insertList.remove(key);
           return m_baseMap.remove(key);
       } else {
           return null;
       }
   }
   /* (non-Javadoc)
    * @see java.util.Map#size()
    */
   public int size() {
       return m_baseMap.size();
   }
   /* (non-Javadoc)
    * @see java.util.Map#values()
    */
   public Collection values() {
       return new ValueCollection();
   }
   
   /**
    * Get list of keys in order added. The returned list is live, and will
    * grow or shrink as pairs are added to or removed from the map.
    *
    * @return key list
    */
   public ArrayList keyList() {
       return m_insertList;
   }
   
   /**
    * Set implementation backed by a list.
    */
   protected static class ListSet extends AbstractSet
   {
       private final List m_list;
       
       public ListSet(List list) {
           m_list = list;
       }
       
       public Iterator iterator() {
           return m_list.iterator();
       }
       public int size() {
           return m_list.size();
       }
   }
   
   protected class ValueCollection extends AbstractCollection
   {
       public Iterator iterator() {
           return new ValueIterator();
       }
       public int size() {
           return m_insertList.size();
       }
   }
   
   protected class ValueIterator implements Iterator
   {
       private int m_index = -1;
       
       public boolean hasNext() {
           return m_index < m_insertList.size()-1;
       }
       public Object next() {
           if (m_index < m_insertList.size()-1) {
               Object key = m_insertList.get(++m_index);
               return m_baseMap.get(key);
           } else {
               throw new NoSuchElementException("Past end of list");
           }
       }
       public void remove() {
           throw new UnsupportedOperationException("Internal error - remove() not supported");
       }
   }

}</source>

Ordered Map

   <source lang="java">

import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Set; /**

* This is a simple Map implementation backed by a List of Map.Entry objects. 
* It has the property that iterators return entries in the order in whick
* they were inserted.
* 
* Operations involving searching, including get() and put(), have cost linear 
* to the size of the map. In other words, avoid this implementation if your 
* Map might get large.
* 
* If we could assume Java 1.4+, we"d just use java.util.LinkedHashMap 
* instead of this class.  But we can"t.
* 
* @author Mike Williams
*/

public class OrderedMap extends AbstractMap {

   private Set _entrySet = new OrderedSet();
   public Set entrySet() {
       return _entrySet;
   }
   public Object put(Object key, Object value) {
       Entry existingEntry = getEntryWithKey(key);
       if (existingEntry == null) {
           entrySet().add(new Entry(key, value));
           return null;
       }
       Object previousValue = existingEntry.getValue();
       existingEntry.setValue(value);
       return previousValue;
   }    
   private Entry getEntryWithKey(Object key) {
       Iterator i = entrySet().iterator();
       while (i.hasNext()) {
           Entry e = (Entry) i.next();
           if (eq(e.getKey(), key)) {
               return e;
           }
       }
       return null;
   }
   
   static class OrderedSet extends AbstractSet {
       private List _elementList = new LinkedList();
       public int size() {
           return _elementList.size();
       }
       public Iterator iterator() {
           return _elementList.iterator();
       }
       public boolean add(Object o) {
           _elementList.add(o);
           return true;
       }
       
   }
   static class Entry implements Map.Entry {
       
       Object _key;
       Object _value;
       public Entry(Object key, Object value) {
           _key = key;
           _value = value;
       }
       public Object getKey() {
           return _key;
       }
       public Object getValue() {
           return _value;
       }
       public Object setValue(Object value) {
           Object oldValue = _value;
           _value = value;
           return oldValue;
       }
       public boolean equals(Object o) {
           if (!(o instanceof Map.Entry)) {
               return false;
           }
           Map.Entry e = (Map.Entry) o;
           return eq(_key, e.getKey()) && eq(_value, e.getValue());
       }
       public int hashCode() {
           return ((_key == null) ? 0 : _key.hashCode()) ^
                  ((_value == null) ? 0 : _value.hashCode());
       }
       public String toString() {
           return _key + "=" + _value;
       }
   }
   private static boolean eq(Object o1, Object o2) {
       return (o1 == null ? o2 == null : o1.equals(o2));
   }
   

}</source>