Package com.google.common.collect

Class CompactHashSet<E>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>
    Direct Known Subclasses:
    CompactLinkedHashSet
    @GwtIncompatible
class CompactHashSet<E>
extends java.util.AbstractSet<E>
implements java.io.Serializable
    CompactHashSet is an implementation of a Set. All optional operations (adding and removing) are supported. The elements can be any objects.

    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.

    Unlike java.util.HashSet, iteration is only proportional to the actual size(), which is optimal, and not the size of the internal hashtable, which could be much larger than size(). Furthermore, this structure only depends on a fixed number of arrays; add(x) operations do not create objects for the garbage collector to deal with, and for every element added, the garbage collector will have to traverse 1.5 references on average, in the marking phase, not 5.0 as in java.util.HashSet.

    If there are no removals, then iteration order is the same as insertion order. Any removal invalidates any ordering guarantees.

    This class should not be assumed to be universally superior to java.util.HashSet. 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 float DEFAULT_LOAD_FACTOR  
      private static int DEFAULT_SIZE  
      (package private) java.lang.Object[] elements
      The elements contained in the set, in the range of [0, size()).
      private long[] entries
      Contains the logical entries, in the range of [0, size()).
      private static long HASH_MASK
      Bitmask that selects the high 32 bits.
      (package private) float loadFactor
      The load factor.
      private static int MAXIMUM_CAPACITY  
      (package private) int modCount
      Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator.
      private static long NEXT_MASK
      Bitmask that selects the low 32 bits.
      private int size
      The number of elements contained in the set.
      private int[] table
      The hashtable.
      private int threshold
      When we have this many elements, resize the hashtable.
      (package private) static int UNSET  

    • Constructor Summary

      Constructors 
      Constructor Description
      CompactHashSet()
      Constructs a new empty instance of CompactHashSet.
      CompactHashSet​(int expectedSize)
      Constructs a new instance of CompactHashSet with the specified capacity.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E object)  
      (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()  
      boolean contains​(java.lang.Object object)  
      static <E> CompactHashSet<E> create()
      Creates an empty CompactHashSet instance.
      static <E> CompactHashSet<E> create​(E... elements)
      Creates a mutable CompactHashSet instance containing the given elements in unspecified order.
      static <E> CompactHashSet<E> create​(java.util.Collection<? extends E> collection)
      Creates a mutable CompactHashSet instance containing the elements of the given collection in unspecified order.
      static <E> CompactHashSet<E> createWithExpectedSize​(int expectedSize)
      Creates a CompactHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.
      (package private) int firstEntryIndex()  
      void forEach​(java.util.function.Consumer<? super E> action)  
      private static int getHash​(long entry)  
      private static int getNext​(long entry)
      Returns the index, or UNSET if the pointer is "null"
      (package private) int getSuccessor​(int entryIndex)  
      private int hashTableMask()  
      (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.
      boolean isEmpty()  
      java.util.Iterator<E> iterator()  
      (package private) void moveEntry​(int dstIndex)
      Moves the last entry in the entry array into dstIndex, and nulls out its old position.
      private static long[] newEntries​(int size)  
      private static int[] newTable​(int size)  
      private void readObject​(java.io.ObjectInputStream stream)  
      boolean remove​(java.lang.Object object)  
      private boolean remove​(java.lang.Object object, int hash)  
      (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 resizeMeMaybe​(int newSize)
      Returns currentSize + 1, after resizing the entries storage if necessary.
      private void resizeTable​(int newCapacity)  
      int size()  
      java.util.Spliterator<E> spliterator()  
      private static long swapNext​(long entry, int newNext)
      Returns a new entry value by changing the "next" index of an existing entry
      java.lang.Object[] toArray()  
      <T> T[] toArray​(T[] a)  
      void trimToSize()
      Ensures that this CompactHashSet has the smallest representation in memory, given its current size.
      private void writeObject​(java.io.ObjectOutputStream stream)
      The serial form currently mimics Android's java.util.HashSet version, e.g.

      • 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

      • NEXT_MASK

        private static final long NEXT_MASK
        Bitmask that selects the low 32 bits.
        See Also:
        Constant Field Values

      • HASH_MASK

        private static final long HASH_MASK
        Bitmask that selects the high 32 bits.
        See Also:
        Constant Field Values

      • table

        private transient int[] table
        The hashtable. Its values are indexes to both the elements and entries arrays.

        Currently, the UNSET value means "null pointer", and any non negative value x is the actual index.

        Its size must be a power of two.

      • entries

        private transient long[] entries
        Contains the logical entries, in the range of [0, size()). The high 32 bits of each long is the smeared hash of the element, whereas the low 32 bits is the "next" pointer (pointing to the next entry in the bucket chain). The pointers in [size(), entries.length) are all "null" (UNSET).

      • elements

        transient java.lang.Object[] elements
        The elements contained in the set, in the range of [0, size()).

      • loadFactor

        transient float loadFactor
        The load factor.

      • modCount

        transient int modCount
        Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator. Note that we choose not to make this volatile, so we do less of a "best effort" to track such errors, for better performance.

      • threshold

        private transient int threshold
        When we have this many elements, resize the hashtable.

      • size

        private transient int size
        The number of elements contained in the set.

    • Constructor Detail

      • CompactHashSet

        CompactHashSet()
        Constructs a new empty instance of CompactHashSet.

      • CompactHashSet

        CompactHashSet​(int expectedSize)
        Constructs a new instance of CompactHashSet with the specified capacity.
        Parameters:
        expectedSize - the initial capacity of this CompactHashSet.

    • Method Detail

      • create

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

      • create

        public static <E> CompactHashSet<E> create​(java.util.Collection<? extends E> collection)
        Creates a mutable CompactHashSet instance containing the elements of the given collection in unspecified order.
        Parameters:
        collection - the elements that the set should contain
        Returns:
        a new CompactHashSet containing those elements (minus duplicates)

      • create

        public static <E> CompactHashSet<E> create​(E... elements)
        Creates a mutable CompactHashSet instance containing the given elements in unspecified order.
        Parameters:
        elements - the elements that the set should contain
        Returns:
        a new CompactHashSet containing those elements (minus duplicates)

      • createWithExpectedSize

        public static <E> CompactHashSet<E> createWithExpectedSize​(int expectedSize)
        Creates a CompactHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.
        Parameters:
        expectedSize - the number of elements you expect to add to the returned set
        Returns:
        a new, empty CompactHashSet with enough capacity to hold expectedSize elements without resizing
        Throws:
        java.lang.IllegalArgumentException - if expectedSize is negative

      • init

        void init​(int expectedSize,
          float loadFactor)
        Pseudoconstructor for serialization support.

      • newTable

        private static int[] newTable​(int size)

      • newEntries

        private static long[] newEntries​(int size)

      • getHash

        private static int getHash​(long entry)

      • getNext

        private static int getNext​(long entry)
        Returns the index, or UNSET if the pointer is "null"

      • swapNext

        private static long swapNext​(long entry,
                             int newNext)
        Returns a new entry value by changing the "next" index of an existing entry

      • hashTableMask

        private int hashTableMask()

      • add

        public boolean add​(E object)
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.Set<E>
        Overrides:
        add in class java.util.AbstractCollection<E>

      • insertEntry

        void insertEntry​(int entryIndex,
                 E object,
                 int hash)
        Creates a fresh entry with the specified object at the specified position in the entry arrays.

      • resizeMeMaybe

        private void resizeMeMaybe​(int newSize)
        Returns currentSize + 1, after resizing the entries storage if necessary.

      • resizeEntries

        void resizeEntries​(int newCapacity)
        Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.

      • resizeTable

        private void resizeTable​(int newCapacity)

      • contains

        public boolean contains​(java.lang.Object object)
        Specified by:
        contains in interface java.util.Collection<E>
        Specified by:
        contains in interface java.util.Set<E>
        Overrides:
        contains in class java.util.AbstractCollection<E>

      • remove

        public boolean remove​(java.lang.Object object)
        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.Set<E>
        Overrides:
        remove in class java.util.AbstractCollection<E>

      • remove

        private boolean remove​(java.lang.Object object,
                       int hash)

      • moveEntry

        void moveEntry​(int dstIndex)
        Moves the last entry in the entry array into dstIndex, and nulls out its old position.

      • firstEntryIndex

        int firstEntryIndex()

      • getSuccessor

        int getSuccessor​(int entryIndex)

      • adjustAfterRemove

        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.

      • iterator

        public java.util.Iterator<E> iterator()
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in interface java.util.Set<E>
        Specified by:
        iterator in class java.util.AbstractCollection<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>

      • forEach

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

      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.Set<E>
        Specified by:
        size in class java.util.AbstractCollection<E>

      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<E>
        Specified by:
        isEmpty in interface java.util.Set<E>
        Overrides:
        isEmpty in class java.util.AbstractCollection<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 java.util.AbstractCollection<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 java.util.AbstractCollection<E>

      • trimToSize

        public void trimToSize()
        Ensures that this CompactHashSet has the smallest representation in memory, given its current size.

      • 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 java.util.AbstractCollection<E>

      • writeObject

        private void writeObject​(java.io.ObjectOutputStream stream)
                  throws java.io.IOException
        The serial form currently mimics Android's java.util.HashSet version, e.g. see http://omapzoom.org/?p=platform/libcore.git;a=blob;f=luni/src/main/java/java/util/HashSet.java
        Throws:
        java.io.IOException

      • readObject

        private void readObject​(java.io.ObjectInputStream stream)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException