Package com.google.common.collect

Class CompactLinkedHashMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>
    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.

    • 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,
                 int mask)
        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,
                   int mask)
        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>