Class FastMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.util.Map<K,​V>

    public class FastMap<K,​V>
    extends java.lang.Object
    implements java.util.Map<K,​V>, java.lang.Cloneable, java.io.Serializable

    This class represents a Map collection with real-time behavior. Unless the map's size exceeds its current capacity, no dynamic memory allocation is ever performed and response time is extremely fast and consistent.

    Our benchmark indicates that FastMap.put(key, value) is up to 5x faster than java.util.HashMap.put(key, value). This difference is mostly due to the cost of the Map.Entry allocations that FastMap avoids by recycling its entries (see note below).

    FastMap has a predictable iteration order, which is the order in which keys were inserted into the map (similar to java.util.LinkedHashMap collection class).

    Applications may change the resizing policy of FastMap by overriding the sizeChanged() method. For example, to improve predictability, automatic resizing can be disabled.

    This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized externally.

    Note: To avoid dynamic memory allocations, FastMap maintains an internal pool of Map.Entry objects. The size of the pool is determined by the map's capacity. When an entry is removed from the map, it is automatically restored to the pool.

    This class is public domain (not copyrighted).

    Version:
    5.3, October 31 2003
    See Also:
    Serialized Form
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  FastMap.EntryImpl<K,​V>
      This class represents a FastMap entry.
      private class  FastMap.EntrySet  
      private class  FastMap.KeySet  
      private class  FastMap.Values  
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Constructor Summary

      Constructors 
      Constructor Description
      FastMap()
      Creates a FastMap with a capacity of 256 entries.
      FastMap​(int capacity)
      Creates a FastMap with the specified capacity.
      FastMap​(java.util.Map map)
      Creates a FastMap, copy of the specified Map.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void addEntry​(java.lang.Object key, java.lang.Object value)
      Adds a new entry for the specified key and value.
      int capacity()
      Returns the capacity of this FastMap.
      void clear()
      Removes all mappings from this FastMap.
      java.lang.Object clone()
      Returns a shallow copy of this FastMap.
      boolean containsKey​(java.lang.Object key)
      Indicates if this FastMap contains a mapping for the specified key.
      boolean containsValue​(java.lang.Object value)
      Indicates if this FastMap maps one or more keys to the specified value.
      java.util.Set entrySet()
      Returns a collection view of the mappings contained in this FastMap.
      boolean equals​(java.lang.Object obj)
      Compares the specified object with this FastMap for equality.
      V get​(java.lang.Object key)
      Returns the value to which this FastMap maps the specified key.
      java.util.Map.Entry getEntry​(java.lang.Object key)
      Returns the entry with the specified key.
      int hashCode()
      Returns the hash code value for this FastMap.
      private void initialize​(int capacity)
      Initializes this instance for the specified capacity.
      boolean isEmpty()
      Indicates if this FastMap contains no key-value mappings.
      private static int keyHash​(java.lang.Object key)
      Returns the hash code for the specified key.
      java.util.Set keySet()
      Returns a set view of the keys contained in this FastMap.
      java.lang.Object put​(java.lang.Object key, java.lang.Object value)
      Associates the specified value with the specified key in this FastMap.
      void putAll​(java.util.Map<? extends K,​? extends V> map)
      Copies all of the mappings from the specified map to this FastMap.
      private void readObject​(java.io.ObjectInputStream stream)
      Requires special handling during de-serialization process.
      V remove​(java.lang.Object key)
      Removes the mapping for this key from this FastMap if present.
      private void removeEntry​(FastMap.EntryImpl entry)
      Removes the specified entry from the map.
      void setCapacity​(int newCapacity)
      Changes the current capacity of this FastMap.
      int size()
      Returns the number of key-value mappings in this FastMap.
      protected void sizeChanged()
      This methods is being called when the size of this FastMap has changed.
      java.lang.String toString()
      Returns a String representation of this FastMap.
      java.util.Collection values()
      Returns a collection view of the values contained in this FastMap.
      private void writeObject​(java.io.ObjectOutputStream stream)
      Requires special handling during serialization process.
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
    • Field Detail

      • _entries

        private transient FastMap.EntryImpl[] _entries
        Holds the map's hash table.
      • _capacity

        private transient int _capacity
        Holds the map's current capacity.
      • _mask

        private transient int _mask
        Holds the hash code mask.
      • _poolFirst

        private transient FastMap.EntryImpl _poolFirst
        Holds the first pool entry (linked list).
      • _mapFirst

        private transient FastMap.EntryImpl _mapFirst
        Holds the first map entry (linked list).
      • _mapLast

        private transient FastMap.EntryImpl _mapLast
        Holds the last map entry (linked list).
      • _size

        private transient int _size
        Holds the current size.
    • Constructor Detail

      • FastMap

        public FastMap()
        Creates a FastMap with a capacity of 256 entries.
      • FastMap

        public FastMap​(java.util.Map map)
        Creates a FastMap, copy of the specified Map. If the specified map is not an instance of FastMap, the newly created map has a capacity set to the specified map's size. The copy has the same order as the original, regardless of the original map's implementation:
             TreeMap dictionary = ...;
             FastMap dictionaryLookup = new FastMap(dictionary);
         
        Parameters:
        map - the map whose mappings are to be placed in this map.
      • FastMap

        public FastMap​(int capacity)
        Creates a FastMap with the specified capacity. Unless the capacity is exceeded, operations on this map do not allocate entries. For optimum performance, the capacity should be of the same order of magnitude or larger than the expected map's size.
        Parameters:
        capacity - the number of buckets in the hash table; it also defines the number of pre-allocated entries.
    • Method Detail

      • size

        public int size()
        Returns the number of key-value mappings in this FastMap.
        Specified by:
        size in interface java.util.Map<K,​V>
        Returns:
        this map's size.
      • capacity

        public int capacity()
        Returns the capacity of this FastMap. The capacity defines the number of buckets in the hash table, as well as the maximum number of entries the map may contain without allocating memory.
        Returns:
        this map's capacity.
      • isEmpty

        public boolean isEmpty()
        Indicates if this FastMap contains no key-value mappings.
        Specified by:
        isEmpty in interface java.util.Map<K,​V>
        Returns:
        true if this map contains no key-value mappings; false otherwise.
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Indicates if this FastMap contains a mapping for the specified key.
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Parameters:
        key - the key whose presence in this map is to be tested.
        Returns:
        true if this map contains a mapping for the specified key; false otherwise.
        Throws:
        java.lang.NullPointerException - if the key is null.
      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Indicates if this FastMap maps one or more keys to the specified value.
        Specified by:
        containsValue in interface java.util.Map<K,​V>
        Parameters:
        value - the value whose presence in this map is to be tested.
        Returns:
        true if this map maps one or more keys to the specified value.
        Throws:
        java.lang.NullPointerException - if the key is null.
      • get

        public V get​(java.lang.Object key)
        Returns the value to which this FastMap maps the specified key.
        Specified by:
        get in interface java.util.Map<K,​V>
        Parameters:
        key - the key whose associated value is to be returned.
        Returns:
        the value to which this map maps the specified key, or null if there is no mapping for the key.
        Throws:
        java.lang.NullPointerException - if key is null.
      • getEntry

        public java.util.Map.Entry getEntry​(java.lang.Object key)
        Returns the entry with the specified key.
        Parameters:
        key - the key whose associated entry is to be returned.
        Returns:
        the entry for the specified key or null if none.
      • put

        public java.lang.Object put​(java.lang.Object key,
                                    java.lang.Object value)
        Associates the specified value with the specified key in this FastMap. If the FastMap previously contained a mapping for this key, the old value is replaced.
        Specified by:
        put in interface java.util.Map<K,​V>
        Parameters:
        key - the key with which the specified value is to be associated.
        value - the value to be associated with the specified key.
        Returns:
        the previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.
        Throws:
        java.lang.NullPointerException - if the key is null.
      • putAll

        public void putAll​(java.util.Map<? extends K,​? extends V> map)
        Copies all of the mappings from the specified map to this FastMap.
        Specified by:
        putAll in interface java.util.Map<K,​V>
        Parameters:
        map - the mappings to be stored in this map.
        Throws:
        java.lang.NullPointerException - the specified map is null, or the specified map contains null keys.
      • remove

        public V remove​(java.lang.Object key)
        Removes the mapping for this key from this FastMap if present.
        Specified by:
        remove in interface java.util.Map<K,​V>
        Parameters:
        key - the key whose mapping is to be removed from the map.
        Returns:
        previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.
        Throws:
        java.lang.NullPointerException - if the key is null.
      • clear

        public void clear()
        Removes all mappings from this FastMap.
        Specified by:
        clear in interface java.util.Map<K,​V>
      • setCapacity

        public void setCapacity​(int newCapacity)
        Changes the current capacity of this FastMap. If the capacity is increased, new entries are allocated and added to the pool. If the capacity is decreased, entries from the pool are deallocated (and are eventually garbage collected). The capacity also determined the number of buckets for the hash table.
        Parameters:
        newCapacity - the new capacity of this map.
      • clone

        public java.lang.Object clone()
        Returns a shallow copy of this FastMap. The keys and the values themselves are not cloned.
        Overrides:
        clone in class java.lang.Object
        Returns:
        a shallow copy of this map.
      • equals

        public boolean equals​(java.lang.Object obj)
        Compares the specified object with this FastMap for equality. Returns true if the given object is also a map and the two maps represent the same mappings (regardless of collection iteration order).
        Specified by:
        equals in interface java.util.Map<K,​V>
        Overrides:
        equals in class java.lang.Object
        Parameters:
        obj - the object to be compared for equality with this map.
        Returns:
        true if the specified object is equal to this map; false otherwise.
      • hashCode

        public int hashCode()
        Returns the hash code value for this FastMap.
        Specified by:
        hashCode in interface java.util.Map<K,​V>
        Overrides:
        hashCode in class java.lang.Object
        Returns:
        the hash code value for this map.
      • toString

        public java.lang.String toString()
        Returns a String representation of this FastMap.
        Overrides:
        toString in class java.lang.Object
        Returns:
        this.entrySet().toString();
      • values

        public java.util.Collection values()
        Returns a collection view of the values contained in this FastMap. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
        Specified by:
        values in interface java.util.Map<K,​V>
        Returns:
        a collection view of the values contained in this map.
      • entrySet

        public java.util.Set entrySet()
        Returns a collection view of the mappings contained in this FastMap. Each element in the returned collection is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Returns:
        a collection view of the mappings contained in this map.
      • keySet

        public java.util.Set keySet()
        Returns a set view of the keys contained in this FastMap. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Returns:
        a set view of the keys contained in this map.
      • sizeChanged

        protected void sizeChanged()
        This methods is being called when the size of this FastMap has changed. The default behavior is to double the map's capacity when the map's size reaches the current map's capacity. Sub-class may override this method to implement custom resizing policies or to disable automatic resizing. For example:
         Map fixedCapacityMap = new FastMap( 256 )
         {
             protected sizeChanged()
             {
                 // Do nothing, automatic resizing disabled.
             }
         };
         
        See Also:
        setCapacity(int)
      • keyHash

        private static int keyHash​(java.lang.Object key)
        Returns the hash code for the specified key. The formula being used is identical to the formula used by java.util.HashMap (ensures similar behavior for ill-conditioned hashcode keys).
        Parameters:
        key - the key to calculate the hashcode for.
        Returns:
        the hash code for the specified key.
      • addEntry

        private void addEntry​(java.lang.Object key,
                              java.lang.Object value)
        Adds a new entry for the specified key and value.
        Parameters:
        key - the entry's key.
        value - the entry's value.
      • removeEntry

        private void removeEntry​(FastMap.EntryImpl entry)
        Removes the specified entry from the map.
        Parameters:
        entry - the entry to be removed.
      • initialize

        private void initialize​(int capacity)
        Initializes this instance for the specified capacity. Once initialized, operations on this map should not create new objects (unless the map's size exceeds the specified capacity).
        Parameters:
        capacity - the initial capacity.
      • readObject

        private void readObject​(java.io.ObjectInputStream stream)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Requires special handling during de-serialization process.
        Parameters:
        stream - the object input stream.
        Throws:
        java.io.IOException - if an I/O error occurs.
        java.lang.ClassNotFoundException - if the class for the object de-serialized is not found.
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream stream)
                          throws java.io.IOException
        Requires special handling during serialization process.
        Parameters:
        stream - the object output stream.
        Throws:
        java.io.IOException - if an I/O error occurs.