Class CompactLinkedHashMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
com.google.common.collect.CompactHashMap<K,V>
com.google.common.collect.CompactLinkedHashMap<K,V>
All Implemented Interfaces:
Serializable, 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 Details

    • ENDPOINT

      private static final int ENDPOINT
      See Also:
    • 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 Details

    • CompactLinkedHashMap

      CompactLinkedHashMap()
    • CompactLinkedHashMap

      CompactLinkedHashMap(int expectedSize)
    • CompactLinkedHashMap

      CompactLinkedHashMap(int expectedSize, boolean accessOrder)
  • Method Details

    • 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:
      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>
    • allocArrays

      int allocArrays()
      Description copied from class: CompactHashMap
      Handle lazy allocation of arrays.
      Overrides:
      allocArrays in class CompactHashMap<K,V>
    • createHashFloodingResistantDelegate

      Map<K,V> createHashFloodingResistantDelegate(int tableSize)
      Overrides:
      createHashFloodingResistantDelegate in class CompactHashMap<K,V>
    • convertToHashFloodingResistantImplementation

      Map<K,V> convertToHashFloodingResistantImplementation()
      Overrides:
      convertToHashFloodingResistantImplementation in class CompactHashMap<K,V>
    • getPredecessor

      private int getPredecessor(int entry)
    • getSuccessor

      int getSuccessor(int entry)
      Overrides:
      getSuccessor in class CompactHashMap<K,V>
    • 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>
    • firstEntryIndex

      int firstEntryIndex()
      Overrides:
      firstEntryIndex 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>
    • createEntrySet

      Set<Map.Entry<K,V>> createEntrySet()
      Overrides:
      createEntrySet in class CompactHashMap<K,V>
    • createKeySet

      Set<K> createKeySet()
      Overrides:
      createKeySet in class CompactHashMap<K,V>
    • createValues

      Collection<V> createValues()
      Overrides:
      createValues in class CompactHashMap<K,V>
    • clear

      public void clear()
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class CompactHashMap<K,V>
    • requireLinks

      private long[] requireLinks()
    • link

      private long link(int i)
    • setLink

      private void setLink(int i, long value)