Class OpenHashMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.util.Map<K,​V>, java.util.SortedMap<K,​V>
    Direct Known Subclasses:
    OpenHashMapList, OpenHashMapSet

    public class OpenHashMap<K,​V>
    extends java.lang.Object
    implements java.io.Serializable, java.lang.Cloneable, java.util.SortedMap<K,​V>
    Based on fastutil Object2ObjectLinkedOpenHashMap
    See Also:
    Serialized Form
    • Field Detail

      • key

        protected transient java.lang.Object[] key
      • value

        protected transient java.lang.Object[] value
      • mask

        protected transient int mask
      • containsNullKey

        protected transient boolean containsNullKey
      • first

        protected transient int first
      • last

        protected transient int last
      • link

        protected transient long[] link
      • n

        protected transient int n
      • maxFill

        protected transient int maxFill
      • size

        protected int size
      • f

        protected final float f
      • defRetValue

        protected V defRetValue
      • fast

        protected transient java.lang.Iterable<java.util.Map.Entry<K,​V>> fast
      • entries

        protected transient java.util.SortedSet<java.util.Map.Entry<K,​V>> entries
      • keys

        protected transient java.util.SortedSet<K> keys
      • values

        protected transient java.util.Collection<V> values
    • Constructor Detail

      • OpenHashMap

        public OpenHashMap​(int expected,
                           float f)
      • OpenHashMap

        public OpenHashMap​(int expected)
      • OpenHashMap

        public OpenHashMap()
      • OpenHashMap

        public OpenHashMap​(java.util.Map<? extends K,​? extends V> m,
                           float f)
      • OpenHashMap

        public OpenHashMap​(java.util.Map<? extends K,​? extends V> m)
      • OpenHashMap

        public OpenHashMap​(K[] k,
                           V[] v,
                           float f)
      • OpenHashMap

        public OpenHashMap​(K[] k,
                           V[] v)
    • Method Detail

      • defaultReturnValue

        public void defaultReturnValue​(V rv)
      • defaultReturnValue

        public V defaultReturnValue()
      • equals

        public boolean equals​(java.lang.Object o)
        Specified by:
        equals in interface java.util.Map<K,​V>
        Overrides:
        equals in class java.lang.Object
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • realSize

        private int realSize()
      • ensureCapacity

        private void ensureCapacity​(int capacity)
      • tryCapacity

        private void tryCapacity​(long capacity)
      • removeEntry

        private V removeEntry​(int pos)
      • removeNullEntry

        private V removeNullEntry()
      • putAll

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

        private int insert​(K k,
                           V v)
      • put

        public V put​(K k,
                     V v)
        Specified by:
        put in interface java.util.Map<K,​V>
      • getOrCompute

        public V getOrCompute​(K k)
      • compute

        protected V compute​(K k)
      • shiftKeys

        protected final void shiftKeys​(int pos)
      • remove

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

        private V setValue​(int pos,
                           V v)
      • removeFirst

        public V removeFirst()
      • removeLast

        public V removeLast()
      • moveIndexToFirst

        private void moveIndexToFirst​(int i)
      • moveIndexToLast

        private void moveIndexToLast​(int i)
      • getAndMoveToFirst

        public V getAndMoveToFirst​(K k)
      • getAndMoveToLast

        public V getAndMoveToLast​(K k)
      • putAndMoveToFirst

        public V putAndMoveToFirst​(K k,
                                   V v)
      • putAndMoveToLast

        public V putAndMoveToLast​(K k,
                                  V v)
      • get

        public V get​(java.lang.Object k)
        Specified by:
        get in interface java.util.Map<K,​V>
      • containsKey

        public boolean containsKey​(java.lang.Object k)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
      • containsValue

        public boolean containsValue​(java.lang.Object v)
        Specified by:
        containsValue in interface java.util.Map<K,​V>
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<K,​V>
      • fixPointers

        protected void fixPointers​(int i)
      • fixPointers

        protected void fixPointers​(int s,
                                   int d)
      • firstKey

        public K firstKey()
        Specified by:
        firstKey in interface java.util.SortedMap<K,​V>
      • lastKey

        public K lastKey()
        Specified by:
        lastKey in interface java.util.SortedMap<K,​V>
      • comparator

        public java.util.Comparator<? super K> comparator()
        Specified by:
        comparator in interface java.util.SortedMap<K,​V>
      • tailMap

        public java.util.SortedMap<K,​V> tailMap​(K from)
        Specified by:
        tailMap in interface java.util.SortedMap<K,​V>
      • headMap

        public java.util.SortedMap<K,​V> headMap​(K to)
        Specified by:
        headMap in interface java.util.SortedMap<K,​V>
      • subMap

        public java.util.SortedMap<K,​V> subMap​(K from,
                                                     K to)
        Specified by:
        subMap in interface java.util.SortedMap<K,​V>
      • fast

        public java.lang.Iterable<java.util.Map.Entry<K,​V>> fast()
      • entrySet

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

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

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

        public boolean trim()
        Rehashes the map, making the table as small as possible.

        This method rehashes the table to the smallest size satisfying the load factor. It can be used when the set will not be changed anymore, so to optimize access speed and size.

        If the table size is already the minimum possible, this method does nothing.

        Returns:
        true if there was enough memory to trim the map.
        See Also:
        trim(int)
      • trim

        public boolean trim​(int n)
        Rehashes this map if the table is too large.

        Let N be the smallest table size that can hold max(n,size()) entries, still satisfying the load factor. If the current table size is smaller than or equal to N, this method does nothing. Otherwise, it rehashes this map in a table of size N.

        This method is useful when reusing maps. Clearing a map leaves the table size untouched. If you are reusing a map many times, you can call this method with a typical size to avoid keeping around a very large table just because of a few large transient maps.

        Parameters:
        n - the threshold for the trimming.
        Returns:
        true if there was enough memory to trim the map.
        See Also:
        trim()
      • rehash

        protected void rehash​(int newN)
        Rehashes the map.

        This method implements the basic rehashing strategy, and may be overriden by subclasses implementing different rehashing strategies (e.g., disk-based rehashing). However, you should not override this method unless you understand the internal workings of this class.

        Parameters:
        newN - the new size
      • clone

        public OpenHashMap<K,​V> clone()
        Overrides:
        clone in class java.lang.Object
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Map<K,​V>
        Overrides:
        hashCode in class java.lang.Object
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • readObject

        private void readObject​(java.io.ObjectInputStream s)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException
      • checkTable

        private void checkTable()
      • arraySize

        private static int arraySize​(int expected,
                                     float f)
      • maxFill

        private static int maxFill​(int n,
                                   float f)
      • nextPowerOfTwo

        private static int nextPowerOfTwo​(int x)
      • nextPowerOfTwo

        private static long nextPowerOfTwo​(long x)
      • mix

        private static int mix​(int x)
      • unwrap

        private static <K> int unwrap​(java.util.Iterator<? extends K> i,
                                      K[] array,
                                      int offset,
                                      int max)
      • unwrap

        private static <K> int unwrap​(java.util.Iterator<? extends K> i,
                                      K[] array)