Package com.linkedin.davinci.utils

Class IndexedHashMap<K,​V>

  • Type Parameters:
    K - the type of keys maintained by this map
    V - the type of mapped values
    All Implemented Interfaces:
    IndexedMap<K,​V>, java.util.Map<K,​V>
    public class IndexedHashMap<K,​V>
extends java.util.AbstractMap<K,​V>
implements IndexedMap<K,​V>
    This is a fork of the standard HashMap which implements IndexedMap. It is composed of an ArrayList to keep track of the insertion & iteration order of the entries. The performance of the various operations should be as follows: - The get and put performance should be constant-time, like HashMap. - The iteration performance should be equal or slightly better than HashMap, since a regular map needs to weed through some empty nodes which are part of the map's internal structure. - The delete performance should be worse than that of the HashMap, since it needs to do extra bookkeeping to keep the list and map nodes in sync, with a worse case of O(N). - The indexOf(key) should be constant-time, like HashMap's get. - The putByIndex should be O(N) in the worst case. - The getByIndex should be O(1). - The removeByIndex should be O(N) in the worst case. - The moveElement should be O(N) in the worst case. Compared to the standard HashMap, this implementation is a bit simplified since it doesn't attempt to provide support to the LinkedHashMap, doesn't support cloning, nor Java serialization.

    Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

       Map m = Collections.synchronizedMap(new IndexedHashMap(...));

    The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

    Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

    • Nested Class Summary

      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>

      • 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
      IndexedHashMap()
      Constructs an empty IndexedHashMap with the default initial capacity (16) and the default load factor (0.75).
      IndexedHashMap​(int initialCapacity)
      Constructs an empty IndexedHashMap with the specified initial capacity and the default load factor (0.75).
      IndexedHashMap​(int initialCapacity, float loadFactor)
      Constructs an empty IndexedHashMap with the specified initial capacity and load factor.
      IndexedHashMap​(int initialCapacity, float loadFactor, java.util.List<java.util.Map.Entry<K,​V>> entryList)
      Constructs an empty IndexedHashMap using the provided list implementation.
      IndexedHashMap​(java.util.Map<? extends K,​? extends V> m)
      Constructs a new IndexedHashMap with the same mappings as the specified Map.
      IndexedHashMap​(java.util.Map<? extends K,​? extends V> m, java.util.List<java.util.Map.Entry<K,​V>> entryList)
      Constructs a new IndexedHashMap with the same mappings as the specified Map.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Removes all of the mappings from this map.
      V compute​(K key, java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)  
      V computeIfAbsent​(K key, java.util.function.Function<? super K,​? extends V> mappingFunction)  
      V computeIfPresent​(K key, java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)  
      boolean containsKey​(java.lang.Object key)
      Returns true if this map contains a mapping for the specified key.
      boolean containsValue​(java.lang.Object value)
      Returns true if this map maps one or more keys to the specified value.
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
      Returns a Set view of the mappings contained in this map.
      void forEach​(java.util.function.BiConsumer<? super K,​? super V> action)  
      V get​(java.lang.Object key)
      Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
      java.util.Map.Entry<K,​V> getByIndex​(int index)
      O(1)
      V getOrDefault​(java.lang.Object key, V defaultValue)  
      int indexOf​(K key)
      Constant-time, as Map.get(Object)
      boolean isEmpty()
      Returns true if this map contains no key-value mappings.
      java.util.Set<K> keySet()
      Returns a Set view of the keys contained in this map.
      V merge​(K key, V value, java.util.function.BiFunction<? super V,​? super V,​? extends V> remappingFunction)  
      void moveElement​(int originalIndex, int newIndex)
      O(N) in the worst case.
      V put​(K key, V value)
      Associates the specified value with the specified key in this map.
      void putAll​(java.util.Map<? extends K,​? extends V> m)
      Copies all of the mappings from the specified map to this map.
      V putByIndex​(K key, V value, int index)
      O(N) in the worst case.
      V putIfAbsent​(K key, V value)  
      V remove​(java.lang.Object key)
      Removes the mapping for the specified key from this map if present.
      boolean remove​(java.lang.Object key, java.lang.Object value)  
      java.util.Map.Entry<K,​V> removeByIndex​(int index)
      O(N) in the worst case.
      V replace​(K key, V value)  
      boolean replace​(K key, V oldValue, V newValue)  
      void replaceAll​(java.util.function.BiFunction<? super K,​? super V,​? extends V> function)  
      int size()
      Returns the number of key-value mappings in this map.
      java.lang.String toString()
      Returns a string representation of this map.
      java.util.Collection<V> values()
      Returns a Collection view of the values contained in this map.

      • Methods inherited from class java.util.AbstractMap

        clone, equals, hashCode

      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.Map

        equals, hashCode

    • Constructor Detail

      • IndexedHashMap

        public IndexedHashMap​(int initialCapacity,
                      float loadFactor,
                      java.util.List<java.util.Map.Entry<K,​V>> entryList)
        Constructs an empty IndexedHashMap using the provided list implementation.
        Parameters:
        initialCapacity - the initial capacity
        loadFactor - the load factor
        entryList - the list which backs the iteration functionality of the map
        Throws:
        java.lang.IllegalArgumentException - if the initial capacity is negative or the load factor is nonpositive

      • IndexedHashMap

        public IndexedHashMap​(int initialCapacity,
                      float loadFactor)
        Constructs an empty IndexedHashMap with the specified initial capacity and load factor.
        Parameters:
        initialCapacity - the initial capacity
        loadFactor - the load factor
        Throws:
        java.lang.IllegalArgumentException - if the initial capacity is negative or the load factor is nonpositive

      • IndexedHashMap

        public IndexedHashMap​(int initialCapacity)
        Constructs an empty IndexedHashMap with the specified initial capacity and the default load factor (0.75).
        Parameters:
        initialCapacity - the initial capacity.
        Throws:
        java.lang.IllegalArgumentException - if the initial capacity is negative.

      • IndexedHashMap

        public IndexedHashMap()
        Constructs an empty IndexedHashMap with the default initial capacity (16) and the default load factor (0.75).

      • IndexedHashMap

        public IndexedHashMap​(java.util.Map<? extends K,​? extends V> m)
        Constructs a new IndexedHashMap with the same mappings as the specified Map.
        Parameters:
        m - the map whose mappings are to be placed in this map
        Throws:
        java.lang.NullPointerException - if the specified map is null

      • IndexedHashMap

        public IndexedHashMap​(java.util.Map<? extends K,​? extends V> m,
                      java.util.List<java.util.Map.Entry<K,​V>> entryList)
        Constructs a new IndexedHashMap with the same mappings as the specified Map. The IndexedHashMap is created with default load factor (0.75) and an initial capacity sufficient to hold the mappings in the specified Map. The ordering of the elements in the IndexedHashMap will be the same as the one provided by the Map.entrySet() of the passed in map. Depending on the implementation of the passed in map, that ordering may or may not be deterministic. If the passed in map later undergoes structural changes, the IndexedHashMap will still maintain the same initial ordering.
        Parameters:
        m - the map whose mappings are to be placed in this map
        Throws:
        java.lang.NullPointerException - if the specified map is null

    • Method Detail

      • size

        public int size()
        Returns the number of key-value mappings in this map.
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>
        Returns:
        the number of key-value mappings in this map

      • isEmpty

        public boolean isEmpty()
        Returns true if this map contains no key-value mappings.
        Specified by:
        isEmpty in interface java.util.Map<K,​V>
        Overrides:
        isEmpty in class java.util.AbstractMap<K,​V>
        Returns:
        true if this map contains no key-value mappings

      • get

        public V get​(java.lang.Object key)
        Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

        More formally, if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

        A return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey operation may be used to distinguish these two cases.

        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
        See Also:
        put(Object, Object)

      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Returns true if this map contains a mapping for the specified key.
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<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.

      • put

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

      • indexOf

        public int indexOf​(K key)
        Constant-time, as Map.get(Object)
        Specified by:
        indexOf in interface IndexedMap<K,​V>
        Returns:
        Index of the key or -1 if the key does not exist.

      • putByIndex

        public V putByIndex​(K key,
                    V value,
                    int index)
        O(N) in the worst case.
        Specified by:
        putByIndex in interface IndexedMap<K,​V>

      • getByIndex

        public java.util.Map.Entry<K,​V> getByIndex​(int index)
        O(1)
        Specified by:
        getByIndex in interface IndexedMap<K,​V>

      • removeByIndex

        public java.util.Map.Entry<K,​V> removeByIndex​(int index)
        O(N) in the worst case.
        Specified by:
        removeByIndex in interface IndexedMap<K,​V>

      • moveElement

        public void moveElement​(int originalIndex,
                        int newIndex)
        O(N) in the worst case.
        Specified by:
        moveElement in interface IndexedMap<K,​V>

      • toString

        public java.lang.String toString()
        Returns a string representation of this map. The string representation consists of a list of key-value mappings in the order returned by the map's entrySet view's iterator, enclosed in braces ("{}"). Adjacent mappings are separated by the characters ", " (comma and space). Each key-value mapping is rendered as the key followed by an equals sign ("=") followed by the associated value. Keys and values are converted to strings as by String.valueOf(Object).
        Overrides:
        toString in class java.util.AbstractMap<K,​V>
        Returns:
        a string representation of this map

      • putAll

        public void putAll​(java.util.Map<? extends K,​? extends V> m)
        Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this map had for any of the keys currently in the specified map.
        Specified by:
        putAll in interface java.util.Map<K,​V>
        Overrides:
        putAll in class java.util.AbstractMap<K,​V>
        Parameters:
        m - mappings to be stored in this map
        Throws:
        java.lang.NullPointerException - if the specified map is null

      • remove

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

      • clear

        public void clear()
        Removes all of the mappings from this map. The map will be empty after this call returns.
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>

      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Returns true if this map maps one or more keys to the specified value.
        Specified by:
        containsValue in interface java.util.Map<K,​V>
        Overrides:
        containsValue in class java.util.AbstractMap<K,​V>
        Parameters:
        value - value whose presence in this map is to be tested
        Returns:
        true if this map maps one or more keys to the specified value

      • keySet

        public java.util.Set<K> keySet()
        Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.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>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>
        Returns:
        a set view of the keys contained in this map

      • values

        public java.util.Collection<V> values()
        Returns a Collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. If the map is modified while an iteration over the collection is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The collection supports element removal, which removes the corresponding mapping from the 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>
        Overrides:
        values in class java.util.AbstractMap<K,​V>
        Returns:
        a view of the values contained in this map

      • entrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Returns a Set view of the mappings contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator) the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.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>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>
        Returns:
        a set view of the mappings contained in this map

      • getOrDefault

        public V getOrDefault​(java.lang.Object key,
                      V defaultValue)
        Specified by:
        getOrDefault in interface java.util.Map<K,​V>

      • putIfAbsent

        public V putIfAbsent​(K key,
                     V value)
        Specified by:
        putIfAbsent in interface java.util.Map<K,​V>

      • remove

        public boolean remove​(java.lang.Object key,
                      java.lang.Object value)
        Specified by:
        remove in interface java.util.Map<K,​V>

      • replace

        public boolean replace​(K key,
                       V oldValue,
                       V newValue)
        Specified by:
        replace in interface java.util.Map<K,​V>

      • replace

        public V replace​(K key,
                 V value)
        Specified by:
        replace in interface java.util.Map<K,​V>

      • computeIfAbsent

        public V computeIfAbsent​(K key,
                         java.util.function.Function<? super K,​? extends V> mappingFunction)
        Specified by:
        computeIfAbsent in interface java.util.Map<K,​V>

      • computeIfPresent

        public V computeIfPresent​(K key,
                          java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)
        Specified by:
        computeIfPresent in interface java.util.Map<K,​V>

      • compute

        public V compute​(K key,
                 java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)
        Specified by:
        compute in interface java.util.Map<K,​V>

      • merge

        public V merge​(K key,
               V value,
               java.util.function.BiFunction<? super V,​? super V,​? extends V> remappingFunction)
        Specified by:
        merge in interface java.util.Map<K,​V>

      • forEach

        public void forEach​(java.util.function.BiConsumer<? super K,​? super V> action)
        Specified by:
        forEach in interface java.util.Map<K,​V>

      • replaceAll

        public void replaceAll​(java.util.function.BiFunction<? super K,​? super V,​? extends V> function)
        Specified by:
        replaceAll in interface java.util.Map<K,​V>