Class CompactLinkedHashSet<E>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>

    @GwtIncompatible
    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.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (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.
      void clear()  
      static <E> CompactLinkedHashSet<E> create()
      Creates an empty CompactLinkedHashSet instance.
      static <E> CompactLinkedHashSet<E> create​(E... elements)
      Creates a CompactLinkedHashSet instance containing the given elements in unspecified order.
      static <E> CompactLinkedHashSet<E> create​(java.util.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.
      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.
      (package private) int firstEntryIndex()  
      void forEach​(java.util.function.Consumer<? super E> action)  
      (package private) int getSuccessor​(int entryIndex)  
      (package private) void init​(int expectedSize, float loadFactor)
      Pseudoconstructor for serialization support.
      (package private) void insertEntry​(int entryIndex, E object, int hash)
      Creates a fresh entry with the specified object at the specified position in the entry arrays.
      (package private) void moveEntry​(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.
      java.util.Spliterator<E> spliterator()  
      private void succeeds​(int pred, int succ)  
      java.lang.Object[] toArray()  
      <T> T[] toArray​(T[] a)  
      • Methods inherited from class java.util.AbstractSet

        equals, hashCode, removeAll
      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, retainAll, toString
      • Methods inherited from class java.lang.Object

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

        parallelStream, removeIf, stream, toArray
      • Methods inherited from interface java.util.Set

        addAll, containsAll, retainAll
    • Field Detail

      • predecessor

        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

        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
      • lastEntry

        private transient int lastEntry
    • Constructor Detail

      • CompactLinkedHashSet

        CompactLinkedHashSet()
      • CompactLinkedHashSet

        CompactLinkedHashSet​(int expectedSize)
    • Method Detail

      • create

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

        public static <E> CompactLinkedHashSet<E> create​(java.util.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

        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:
        java.lang.IllegalArgumentException - if expectedSize is negative
      • init

        void init​(int expectedSize,
                  float loadFactor)
        Description copied from class: CompactHashSet
        Pseudoconstructor for serialization support.
        Overrides:
        init in class CompactHashSet<E>
      • succeeds

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

        void insertEntry​(int entryIndex,
                         E object,
                         int hash)
        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>
      • moveEntry

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

        public void clear()
        Specified by:
        clear in interface java.util.Collection<E>
        Specified by:
        clear in interface java.util.Set<E>
        Overrides:
        clear 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>
      • toArray

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

        public <T> T[] toArray​(T[] a)
        Specified by:
        toArray in interface java.util.Collection<E>
        Specified by:
        toArray in interface java.util.Set<E>
        Overrides:
        toArray 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>
      • spliterator

        public java.util.Spliterator<E> spliterator()
        Specified by:
        spliterator in interface java.util.Collection<E>
        Specified by:
        spliterator in interface java.lang.Iterable<E>
        Specified by:
        spliterator in interface java.util.Set<E>
        Overrides:
        spliterator in class CompactHashSet<E>
      • forEach

        public void forEach​(java.util.function.Consumer<? super E> action)
        Specified by:
        forEach in interface java.lang.Iterable<E>
        Overrides:
        forEach in class CompactHashSet<E>