Class UnifiedMapWithHashingStrategy<K,​V>

  • All Implemented Interfaces:
    java.io.Externalizable, java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<V>, java.util.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 java.io.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:
    Serialized Form
    • Field Detail

      • NULL_KEY

        protected static final java.lang.Object NULL_KEY
      • CHAINED_KEY

        protected static final java.lang.Object CHAINED_KEY
      • DEFAULT_INITIAL_CAPACITY

        protected static final int DEFAULT_INITIAL_CAPACITY
        See Also:
        Constant Field Values
      • table

        protected transient java.lang.Object[] table
      • occupied

        protected transient int occupied
      • loadFactor

        protected float loadFactor
      • maxSize

        protected int maxSize
    • Constructor Detail

      • 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,
                                             java.util.Map<? extends K,​? extends V> map)
      • UnifiedMapWithHashingStrategy

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

      • 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)
      • 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 java.util.Map<K,​V>
      • put

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

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

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

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

        private V chainedGetIfAbsentPut​(K key,
                                        int index,
                                        Function0<? extends V> function)
      • 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​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Specified by:
        get in interface MapIterable<K,​V>
        See Also:
        Map.get(Object)
      • getFromChain

        private V getFromChain​(java.lang.Object[] chain,
                               K key)
      • containsKey

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

        private boolean chainContainsKey​(java.lang.Object[] chain,
                                         K key)
      • containsValue

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

        private boolean chainedContainsValue​(java.lang.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​(java.lang.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:
        Map.remove(Object)
      • chainedForEachEntry

        private void chainedForEachEntry​(java.lang.Object[] chain,
                                         Procedure2<? super K,​? super V> procedure)
      • 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​(java.lang.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​(java.lang.Object[] chain,
                                         Procedure<? super V> procedure)
      • putAll

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

        private java.util.Set<? extends java.util.Map.Entry<? extends K,​? extends V>> getEntrySetFrom​(java.util.Map<? extends K,​? extends V> map)
      • copyChain

        private void copyChain​(java.lang.Object[] chain)
      • remove

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

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

        private void overwriteWithLastElementFromChain​(java.lang.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 java.util.Map<K,​V>
        Specified by:
        size in interface RichIterable<K>
      • entrySet

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

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

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

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

        private boolean chainedEquals​(java.lang.Object[] chain,
                                      java.util.Map<?,​?> other)
      • hashCode

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

        private int chainedHashCode​(java.lang.Object[] chain)
      • toString

        public java.lang.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:
        AbstractCollection.toString()
      • 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​(java.io.ObjectInput in)
                          throws java.io.IOException,
                                 java.lang.ClassNotFoundException
        Specified by:
        readExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException
      • writeExternal

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

        private void writeExternalChain​(java.io.ObjectOutput out,
                                        java.lang.Object[] chain)
                                 throws java.io.IOException
        Throws:
        java.io.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​(java.lang.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​(java.lang.Object[] chain,
                                                 Procedure2<? super V,​? super P> procedure,
                                                 P parameter)
      • nullSafeEquals

        private static boolean nullSafeEquals​(java.lang.Object value,
                                              java.lang.Object other)
      • nonSentinel

        private K nonSentinel​(java.lang.Object key)
      • toSentinelIfNull

        private static java.lang.Object toSentinelIfNull​(java.lang.Object key)
      • nonNullTableObjectEquals

        private boolean nonNullTableObjectEquals​(java.lang.Object cur,
                                                 K key)