Class UnifiedMapWithHashingStrategy<K,V>

All Implemented Interfaces:
Externalizable, Serializable, Cloneable, Iterable<V>, Map<K,V>, InternalIterable<V>, MapIterable<K,V>, MutableMap<K,V>, MutableMapIterable<K,V>, UnsortedMapIterable<K,V>, RichIterable<V>, BatchIterable<V>

public class UnifiedMapWithHashingStrategy<K,V> extends AbstractMutableMap<K,V> implements Externalizable, BatchIterable<V>
UnifiedMapWithHashingStrategy stores key/value pairs in a single array, where alternate slots are keys and values. This is nicer to CPU caches as consecutive memory addresses are very cheap to access. Entry objects are not stored in the table like in java.util.HashMap. Instead of trying to deal with collisions in the main array using Entry objects, we put a special object in the key slot and put a regular Object[] in the value slot. The array contains the key value pairs in consecutive slots, just like the main array, but it's a linear list with no hashing.

The difference between UnifiedMap and UnifiedMapWithHashingStrategy is that a HashingStrategy based UnifiedMap does not rely on the hashCode or equality of the object at the key, but instead relies on a HashingStrategy implementation provided by a developer to compute the hashCode and equals for the objects stored in the map.

See Also:
  • Field Details

    • NULL_KEY

      protected static final Object NULL_KEY
    • CHAINED_KEY

      protected static final Object CHAINED_KEY
    • DEFAULT_LOAD_FACTOR

      protected static final float DEFAULT_LOAD_FACTOR
      See Also:
    • DEFAULT_INITIAL_CAPACITY

      protected static final int DEFAULT_INITIAL_CAPACITY
      See Also:
    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • table

      protected transient Object[] table
    • occupied

      protected transient int occupied
    • loadFactor

      protected float loadFactor
    • maxSize

      protected int maxSize
    • hashingStrategy

      protected HashingStrategy<? super K> hashingStrategy
  • Constructor Details

    • UnifiedMapWithHashingStrategy

      @Deprecated public UnifiedMapWithHashingStrategy()
      Deprecated.
      No argument default constructor used for serialization. Instantiating an UnifiedMapWithHashingStrategyMultimap with this constructor will have a null hashingStrategy and throw NullPointerException when used.
    • UnifiedMapWithHashingStrategy

      public UnifiedMapWithHashingStrategy(HashingStrategy<? super K> hashingStrategy)
    • UnifiedMapWithHashingStrategy

      public UnifiedMapWithHashingStrategy(HashingStrategy<? super K> hashingStrategy, int initialCapacity)
    • UnifiedMapWithHashingStrategy

      public UnifiedMapWithHashingStrategy(HashingStrategy<? super K> hashingStrategy, int initialCapacity, float loadFactor)
    • UnifiedMapWithHashingStrategy

      public UnifiedMapWithHashingStrategy(HashingStrategy<? super K> hashingStrategy, Map<? extends K,? extends V> map)
    • UnifiedMapWithHashingStrategy

      public UnifiedMapWithHashingStrategy(HashingStrategy<? super K> hashingStrategy, Pair<K,V>... pairs)
  • Method Details

    • newMap

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMap(HashingStrategy<? super K> hashingStrategy)
    • newMap

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMap(HashingStrategy<? super K> hashingStrategy, int size)
    • newMap

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMap(HashingStrategy<? super K> hashingStrategy, int size, float loadFactor)
    • newMap

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMap(HashingStrategy<? super K> hashingStrategy, Map<? extends K,? extends V> map)
    • newMapWith

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMapWith(HashingStrategy<? super K> hashingStrategy, Iterable<Pair<K,V>> inputIterable)
    • newMap

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMap(UnifiedMapWithHashingStrategy<K,V> map)
    • newMapWith

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newMapWith(HashingStrategy<? super K> hashingStrategy, Pair<K,V>... pairs)
    • newWithKeysValues

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newWithKeysValues(HashingStrategy<? super K> hashingStrategy, K key, V value)
    • newWithKeysValues

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newWithKeysValues(HashingStrategy<? super K> hashingStrategy, K key1, V value1, K key2, V value2)
    • newWithKeysValues

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newWithKeysValues(HashingStrategy<? super K> hashingStrategy, K key1, V value1, K key2, V value2, K key3, V value3)
    • newWithKeysValues

      public static <K, V> UnifiedMapWithHashingStrategy<K,V> newWithKeysValues(HashingStrategy<? super K> hashingStrategy, K key1, V value1, K key2, V value2, K key3, V value3, K key4, V value4)
    • withKeysValues

      public UnifiedMapWithHashingStrategy<K,V> withKeysValues(K key, V value)
    • withKeysValues

      public UnifiedMapWithHashingStrategy<K,V> withKeysValues(K key1, V value1, K key2, V value2)
    • withKeysValues

      public UnifiedMapWithHashingStrategy<K,V> withKeysValues(K key1, V value1, K key2, V value2, K key3, V value3)
    • withKeysValues

      public UnifiedMapWithHashingStrategy<K,V> withKeysValues(K key1, V value1, K key2, V value2, K key3, V value3, K key4, V value4)
    • hashingStrategy

      public HashingStrategy<? super K> hashingStrategy()
    • clone

      Specified by:
      clone in interface MutableMap<K,V>
      Specified by:
      clone in class AbstractMutableMap<K,V>
    • newEmpty

      public MutableMap<K,V> newEmpty()
      Description copied from interface: MutableMapIterable
      Creates a new instance of the same type, using the default capacity and growth parameters.
      Specified by:
      newEmpty in interface MutableMap<K,V>
      Specified by:
      newEmpty in interface MutableMapIterable<K,V>
    • newEmpty

      public MutableMap<K,V> newEmpty(int capacity)
      Description copied from class: AbstractMutableMap
      Creates a new instance of the same type, using the given capacity and the default growth parameters.
      Specified by:
      newEmpty in class AbstractMutableMap<K,V>
    • fastCeil

      private int fastCeil(float v)
    • init

      protected int init(int initialCapacity)
    • allocate

      protected int allocate(int capacity)
    • allocateTable

      protected void allocateTable(int sizeToAllocate)
    • computeMaxSize

      protected void computeMaxSize(int capacity)
    • index

      protected int index(K key)
    • clear

      public void clear()
      Specified by:
      clear in interface Map<K,V>
    • put

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

      private V chainedPut(K key, int index, V value)
    • updateValue

      public V updateValue(K key, Function0<? extends V> factory, Function<? super V,? extends V> function)
      Description copied from interface: MutableMapIterable
      Looks up the value associated with key, applies the function to it, and replaces the value. If there is no value associated with key, starts it off with a value supplied by factory.
      Specified by:
      updateValue in interface MutableMapIterable<K,V>
      Overrides:
      updateValue in class AbstractMutableMapIterable<K,V>
    • chainedUpdateValue

      private V chainedUpdateValue(K key, int index, Function0<? extends V> factory, Function<? super V,? extends V> function)
    • updateValueWith

      public <P> V updateValueWith(K key, Function0<? extends V> factory, Function2<? super V,? super P,? extends V> function, P parameter)
      Description copied from interface: MutableMapIterable
      Same as MutableMapIterable.updateValue(Object, Function0, Function) with a Function2 and specified parameter which is passed to the function.
      Specified by:
      updateValueWith in interface MutableMapIterable<K,V>
      Overrides:
      updateValueWith in class AbstractMutableMapIterable<K,V>
    • chainedUpdateValueWith

      private <P> V chainedUpdateValueWith(K key, int index, Function0<? extends V> factory, Function2<? super V,? super P,? extends V> function, P parameter)
    • getIfAbsentPut

      public V getIfAbsentPut(K key, Function0<? extends V> function)
      Description copied from interface: MutableMapIterable
      Get and return the value in the Map at the specified key. Alternatively, if there is no value in the map at the key, return the result of evaluating the specified Function0, and put that value in the map at the specified key.
      Specified by:
      getIfAbsentPut in interface MutableMapIterable<K,V>
      Overrides:
      getIfAbsentPut in class AbstractMutableMapIterable<K,V>
    • chainedGetIfAbsentPut

      private V chainedGetIfAbsentPut(K key, int index, Function0<? extends V> function)
    • getIfAbsentPut

      public V getIfAbsentPut(K key, V value)
      Description copied from interface: MutableMapIterable
      Get and return the value in the Map at the specified key. Alternatively, if there is no value in the map at the key, return the specified value, and put that value in the map at the specified key.
      Specified by:
      getIfAbsentPut in interface MutableMapIterable<K,V>
      Overrides:
      getIfAbsentPut in class AbstractMutableMapIterable<K,V>
    • chainedGetIfAbsentPut

      private V chainedGetIfAbsentPut(K key, int index, V value)
    • getIfAbsentPutWith

      public <P> V getIfAbsentPutWith(K key, Function<? super P,? extends V> function, P parameter)
      Description copied from interface: MutableMapIterable
      Get and return the value in the Map at the specified key. Alternatively, if there is no value in the map for that key return the result of evaluating the specified Function using the specified parameter, and put that value in the map at the specified key.
      Specified by:
      getIfAbsentPutWith in interface MutableMapIterable<K,V>
      Overrides:
      getIfAbsentPutWith in class AbstractMutableMapIterable<K,V>
    • chainedGetIfAbsentPutWith

      private <P> V chainedGetIfAbsentPutWith(K key, int index, Function<? super P,? extends V> function, P parameter)
    • getCollidingBuckets

      public int getCollidingBuckets()
    • getMapMemoryUsedInWords

      public int getMapMemoryUsedInWords()
      Returns the number of JVM words that is used by this map. A word is 4 bytes in a 32bit VM and 8 bytes in a 64bit VM. Each array has a 2 word header, thus the formula is: words = (internal table length + 2) + sum (for all chains (chain length + 2))
      Returns:
      the number of JVM words that is used by this map.
    • rehash

      protected void rehash(int newCapacity)
    • get

      public V get(Object key)
      Specified by:
      get in interface Map<K,V>
      Specified by:
      get in interface MapIterable<K,V>
      See Also:
    • getFromChain

      private V getFromChain(Object[] chain, K key)
    • containsKey

      public boolean containsKey(Object key)
      Specified by:
      containsKey in interface Map<K,V>
      Specified by:
      containsKey in interface MapIterable<K,V>
      See Also:
    • chainContainsKey

      private boolean chainContainsKey(Object[] chain, K key)
    • containsValue

      public boolean containsValue(Object value)
      Specified by:
      containsValue in interface Map<K,V>
      Specified by:
      containsValue in interface MapIterable<K,V>
      See Also:
    • chainedContainsValue

      private boolean chainedContainsValue(Object[] chain, V value)
    • forEachKeyValue

      public void forEachKeyValue(Procedure2<? super K,? super V> procedure)
      Description copied from interface: MapIterable
      Calls the procedure with each key-value pair of the map.
           final Collection<String> collection = new ArrayList<String>();
           MutableMap<Integer, String> map = this.newMapWithKeysValues(1, "One", 2, "Two", 3, "Three");
           map.forEachKeyValue((Integer key, String value) -> collection.add(String.valueOf(key) + value));
           Verify.assertContainsAll(collection, "1One", "2Two", "3Three");
       
      Specified by:
      forEachKeyValue in interface MapIterable<K,V>
    • getFirst

      public V getFirst()
      Description copied from interface: RichIterable
      Returns the first element of an iterable. In the case of a List it is the element at the first index. In the case of any other Collection, it is the first element that would be returned during an iteration. If the iterable is empty, null is returned. If null is a valid element of the container, then a developer would need to check to see if the iterable is empty to validate that a null result was not due to the container being empty.

      The order of Sets are not guaranteed (except for TreeSets and other Ordered Set implementations), so if you use this method, the first element could be any element from the Set.

      Specified by:
      getFirst in interface RichIterable<K>
      Overrides:
      getFirst in class AbstractMapIterable<K,V>
    • collectKeysAndValues

      public <E> MutableMap<K,V> collectKeysAndValues(Iterable<E> iterable, Function<? super E,? extends K> keyFunction, Function<? super E,? extends V> valueFunction)
      Description copied from interface: MutableMap
      Adds all the entries derived from iterable to this. The key and value for each entry is determined by applying the keyFunction and valueFunction to each item in collection. Any entry in map that has the same key as an entry in this will have its value replaced by that in map.
      Specified by:
      collectKeysAndValues in interface MutableMap<K,V>
    • removeKey

      public V removeKey(K key)
      Description copied from interface: MutableMapIterable
      Remove an entry from the map at the specified key.
      Specified by:
      removeKey in interface MutableMapIterable<K,V>
      Returns:
      The value removed from entry at key, or null if not found.
      See Also:
    • chainedForEachEntry

      private void chainedForEachEntry(Object[] chain, Procedure2<? super K,? super V> procedure)
    • getBatchCount

      public int getBatchCount(int batchSize)
      Specified by:
      getBatchCount in interface BatchIterable<K>
    • batchForEach

      public void batchForEach(Procedure<? super V> procedure, int sectionIndex, int sectionCount)
      Specified by:
      batchForEach in interface BatchIterable<K>
    • forEachKey

      public void forEachKey(Procedure<? super K> procedure)
      Description copied from interface: MapIterable
      Calls the procedure with each key of the map.
           final Collection<Integer> result = new ArrayList<Integer>();
           MutableMap<Integer, String> map = this.newMapWithKeysValues(1, "1", 2, "2", 3, "3");
           map.forEachKey(new CollectionAddProcedure<Integer>(result));
           Verify.assertContainsAll(result, 1, 2, 3);
       
      Specified by:
      forEachKey in interface MapIterable<K,V>
      Overrides:
      forEachKey in class AbstractMapIterable<K,V>
    • chainedForEachKey

      private void chainedForEachKey(Object[] chain, Procedure<? super K> procedure)
    • forEachValue

      public void forEachValue(Procedure<? super V> procedure)
      Description copied from interface: MapIterable
      Calls the procedure with each value of the map.
           Set<String> result = UnifiedSet.newSet();
           MutableMap<Integer, String> map = this.newMapWithKeysValues(1, "One", 2, "Two", 3, "Three", 4, "Four");
           map.forEachValue(new CollectionAddProcedure<String>(result));
           Verify.assertSetsEqual(UnifiedSet.newSetWith("One", "Two", "Three", "Four"), result);
       
      Specified by:
      forEachValue in interface MapIterable<K,V>
      Overrides:
      forEachValue in class AbstractMapIterable<K,V>
    • chainedForEachValue

      private void chainedForEachValue(Object[] chain, Procedure<? super V> procedure)
    • isEmpty

      public boolean isEmpty()
      Description copied from interface: RichIterable
      Returns true if this iterable has zero items.
      Specified by:
      isEmpty in interface Map<K,V>
      Specified by:
      isEmpty in interface RichIterable<K>
      Overrides:
      isEmpty in class AbstractRichIterable<V>
    • putAll

      public void putAll(Map<? extends K,? extends V> map)
      Specified by:
      putAll in interface Map<K,V>
    • getEntrySetFrom

      private Set<? extends Map.Entry<? extends K,? extends V>> getEntrySetFrom(Map<? extends K,? extends V> map)
    • copyMap

      protected void copyMap(UnifiedMapWithHashingStrategy<K,V> unifiedMap)
    • copyChain

      private void copyChain(Object[] chain)
    • remove

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

      private V removeFromChain(Object[] chain, K key, int index)
    • overwriteWithLastElementFromChain

      private void overwriteWithLastElementFromChain(Object[] chain, int index, int i)
    • size

      public int size()
      Description copied from interface: RichIterable
      Returns the number of items in this iterable.
      Specified by:
      size in interface BatchIterable<K>
      Specified by:
      size in interface Map<K,V>
      Specified by:
      size in interface RichIterable<K>
    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Specified by:
      entrySet in interface Map<K,V>
    • keySet

      public Set<K> keySet()
      Specified by:
      keySet in interface Map<K,V>
    • values

      public Collection<V> values()
      Specified by:
      values in interface Map<K,V>
    • equals

      public boolean equals(Object object)
      Description copied from interface: MapIterable
      Follows the same general contract as Map.equals(Object).
      Specified by:
      equals in interface Map<K,V>
      Specified by:
      equals in interface MapIterable<K,V>
      Overrides:
      equals in class Object
    • chainedEquals

      private boolean chainedEquals(Object[] chain, Map<?,?> other)
    • hashCode

      public int hashCode()
      Description copied from interface: MapIterable
      Follows the same general contract as Map.hashCode().
      Specified by:
      hashCode in interface Map<K,V>
      Specified by:
      hashCode in interface MapIterable<K,V>
      Overrides:
      hashCode in class Object
    • chainedHashCode

      private int chainedHashCode(Object[] chain)
    • toString

      public String toString()
      Description copied from class: AbstractRichIterable
      Returns a string with the elements of the iterable separated by commas with spaces and enclosed in square brackets.
       Assert.assertEquals("[]", Lists.mutable.empty().toString());
       Assert.assertEquals("[1]", Lists.mutable.with(1).toString());
       Assert.assertEquals("[1, 2, 3]", Lists.mutable.with(1, 2, 3).toString());
       
      Specified by:
      toString in interface MapIterable<K,V>
      Specified by:
      toString in interface RichIterable<K>
      Overrides:
      toString in class AbstractRichIterable<V>
      Returns:
      a string representation of this collection.
      See Also:
    • trimToSize

      public boolean trimToSize()
    • putForTrim

      private void putForTrim(K key, V value, int oldIndex, int mask)
    • chainedPutForTrim

      private void chainedPutForTrim(K key, int index, V value)
    • readExternal

      public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
      Specified by:
      readExternal in interface Externalizable
      Throws:
      IOException
      ClassNotFoundException
    • writeExternal

      public void writeExternal(ObjectOutput out) throws IOException
      Specified by:
      writeExternal in interface Externalizable
      Throws:
      IOException
    • writeExternalChain

      private void writeExternalChain(ObjectOutput out, Object[] chain) throws IOException
      Throws:
      IOException
    • forEachWithIndex

      public void forEachWithIndex(ObjectIntProcedure<? super V> objectIntProcedure)
      Description copied from interface: InternalIterable
      Iterates over the iterable passing each element and the current relative int index to the specified instance of ObjectIntProcedure.

      Example using a Java 8 lambda:

       people.forEachWithIndex((Person person, int index) -> LOGGER.info("Index: " + index + " person: " + person.getName()));
       

      Example using an anonymous inner class:

       people.forEachWithIndex(new ObjectIntProcedure<Person>()
       {
           public void value(Person person, int index)
           {
               LOGGER.info("Index: " + index + " person: " + person.getName());
           }
       });
       
      Specified by:
      forEachWithIndex in interface InternalIterable<K>
      Overrides:
      forEachWithIndex in class AbstractMapIterable<K,V>
    • chainedForEachValueWithIndex

      private int chainedForEachValueWithIndex(Object[] chain, ObjectIntProcedure<? super V> objectIntProcedure, int index)
    • forEachWith

      public <P> void forEachWith(Procedure2<? super V,? super P> procedure, P parameter)
      Description copied from interface: InternalIterable
      The procedure2 is evaluated for each element in the iterable with the specified parameter provided as the second argument.

      Example using a Java 8 lambda:

       people.forEachWith((Person person, Person other) ->
           {
               if (person.isRelatedTo(other))
               {
                    LOGGER.info(person.getName());
               }
           }, fred);
       

      Example using an anonymous inner class:

       people.forEachWith(new Procedure2<Person, Person>()
       {
           public void value(Person person, Person other)
           {
               if (person.isRelatedTo(other))
               {
                    LOGGER.info(person.getName());
               }
           }
       }, fred);
       
      Specified by:
      forEachWith in interface InternalIterable<K>
      Overrides:
      forEachWith in class AbstractMapIterable<K,V>
    • chainedForEachValueWith

      private <P> void chainedForEachValueWith(Object[] chain, Procedure2<? super V,? super P> procedure, P parameter)
    • collectValues

      public <R> MutableMap<K,R> collectValues(Function2<? super K,? super V,? extends R> function)
      Description copied from interface: MapIterable
      For each key and value of the map the function is evaluated. The results of these evaluations are returned in a new map. The map returned will use the values projected from the function rather than the original values.
       MapIterable<City, String> collected =
           peopleByCity.collectValues((City city, Person person) -> person.getFirstName() + " " + person.getLastName());
       
      Specified by:
      collectValues in interface MapIterable<K,V>
      Specified by:
      collectValues in interface MutableMap<K,V>
      Specified by:
      collectValues in interface MutableMapIterable<K,V>
      Specified by:
      collectValues in interface UnsortedMapIterable<K,V>
      Overrides:
      collectValues in class AbstractMutableMap<K,V>
    • nullSafeEquals

      private static boolean nullSafeEquals(Object value, Object other)
    • nonSentinel

      private K nonSentinel(Object key)
    • toSentinelIfNull

      private static Object toSentinelIfNull(Object key)
    • nonNullTableObjectEquals

      private boolean nonNullTableObjectEquals(Object cur, K key)
    • toImmutable

      public ImmutableMap<K,V> toImmutable()
      Description copied from interface: MutableMapIterable
      Returns an immutable copy of this map. If the map is immutable, it returns itself.
      Specified by:
      toImmutable in interface MapIterable<K,V>
      Specified by:
      toImmutable in interface MutableMapIterable<K,V>
      Specified by:
      toImmutable in interface UnsortedMapIterable<K,V>
      Overrides:
      toImmutable in class AbstractMutableMap<K,V>