Class LightHashSet

  • All Implemented Interfaces:
    java.lang.Cloneable, java.lang.Iterable, java.util.Collection, java.util.Set

    public class LightHashSet
    extends java.util.AbstractSet
    implements java.lang.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 compareable 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
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(java.lang.Object key)  
      boolean addAll​(java.util.Collection c)  
      private boolean addInternal​(java.lang.Object key, boolean bulkAdd)  
      private void adjustCapacity​(int newSize)  
      int capacity()  
      private void checkCapacity​(int n)  
      void clear()  
      java.lang.Object clone()  
      void compactify​(float compactingLoadFactor)
      will shrink the internal storage size to the least possible amount, should be used after removing many entries for example
      boolean contains​(java.lang.Object key)  
      private int findIndex​(java.lang.Object keyToFind)  
      java.lang.Object get​(java.lang.Object key)
      Fetches an element which does equal() the provided object but is not necessarily the same object
      java.util.Iterator iterator()  
      private boolean keysEqual​(java.lang.Object o1, java.lang.Object o2)  
      static void main​(java.lang.String[] args)  
      private int nonModifyingFindIndex​(java.lang.Object keyToFind)  
      boolean remove​(java.lang.Object key)  
      private void removeForIndex​(int idx)  
      int size()  
      (package private) static void test()  
      • Methods inherited from class java.util.AbstractSet

        equals, hashCode, removeAll
      • Methods inherited from class java.util.AbstractCollection

        containsAll, isEmpty, retainAll, toArray, toArray, toString
      • Methods inherited from class java.lang.Object

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

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

        forEach
      • Methods inherited from interface java.util.Set

        containsAll, isEmpty, retainAll, spliterator, toArray, toArray
    • Field Detail

      • THOMBSTONE

        private static final java.lang.Object THOMBSTONE
      • NULLKEY

        private static final java.lang.Object NULLKEY
      • loadFactor

        final float loadFactor
      • size

        int size
      • data

        java.lang.Object[] data
    • Constructor Detail

      • LightHashSet

        public LightHashSet()
      • LightHashSet

        public LightHashSet​(int initialCapacity)
      • LightHashSet

        public LightHashSet​(java.util.Collection c)
      • LightHashSet

        public LightHashSet​(int initialCapacity,
                            float loadFactor)
    • Method Detail

      • clone

        public java.lang.Object clone()
        Overrides:
        clone in class java.lang.Object
      • iterator

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

        public boolean add​(java.lang.Object key)
        Specified by:
        add in interface java.util.Collection
        Specified by:
        add in interface java.util.Set
        Overrides:
        add in class java.util.AbstractCollection
      • size

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

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

        public int capacity()
      • get

        public java.lang.Object get​(java.lang.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​(java.lang.Object key,
                                    boolean bulkAdd)
      • remove

        public boolean remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Collection
        Specified by:
        remove in interface java.util.Set
        Overrides:
        remove in class java.util.AbstractCollection
      • removeForIndex

        private void removeForIndex​(int idx)
      • clear

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

        public boolean contains​(java.lang.Object key)
        Specified by:
        contains in interface java.util.Collection
        Specified by:
        contains in interface java.util.Set
        Overrides:
        contains in class java.util.AbstractCollection
      • keysEqual

        private boolean keysEqual​(java.lang.Object o1,
                                  java.lang.Object o2)
      • findIndex

        private int findIndex​(java.lang.Object keyToFind)
      • nonModifyingFindIndex

        private int nonModifyingFindIndex​(java.lang.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​(java.lang.String[] args)