Class IntHashSet

  • All Implemented Interfaces:
    java.lang.Iterable<java.lang.Integer>, java.util.Collection<java.lang.Integer>, java.util.Set<java.lang.Integer>

    public class IntHashSet
    extends java.util.AbstractSet<java.lang.Integer>
    Open-addressing with linear-probing expandable hash set. Allocation free in steady state use when expanded.

    By storing elements as int primitives this significantly reduces memory consumption compared with Java's builtin HashSet<Integer>. It implements Set<Integer> for convenience, but calling functionality via those methods can add boxing overhead to your usage.

    This class is not Threadsafe.

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

    See Also:
    IntHashSet.IntIterator, Set
    • Constructor Summary

      Constructors 
      Constructor Description
      IntHashSet()
      Construct a hash set with DEFAULT_INITIAL_CAPACITY, Hashing.DEFAULT_LOAD_FACTOR, iterator caching support and 0 as a missing value.
      IntHashSet​(int proposedCapacity)
      Construct a hash set with a proposed capacity, Hashing.DEFAULT_LOAD_FACTOR, iterator caching support and 0 as a missing value.
      IntHashSet​(int proposedCapacity, float loadFactor)
      Construct a hash set with a proposed initial capacity, load factor, iterator caching support and 0 as a missing value.
      IntHashSet​(int proposedCapacity, float loadFactor, boolean shouldAvoidAllocation)
      Construct a hash set with a proposed initial capacity, load factor, iterator caching support and -1 as a missing value.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(int value)
      Primitive specialised overload of {this#add(Integer)}.
      boolean add​(java.lang.Integer value)
      boolean addAll​(java.util.Collection<? extends java.lang.Integer> coll)
      boolean addAll​(IntHashSet coll)
      Alias for addAll(Collection) for the specialized case when adding another IntHashSet, 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​(int value)
      Contains method that does not box values.
      boolean contains​(java.lang.Object value)
      boolean containsAll​(IntHashSet coll)
      IntHashSet specialised variant of {this#containsAll(Collection)}.
      void copy​(IntHashSet that)
      Copy values from another IntHashSet into this one.
      private void copyValues​(java.lang.Object[] arrayCopy)  
      IntHashSet difference​(IntHashSet other)
      Fast Path set difference for comparison with another IntHashSet.
      boolean equals​(java.lang.Object other)
      void forEachInt​(java.util.function.IntConsumer action)
      Iterate over the collection without boxing.
      int hashCode()
      private void increaseCapacity()  
      boolean isEmpty()
      IntHashSet.IntIterator 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​(int value)
      Specialised version of {this#remove(Object)} for int.
      boolean remove​(java.lang.Object value)
      boolean removeAll​(java.util.Collection<?> coll)
      boolean removeAll​(IntHashSet coll)
      Alias for removeAll(Collection) for the specialized case when removing another IntHashSet, avoids boxing and allocations.
      boolean removeIf​(java.util.function.Predicate<? super java.lang.Integer> filter)
      boolean removeIfInt​(java.util.function.IntPredicate filter)
      Removes all the elements of this collection that satisfy the given predicate.
      int resizeThreshold()
      Get the actual threshold which when reached the map will resize.
      boolean retainAll​(java.util.Collection<?> coll)
      boolean retainAll​(IntHashSet coll)
      Alias for retainAll(Collection) for the specialized case when retaining on another IntHashSet, avoids boxing and allocations.
      int size()
      java.lang.Object[] toArray()
      <T> T[] toArray​(T[] a)
      java.lang.String toString()
      • Methods inherited from class java.util.AbstractCollection

        containsAll
      • Methods inherited from class java.lang.Object

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

        parallelStream, stream, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
      • Methods inherited from interface java.util.Set

        containsAll, spliterator
    • 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
      • shouldAvoidAllocation

        private final boolean shouldAvoidAllocation
      • containsMissingValue

        private boolean containsMissingValue
      • loadFactor

        private final float loadFactor
      • resizeThreshold

        private int resizeThreshold
      • sizeOfArrayValues

        private int sizeOfArrayValues
      • values

        private int[] values
    • Constructor Detail

      • IntHashSet

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

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

        public IntHashSet​(int proposedCapacity,
                          float loadFactor,
                          boolean shouldAvoidAllocation)
        Construct a hash set with a proposed initial capacity, load factor, iterator caching support and -1 as a missing value.
        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.
      • add

        public boolean add​(java.lang.Integer value)
        Specified by:
        add in interface java.util.Collection<java.lang.Integer>
        Specified by:
        add in interface java.util.Set<java.lang.Integer>
        Overrides:
        add in class java.util.AbstractCollection<java.lang.Integer>
      • add

        public boolean add​(int value)
        Primitive specialised overload of {this#add(Integer)}.
        Parameters:
        value - the value to add.
        Returns:
        true if the collection has changed, false otherwise.
      • 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<java.lang.Integer>
        Specified by:
        remove in interface java.util.Set<java.lang.Integer>
        Overrides:
        remove in class java.util.AbstractCollection<java.lang.Integer>
      • remove

        public boolean remove​(int value)
        Specialised version of {this#remove(Object)} for int.
        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<java.lang.Integer>
        Specified by:
        contains in interface java.util.Set<java.lang.Integer>
        Overrides:
        contains in class java.util.AbstractCollection<java.lang.Integer>
      • contains

        public boolean contains​(int value)
        Contains method that does not box values.
        Parameters:
        value - to be checked for if the set contains it.
        Returns:
        true if the value is contained in the set otherwise false.
        See Also:
        Collection.contains(Object)
      • size

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

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

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

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

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

        public boolean containsAll​(IntHashSet coll)
        IntHashSet specialised variant of {this#containsAll(Collection)}.
        Parameters:
        coll - int hash set to compare against.
        Returns:
        true if every element in other is in this.
      • difference

        public IntHashSet difference​(IntHashSet other)
        Fast Path set difference for comparison with another IntHashSet.

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

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

        public boolean removeIf​(java.util.function.Predicate<? super java.lang.Integer> filter)
      • removeIfInt

        public boolean removeIfInt​(java.util.function.IntPredicate filter)
        Removes all the elements of this collection that satisfy the given predicate.

        NB: Renamed from removeIf to avoid overloading on parameter types of lambda expression, which doesn't play well with type inference in lambda expressions.

        Parameters:
        filter - which returns true for elements to be removed.
        Returns:
        true if any elements were removed.
      • removeAll

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

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

        public boolean retainAll​(java.util.Collection<?> coll)
        Specified by:
        retainAll in interface java.util.Collection<java.lang.Integer>
        Specified by:
        retainAll in interface java.util.Set<java.lang.Integer>
        Overrides:
        retainAll in class java.util.AbstractCollection<java.lang.Integer>
      • retainAll

        public boolean retainAll​(IntHashSet coll)
        Alias for retainAll(Collection) for the specialized case when retaining on another IntHashSet, avoids boxing and allocations.
        Parameters:
        coll - containing elements to be retained in this set.
        Returns:
        true if this set changed as a result of the call.
      • iterator

        public IntHashSet.IntIterator iterator()
        Specified by:
        iterator in interface java.util.Collection<java.lang.Integer>
        Specified by:
        iterator in interface java.lang.Iterable<java.lang.Integer>
        Specified by:
        iterator in interface java.util.Set<java.lang.Integer>
        Specified by:
        iterator in class java.util.AbstractCollection<java.lang.Integer>
      • forEachInt

        public void forEachInt​(java.util.function.IntConsumer action)
        Iterate over the collection without boxing.
        Parameters:
        action - to be taken for each element.
      • copy

        public void copy​(IntHashSet that)
        Copy values from another IntHashSet into this one.
        Parameters:
        that - set to copy values from.
      • toString

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

        public <T> T[] toArray​(T[] a)
        Specified by:
        toArray in interface java.util.Collection<java.lang.Integer>
        Specified by:
        toArray in interface java.util.Set<java.lang.Integer>
        Overrides:
        toArray in class java.util.AbstractCollection<java.lang.Integer>
      • toArray

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

        private void copyValues​(java.lang.Object[] arrayCopy)
      • equals

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

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