Package com.linkedin.davinci.utils

Class IndexedHashMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
com.linkedin.davinci.utils.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>, Map<K,V>
public class IndexedHashMap<K,V> extends 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.

  • Constructor Details

    • IndexedHashMap

      public IndexedHashMap(int initialCapacity, float loadFactor, List<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:
      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:
      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:
      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(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:
      NullPointerException - if the specified map is null

    • IndexedHashMap

      public IndexedHashMap(Map<? extends K,? extends V> m, List<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:
      NullPointerException - if the specified map is null

  • Method Details

    • size

      public int size()
      Returns the number of key-value mappings in this map.
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class 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 Map<K,V>
      Overrides:
      isEmpty in class AbstractMap<K,V>
      Returns:
      true if this map contains no key-value mappings

    • get

      public V get(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 Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
      See Also:

    • containsKey

      public boolean containsKey(Object key)
      Returns true if this map contains a mapping for the specified key.
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class 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 Map<K,V>
      Overrides:
      put in class 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 Map.Entry<K,V> getByIndex(int index)
      O(1)
      Specified by:
      getByIndex in interface IndexedMap<K,V>

    • removeByIndex

      public 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 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 AbstractMap<K,V>
      Returns:
      a string representation of this map

    • putAll

      public void putAll(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 Map<K,V>
      Overrides:
      putAll in class AbstractMap<K,V>
      Parameters:
      m - mappings to be stored in this map
      Throws:
      NullPointerException - if the specified map is null

    • remove

      public V remove(Object key)
      Removes the mapping for the specified key from this map if present.
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class 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 Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>

    • containsValue

      public boolean containsValue(Object value)
      Returns true if this map maps one or more keys to the specified value.
      Specified by:
      containsValue in interface Map<K,V>
      Overrides:
      containsValue in class 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 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 Map<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>
      Returns:
      a set view of the keys contained in this map

    • values

      public 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 Map<K,V>
      Overrides:
      values in class AbstractMap<K,V>
      Returns:
      a view of the values contained in this map

    • entrySet

      public Set<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 Map<K,V>
      Specified by:
      entrySet in class AbstractMap<K,V>
      Returns:
      a set view of the mappings contained in this map

    • getOrDefault

      public V getOrDefault(Object key, V defaultValue)
      Specified by:
      getOrDefault in interface Map<K,V>

    • putIfAbsent

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

    • remove

      public boolean remove(Object key, Object value)
      Specified by:
      remove in interface Map<K,V>

    • replace

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

    • replace

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

    • computeIfAbsent

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

    • computeIfPresent

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

    • compute

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

    • merge

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

    • forEach

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

    • replaceAll

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