Class CompactLinkedHashMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>

    @GwtIncompatible
    class CompactLinkedHashMap<K,​V>
    extends CompactHashMap<K,​V>
    CompactLinkedHashMap is an implementation of a Map with insertion or LRU iteration order, maintained with a doubly linked list through the entries. All optional operations (put and remove) are supported. Null keys and values are supported.

    containsKey(k), put(k, v) and remove(k) are all (expected and amortized) constant time operations. Expected in the hashtable sense (depends on the hash function doing a good job of distributing the elements to the buckets to a distribution not far from uniform), and amortized since some operations can trigger a hash table resize.

    As compared with LinkedHashMap, this structure places significantly reduced load on the garbage collector by only using a constant number of internal objects.

    This class should not be assumed to be universally superior to java.util.LinkedHashMap. Generally speaking, this class reduces object allocation and memory consumption at the price of moderately increased constant factors of CPU. Only use this class when there is a specific reason to prioritize memory over CPU.

    • 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>
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private boolean accessOrder  
      private static int ENDPOINT  
      private int firstEntry
      Pointer to the first node in the linked list, or ENDPOINT if there are no entries.
      private int lastEntry
      Pointer to the last node in the linked list, or ENDPOINT if there are no entries.
      (package private) long[] links
      Contains the link pointers corresponding with the entries, in the range of [0, size()).
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void accessEntry​(int index)
      Mark an access of the specified entry.
      (package private) int adjustAfterRemove​(int indexBeforeRemove, int indexRemoved)
      Updates the index an iterator is pointing to after a call to remove: returns the index of the entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the index that *was* the next entry that would be looked at.
      (package private) void allocArrays()
      Handle lazy allocation of arrays.
      void clear()  
      static <K,​V>
      CompactLinkedHashMap<K,​V>
      create()
      Creates an empty CompactLinkedHashMap instance.
      (package private) java.util.Set<java.util.Map.Entry<K,​V>> createEntrySet()  
      (package private) java.util.Set<K> createKeySet()  
      (package private) java.util.Collection<V> createValues()  
      static <K,​V>
      CompactLinkedHashMap<K,​V>
      createWithExpectedSize​(int expectedSize)
      Creates a CompactLinkedHashMap instance, with a high enough "initial capacity" that it should hold expectedSize elements without rebuilding internal data structures.
      (package private) int firstEntryIndex()  
      private int getPredecessor​(int entry)  
      (package private) int getSuccessor​(int entry)  
      (package private) void init​(int expectedSize)
      Pseudoconstructor for serialization support.
      (package private) void insertEntry​(int entryIndex, K key, V value, int hash)
      Creates a fresh entry with the specified object at the specified position in the entry arrays.
      (package private) void moveLastEntry​(int dstIndex)
      Moves the last entry in the entry array into dstIndex, and nulls out its old position.
      (package private) void resizeEntries​(int newCapacity)
      Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
      private void setPredecessor​(int entry, int pred)  
      private void setSucceeds​(int pred, int succ)  
      private void setSuccessor​(int entry, int succ)  
      • Methods inherited from class java.util.AbstractMap

        clone, equals, hashCode, putAll, toString
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, getOrDefault, merge, putIfAbsent, remove, replace, replace
    • Field Detail

      • links

        transient long[] links
        Contains the link pointers corresponding with the entries, in the range of [0, size()). The high 32 bits of each long is the "prev" pointer, whereas the low 32 bits is the "succ" pointer (pointing to the next entry in the linked list). The pointers in [size(), entries.length) are all "null" (UNSET).

        A node with "prev" pointer equal to ENDPOINT is the first node in the linked list, and a node with "next" pointer equal to ENDPOINT is the last node.

      • firstEntry

        private transient int firstEntry
        Pointer to the first node in the linked list, or ENDPOINT if there are no entries.
      • lastEntry

        private transient int lastEntry
        Pointer to the last node in the linked list, or ENDPOINT if there are no entries.
      • accessOrder

        private final boolean accessOrder
    • Constructor Detail

      • CompactLinkedHashMap

        CompactLinkedHashMap()
      • CompactLinkedHashMap

        CompactLinkedHashMap​(int expectedSize)
      • CompactLinkedHashMap

        CompactLinkedHashMap​(int expectedSize,
                             boolean accessOrder)
    • Method Detail

      • create

        public static <K,​V> CompactLinkedHashMap<K,​V> create()
        Creates an empty CompactLinkedHashMap instance.
      • createWithExpectedSize

        public static <K,​V> CompactLinkedHashMap<K,​V> createWithExpectedSize​(int expectedSize)
        Creates a CompactLinkedHashMap instance, with a high enough "initial capacity" that it should hold expectedSize elements without rebuilding internal data structures.
        Parameters:
        expectedSize - the number of elements you expect to add to the returned set
        Returns:
        a new, empty CompactLinkedHashMap with enough capacity to hold expectedSize elements without resizing
        Throws:
        java.lang.IllegalArgumentException - if expectedSize is negative
      • init

        void init​(int expectedSize)
        Description copied from class: CompactHashMap
        Pseudoconstructor for serialization support.
        Overrides:
        init in class CompactHashMap<K,​V>
      • getPredecessor

        private int getPredecessor​(int entry)
      • setSuccessor

        private void setSuccessor​(int entry,
                                  int succ)
      • setPredecessor

        private void setPredecessor​(int entry,
                                    int pred)
      • setSucceeds

        private void setSucceeds​(int pred,
                                 int succ)
      • insertEntry

        void insertEntry​(int entryIndex,
                         K key,
                         V value,
                         int hash)
        Description copied from class: CompactHashMap
        Creates a fresh entry with the specified object at the specified position in the entry arrays.
        Overrides:
        insertEntry in class CompactHashMap<K,​V>
      • accessEntry

        void accessEntry​(int index)
        Description copied from class: CompactHashMap
        Mark an access of the specified entry. Used only in CompactLinkedHashMap for LRU ordering.
        Overrides:
        accessEntry in class CompactHashMap<K,​V>
      • moveLastEntry

        void moveLastEntry​(int dstIndex)
        Description copied from class: CompactHashMap
        Moves the last entry in the entry array into dstIndex, and nulls out its old position.
        Overrides:
        moveLastEntry in class CompactHashMap<K,​V>
      • resizeEntries

        void resizeEntries​(int newCapacity)
        Description copied from class: CompactHashMap
        Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
        Overrides:
        resizeEntries in class CompactHashMap<K,​V>
      • adjustAfterRemove

        int adjustAfterRemove​(int indexBeforeRemove,
                              int indexRemoved)
        Description copied from class: CompactHashMap
        Updates the index an iterator is pointing to after a call to remove: returns the index of the entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the index that *was* the next entry that would be looked at.
        Overrides:
        adjustAfterRemove in class CompactHashMap<K,​V>
      • clear

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