Class LongHashSet

All Implemented Interfaces:
Iterable<Long>, Collection<Long>, Set<Long>

public class LongHashSet extends AbstractSet<Long>
Open-addressing with linear-probing expandable hash set. Allocation free in steady state use when expanded.

By storing elements as long primitives this significantly reduces memory consumption compared with Java's builtin HashSet<Long>. It implements Set<Long> 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:
  • Field Details

    • DEFAULT_INITIAL_CAPACITY

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

      static final long MISSING_VALUE
      See Also:
    • shouldAvoidAllocation

      private final boolean shouldAvoidAllocation
    • containsMissingValue

      private boolean containsMissingValue
    • loadFactor

      private final float loadFactor
    • resizeThreshold

      private int resizeThreshold
    • sizeOfArrayValues

      private int sizeOfArrayValues
    • values

      private long[] values
    • iterator

      private LongHashSet.LongIterator iterator
  • Constructor Details

    • LongHashSet

      public LongHashSet()
      Construct a hash set with DEFAULT_INITIAL_CAPACITY, Hashing.DEFAULT_LOAD_FACTOR, iterator caching support and 0 as a missing value.
    • LongHashSet

      public LongHashSet(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.
    • LongHashSet

      public LongHashSet(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.
    • LongHashSet

      public LongHashSet(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 Details

    • 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(Long value)
      Specified by:
      add in interface Collection<Long>
      Specified by:
      add in interface Set<Long>
      Overrides:
      add in class AbstractCollection<Long>
    • add

      public boolean add(long value)
      Primitive specialised overload of {this#add(Long)}.
      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(Object value)
      Specified by:
      remove in interface Collection<Long>
      Specified by:
      remove in interface Set<Long>
      Overrides:
      remove in class AbstractCollection<Long>
    • remove

      public boolean remove(long value)
      Specialised version of {this#remove(Object)} for long.
      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(Object value)
      Specified by:
      contains in interface Collection<Long>
      Specified by:
      contains in interface Set<Long>
      Overrides:
      contains in class AbstractCollection<Long>
    • contains

      public boolean contains(long 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:
    • size

      public int size()
      Specified by:
      size in interface Collection<Long>
      Specified by:
      size in interface Set<Long>
      Specified by:
      size in class AbstractCollection<Long>
    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Collection<Long>
      Specified by:
      isEmpty in interface Set<Long>
      Overrides:
      isEmpty in class AbstractCollection<Long>
    • clear

      public void clear()
      Specified by:
      clear in interface Collection<Long>
      Specified by:
      clear in interface Set<Long>
      Overrides:
      clear in class AbstractCollection<Long>
    • addAll

      public boolean addAll(Collection<? extends Long> coll)
      Specified by:
      addAll in interface Collection<Long>
      Specified by:
      addAll in interface Set<Long>
      Overrides:
      addAll in class AbstractCollection<Long>
    • addAll

      public boolean addAll(LongHashSet coll)
      Alias for addAll(Collection) for the specialized case when adding another LongHashSet, 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(LongHashSet coll)
      LongHashSet specialised variant of {this#containsAll(Collection)}.
      Parameters:
      coll - long hash set to compare against.
      Returns:
      true if every element in other is in this.
    • difference

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

      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(Predicate<? super Long> filter)
    • removeIfLong

      public boolean removeIfLong(LongPredicate 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(Collection<?> coll)
      Specified by:
      removeAll in interface Collection<Long>
      Specified by:
      removeAll in interface Set<Long>
      Overrides:
      removeAll in class AbstractSet<Long>
    • removeAll

      public boolean removeAll(LongHashSet coll)
      Alias for removeAll(Collection) for the specialized case when removing another LongHashSet, 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(Collection<?> coll)
      Specified by:
      retainAll in interface Collection<Long>
      Specified by:
      retainAll in interface Set<Long>
      Overrides:
      retainAll in class AbstractCollection<Long>
    • retainAll

      public boolean retainAll(LongHashSet coll)
      Alias for retainAll(Collection) for the specialized case when retaining on another LongHashSet, 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 LongHashSet.LongIterator iterator()
      Specified by:
      iterator in interface Collection<Long>
      Specified by:
      iterator in interface Iterable<Long>
      Specified by:
      iterator in interface Set<Long>
      Specified by:
      iterator in class AbstractCollection<Long>
    • forEachLong

      public void forEachLong(LongConsumer action)
      Iterate over the collection without boxing.
      Parameters:
      action - to be taken for each element.
    • copy

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

      public String toString()
      Overrides:
      toString in class AbstractCollection<Long>
    • toArray

      public <T> T[] toArray(T[] a)
      Specified by:
      toArray in interface Collection<Long>
      Specified by:
      toArray in interface Set<Long>
      Overrides:
      toArray in class AbstractCollection<Long>
    • toArray

      public Object[] toArray()
      Specified by:
      toArray in interface Collection<Long>
      Specified by:
      toArray in interface Set<Long>
      Overrides:
      toArray in class AbstractCollection<Long>
    • copyValues

      private void copyValues(Object[] arrayCopy)
    • equals

      public boolean equals(Object other)
      Specified by:
      equals in interface Collection<Long>
      Specified by:
      equals in interface Set<Long>
      Overrides:
      equals in class AbstractSet<Long>
    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface Collection<Long>
      Specified by:
      hashCode in interface Set<Long>
      Overrides:
      hashCode in class AbstractSet<Long>