Class ObjectHashSet<T>

  • Type Parameters:
    T - type of values stored in the Set
    All Implemented Interfaces:
    java.lang.Iterable<T>, java.util.Collection<T>, java.util.Set<T>

    public class ObjectHashSet<T>
    extends java.util.AbstractSet<T>
    Open-addressing with linear-probing expandable hash set. Allocation free in steady state use when expanded. Ability to be notified when resizing occurs so that appropriate sizing can be implemented.

    Not Threadsafe.

    This HashSet caches its iterator object by default, which can be overridden, so nested iteration is not supported. You can override this behaviour at construction by indicating that the iterator should not be cached.

    See Also:
    ObjectHashSet.ObjectIterator, Set
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  ObjectHashSet.ObjectIterator
      Iterator over the set which can be optionally cached to avoid allocation.
    • Constructor Summary

      Constructors 
      Constructor Description
      ObjectHashSet()
      Construct a hash set with DEFAULT_INITIAL_CAPACITY, Hashing.DEFAULT_LOAD_FACTOR, and iterator caching support.
      ObjectHashSet​(int proposedCapacity)
      Construct a hash set with a proposed initial capacity, Hashing.DEFAULT_LOAD_FACTOR, and iterator caching support.
      ObjectHashSet​(int proposedCapacity, float loadFactor)
      Construct a hash set with a proposed initial capacity, load factor, and iterator caching support.
      ObjectHashSet​(int proposedCapacity, float loadFactor, boolean shouldAvoidAllocation)
      Construct a hash set with a proposed initial capacity, load factor, and indicated iterator caching support.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(T value)  
      boolean addAll​(java.util.Collection<? extends T> coll)
      boolean addAll​(ObjectHashSet<T> coll)
      Alias for addAll(Collection) for the specialized case when adding another ObjectHashSet, avoids boxing and allocations
      int capacity()
      Get the total capacity for the set to which the load factor with be a fraction of.
      void clear()
      void compact()
      Compact the backing arrays by rehashing with a capacity just larger than current size and giving consideration to the load factor.
      (package private) void compactChain​(int deleteIndex)  
      boolean contains​(java.lang.Object value)
      boolean containsAll​(java.util.Collection<?> coll)
      void copy​(ObjectHashSet<T> that)
      Copy data from the provided ObjectHashSet into this one.
      ObjectHashSet<T> difference​(ObjectHashSet<T> other)
      Fast Path set difference for comparison with another ObjectHashSet.
      private static <T> boolean disjunction​(java.util.Collection<T> coll, java.util.function.Predicate<T> predicate)  
      boolean equals​(java.lang.Object other)
      void forEach​(java.util.function.Consumer<? super T> action)
      int hashCode()
      private void increaseCapacity()  
      boolean isEmpty()
      ObjectHashSet.ObjectIterator iterator()
      float loadFactor()
      Get the load factor beyond which the set will increase size.
      private static int next​(int index, int mask)  
      private void rehash​(int newCapacity)  
      boolean remove​(java.lang.Object value)  
      boolean removeAll​(java.util.Collection<?> coll)
      boolean removeAll​(ObjectHashSet<T> coll)
      Alias for removeAll(Collection) for the specialized case when removing another ObjectHashSet, avoids boxing and allocations
      void resizeNotifier​(java.util.function.IntConsumer resizeNotifier)
      Add a Consumer that will be called when the collection is re-sized.
      int resizeThreshold()
      Get the actual threshold which when reached the map will resize.
      int size()
      java.lang.String toString()
      • Methods inherited from class java.util.AbstractCollection

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

        retainAll, spliterator, toArray, toArray
    • Field Detail

      • DEFAULT_INITIAL_CAPACITY

        public static final int DEFAULT_INITIAL_CAPACITY
        The initial capacity used when none is specified in the constructor.
        See Also:
        Constant Field Values
      • MISSING_VALUE

        static final java.lang.Object MISSING_VALUE
      • shouldAvoidAllocation

        private final boolean shouldAvoidAllocation
      • loadFactor

        private final float loadFactor
      • resizeThreshold

        private int resizeThreshold
      • size

        private int size
      • values

        private T[] values
      • resizeNotifier

        private java.util.function.IntConsumer resizeNotifier
    • Constructor Detail

      • ObjectHashSet

        public ObjectHashSet​(int proposedCapacity)
        Construct a hash set with a proposed initial capacity, Hashing.DEFAULT_LOAD_FACTOR, and iterator caching support.
        Parameters:
        proposedCapacity - for the initial capacity of the set.
      • ObjectHashSet

        public ObjectHashSet​(int proposedCapacity,
                             float loadFactor)
        Construct a hash set with a proposed initial capacity, load factor, and iterator caching support.
        Parameters:
        proposedCapacity - for the initial capacity of the set.
        loadFactor - to be used for resizing.
      • ObjectHashSet

        public ObjectHashSet​(int proposedCapacity,
                             float loadFactor,
                             boolean shouldAvoidAllocation)
        Construct a hash set with a proposed initial capacity, load factor, and indicated iterator caching support.
        Parameters:
        proposedCapacity - for the initial capacity of the set.
        loadFactor - to be used for resizing.
        shouldAvoidAllocation - should the iterator be cached to avoid further allocation.
    • Method Detail

      • loadFactor

        public float loadFactor()
        Get the load factor beyond which the set will increase size.
        Returns:
        load factor for when the set should increase size.
      • capacity

        public int capacity()
        Get the total capacity for the set to which the load factor with be a fraction of.
        Returns:
        the total capacity for the set.
      • resizeThreshold

        public int resizeThreshold()
        Get the actual threshold which when reached the map will resize. This is a function of the current capacity and load factor.
        Returns:
        the threshold when the map will resize.
      • resizeNotifier

        public void resizeNotifier​(java.util.function.IntConsumer resizeNotifier)
        Add a Consumer that will be called when the collection is re-sized.
        Parameters:
        resizeNotifier - IntConsumer containing the new resizeThreshold
      • add

        public boolean add​(T value)
        Specified by:
        add in interface java.util.Collection<T>
        Specified by:
        add in interface java.util.Set<T>
        Overrides:
        add in class java.util.AbstractCollection<T>
        Parameters:
        value - the value to add
        Returns:
        true if the collection has changed, false otherwise
        Throws:
        java.lang.NullPointerException - if the value is null
      • increaseCapacity

        private void increaseCapacity()
      • rehash

        private void rehash​(int newCapacity)
      • remove

        public boolean remove​(java.lang.Object value)
        Specified by:
        remove in interface java.util.Collection<T>
        Specified by:
        remove in interface java.util.Set<T>
        Overrides:
        remove in class java.util.AbstractCollection<T>
        Parameters:
        value - the value to remove
        Returns:
        true if the value was present, false otherwise
      • next

        private static int next​(int index,
                                int mask)
      • compactChain

        void compactChain​(int deleteIndex)
      • compact

        public void compact()
        Compact the backing arrays by rehashing with a capacity just larger than current size and giving consideration to the load factor.
      • contains

        public boolean contains​(java.lang.Object value)
        Specified by:
        contains in interface java.util.Collection<T>
        Specified by:
        contains in interface java.util.Set<T>
        Overrides:
        contains in class java.util.AbstractCollection<T>
      • size

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

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<T>
        Specified by:
        isEmpty in interface java.util.Set<T>
        Overrides:
        isEmpty in class java.util.AbstractCollection<T>
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<T>
        Specified by:
        clear in interface java.util.Set<T>
        Overrides:
        clear in class java.util.AbstractCollection<T>
      • containsAll

        public boolean containsAll​(java.util.Collection<?> coll)
        Specified by:
        containsAll in interface java.util.Collection<T>
        Specified by:
        containsAll in interface java.util.Set<T>
        Overrides:
        containsAll in class java.util.AbstractCollection<T>
      • addAll

        public boolean addAll​(java.util.Collection<? extends T> coll)
        Specified by:
        addAll in interface java.util.Collection<T>
        Specified by:
        addAll in interface java.util.Set<T>
        Overrides:
        addAll in class java.util.AbstractCollection<T>
      • addAll

        public boolean addAll​(ObjectHashSet<T> coll)
        Alias for addAll(Collection) for the specialized case when adding another ObjectHashSet, avoids boxing and allocations
        Parameters:
        coll - containing the values to be added.
        Returns:
        true if this set changed as a result of the call
      • difference

        public ObjectHashSet<T> difference​(ObjectHashSet<T> other)
        Fast Path set difference for comparison with another ObjectHashSet.

        NB: garbage free in the identical case, allocates otherwise.

        Parameters:
        other - the other set to subtract
        Returns:
        null if identical, otherwise the set of differences
      • removeAll

        public boolean removeAll​(java.util.Collection<?> coll)
        Specified by:
        removeAll in interface java.util.Collection<T>
        Specified by:
        removeAll in interface java.util.Set<T>
        Overrides:
        removeAll in class java.util.AbstractSet<T>
      • removeAll

        public boolean removeAll​(ObjectHashSet<T> coll)
        Alias for removeAll(Collection) for the specialized case when removing another ObjectHashSet, avoids boxing and allocations
        Parameters:
        coll - containing the values to be removed.
        Returns:
        true if this set changed as a result of the call
      • disjunction

        private static <T> boolean disjunction​(java.util.Collection<T> coll,
                                               java.util.function.Predicate<T> predicate)
      • iterator

        public ObjectHashSet.ObjectIterator iterator()
        Specified by:
        iterator in interface java.util.Collection<T>
        Specified by:
        iterator in interface java.lang.Iterable<T>
        Specified by:
        iterator in interface java.util.Set<T>
        Specified by:
        iterator in class java.util.AbstractCollection<T>
      • copy

        public void copy​(ObjectHashSet<T> that)
        Copy data from the provided ObjectHashSet into this one.
        Parameters:
        that - set to copy data from.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.util.AbstractCollection<T>
      • equals

        public boolean equals​(java.lang.Object other)
        Specified by:
        equals in interface java.util.Collection<T>
        Specified by:
        equals in interface java.util.Set<T>
        Overrides:
        equals in class java.util.AbstractSet<T>
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Collection<T>
        Specified by:
        hashCode in interface java.util.Set<T>
        Overrides:
        hashCode in class java.util.AbstractSet<T>
      • forEach

        public void forEach​(java.util.function.Consumer<? super T> action)