Class LightHashSet

All Implemented Interfaces:
Cloneable, Iterable, Collection, Set

public class LightHashSet extends AbstractSet implements Cloneable
A lighter (on memory) hash set
Advantages over HashSet:
  • Lower memory footprint
  • Everything is stored in a single array, this might improve cache performance (not verified)
  • Read-only operations on iterators should be concurrency-safe but they might return null values unexpectedly under concurrent modification (not verified)
Disadvantages:
  • removal is implemented with thombstone-keys, this can significantly increase the lookup time if many values are removed. Use compactify() for scrubbing
  • entry set iterators and thus transfers to other maps are slower than comparable implementations
  • the map does not store hashcodes and relies on either the key-objects themselves caching them (such as strings) or a fast computation of hashcodes
  • Field Details

    • THOMBSTONE

      private static final Object THOMBSTONE
    • NULLKEY

      private static final Object NULLKEY
    • DEFAULT_LOAD_FACTOR

      private static final float DEFAULT_LOAD_FACTOR
      See Also:
    • DEFAULT_CAPACITY

      private static final int DEFAULT_CAPACITY
      See Also:
    • loadFactor

      final float loadFactor
    • size

      int size
    • data

      Object[] data
  • Constructor Details

    • LightHashSet

      public LightHashSet()
    • LightHashSet

      public LightHashSet(int initialCapacity)
    • LightHashSet

      public LightHashSet(Collection c)
    • LightHashSet

      public LightHashSet(int initialCapacity, float loadFactor)
  • Method Details

    • clone

      public Object clone()
      Overrides:
      clone in class Object
    • iterator

      public Iterator iterator()
      Specified by:
      iterator in interface Collection
      Specified by:
      iterator in interface Iterable
      Specified by:
      iterator in interface Set
      Specified by:
      iterator in class AbstractCollection
    • add

      public boolean add(Object key)
      Specified by:
      add in interface Collection
      Specified by:
      add in interface Set
      Overrides:
      add in class AbstractCollection
    • size

      public int size()
      Specified by:
      size in interface Collection
      Specified by:
      size in interface Set
      Specified by:
      size in class AbstractCollection
    • addAll

      public boolean addAll(Collection c)
      Specified by:
      addAll in interface Collection
      Specified by:
      addAll in interface Set
      Overrides:
      addAll in class AbstractCollection
    • capacity

      public int capacity()
    • get

      public Object get(Object key)
      Fetches an element which does equal() the provided object but is not necessarily the same object
      Parameters:
      Object - to retrieve
      Returns:
      an object fulfilling the equals contract or null if no such object was found in this set
    • addInternal

      private boolean addInternal(Object key, boolean bulkAdd)
    • remove

      public boolean remove(Object key)
      Specified by:
      remove in interface Collection
      Specified by:
      remove in interface Set
      Overrides:
      remove in class AbstractCollection
    • removeForIndex

      private void removeForIndex(int idx)
    • clear

      public void clear()
      Specified by:
      clear in interface Collection
      Specified by:
      clear in interface Set
      Overrides:
      clear in class AbstractCollection
    • contains

      public boolean contains(Object key)
      Specified by:
      contains in interface Collection
      Specified by:
      contains in interface Set
      Overrides:
      contains in class AbstractCollection
    • keysEqual

      private boolean keysEqual(Object o1, Object o2)
    • findIndex

      private int findIndex(Object keyToFind)
    • nonModifyingFindIndex

      private int nonModifyingFindIndex(Object keyToFind)
    • checkCapacity

      private void checkCapacity(int n)
    • compactify

      public void compactify(float compactingLoadFactor)
      will shrink the internal storage size to the least possible amount, should be used after removing many entries for example
      Parameters:
      compactingLoadFactor - load factor for the compacting operation. Use 0f to compact with the load factor specified during instantiation. Use negative values of the desired load factors to compact only when it would reduce the storage size.
    • adjustCapacity

      private void adjustCapacity(int newSize)
    • test

      static void test()
    • main

      public static void main(String[] args)