Package com.google.common.collect

Class CompactLinkedHashSet<E>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.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 Summary

      Fields 
      Modifier and Type Field Description
      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.
      private int[] predecessor
      Pointer to the predecessor of an entry in insertion order.
      private int[] successor
      Pointer to the successor of an entry in insertion order.

    • 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.
      (package private) int allocArrays()
      Handle lazy allocation of arrays.
      void clear()  
      (package private) java.util.Set<E> convertToHashFloodingResistantImplementation()  
      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()  
      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, E object, int hash, int mask)
      Creates a fresh entry with the specified object at the specified position in the entry arrays.
      (package private) void moveLastEntry​(int dstIndex, int mask)
      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)  
      java.util.Spliterator<E> spliterator()  
      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
        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 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

        @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:
        java.lang.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>

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

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

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

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