Class CompactLinkedHashSet<E>

All Implemented Interfaces:
Serializable, Iterable<E>, Collection<E>, Set<E>

class CompactLinkedHashSet<E> extends CompactHashSet<E>
CompactLinkedHashSet is an implementation of a Set, which a predictable iteration order that matches the insertion order. All optional operations (adding and removing) are supported. All elements, including null, are permitted.

contains(x), add(x) and remove(x), 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.

This implementation consumes significantly less memory than java.util.LinkedHashSet or even java.util.HashSet, and places considerably less load on the garbage collector. Like java.util.LinkedHashSet, it offers insertion-order iteration, with identical behavior.

This class should not be assumed to be universally superior to java.util.LinkedHashSet. 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:
    • predecessor

      @CheckForNull private transient int[] predecessor
      Pointer to the predecessor of an entry in insertion order. ENDPOINT indicates a node is the first node in insertion order; all values at indices ≥ CompactHashSet.size() are UNSET.
    • successor

      @CheckForNull private transient int[] successor
      Pointer to the successor of an entry in insertion order. ENDPOINT indicates a node is the last node in insertion order; all values at indices ≥ CompactHashSet.size() are UNSET.
    • 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.
  • Constructor Details

    • CompactLinkedHashSet

      CompactLinkedHashSet()
    • CompactLinkedHashSet

      CompactLinkedHashSet(int expectedSize)
  • Method Details

    • create

      public static <E> CompactLinkedHashSet<E> create()
      Creates an empty CompactLinkedHashSet instance.
    • create

      public static <E> CompactLinkedHashSet<E> create(Collection<? extends E> collection)
      Creates a mutable CompactLinkedHashSet instance containing the elements of the given collection in the order returned by the collection's iterator.
      Parameters:
      collection - the elements that the set should contain
      Returns:
      a new CompactLinkedHashSet containing those elements (minus duplicates)
    • create

      @SafeVarargs public static <E> CompactLinkedHashSet<E> create(E... elements)
      Creates a CompactLinkedHashSet instance containing the given elements in unspecified order.
      Parameters:
      elements - the elements that the set should contain
      Returns:
      a new CompactLinkedHashSet containing those elements (minus duplicates)
    • createWithExpectedSize

      public static <E> CompactLinkedHashSet<E> createWithExpectedSize(int expectedSize)
      Creates a CompactLinkedHashSet 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 CompactLinkedHashSet with enough capacity to hold expectedSize elements without resizing
      Throws:
      IllegalArgumentException - if expectedSize is negative
    • init

      void init(int expectedSize)
      Description copied from class: CompactHashSet
      Pseudoconstructor for serialization support.
      Overrides:
      init in class CompactHashSet<E>
    • allocArrays

      int allocArrays()
      Description copied from class: CompactHashSet
      Handle lazy allocation of arrays.
      Overrides:
      allocArrays in class CompactHashSet<E>
    • convertToHashFloodingResistantImplementation

      Set<E> convertToHashFloodingResistantImplementation()
      Overrides:
      convertToHashFloodingResistantImplementation in class CompactHashSet<E>
    • getPredecessor

      private int getPredecessor(int entry)
    • getSuccessor

      int getSuccessor(int entry)
      Overrides:
      getSuccessor in class CompactHashSet<E>
    • 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, E object, int hash, int mask)
      Description copied from class: CompactHashSet
      Creates a fresh entry with the specified object at the specified position in the entry arrays.
      Overrides:
      insertEntry in class CompactHashSet<E>
    • moveLastEntry

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

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

      int firstEntryIndex()
      Overrides:
      firstEntryIndex in class CompactHashSet<E>
    • adjustAfterRemove

      int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
      Description copied from class: CompactHashSet
      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 CompactHashSet<E>
    • toArray

      public Object[] toArray()
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface Set<E>
      Overrides:
      toArray in class CompactHashSet<E>
    • toArray

      public <T> T[] toArray(T[] a)
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface Set<E>
      Overrides:
      toArray in class CompactHashSet<E>
    • spliterator

      public Spliterator<E> spliterator()
      Specified by:
      spliterator in interface Collection<E>
      Specified by:
      spliterator in interface Iterable<E>
      Specified by:
      spliterator in interface Set<E>
      Overrides:
      spliterator in class CompactHashSet<E>
    • clear

      public void clear()
      Specified by:
      clear in interface Collection<E>
      Specified by:
      clear in interface Set<E>
      Overrides:
      clear in class CompactHashSet<E>
    • requirePredecessors

      private int[] requirePredecessors()
    • requireSuccessors

      private int[] requireSuccessors()