Class LightHashMap<S,​T>

  • All Implemented Interfaces:
    java.lang.Cloneable, java.util.Map<S,​T>
    Direct Known Subclasses:
    JSONObject, LightHashMapEx

    public class LightHashMap<S,​T>
    extends java.util.AbstractMap<S,​T>
    implements java.lang.Cloneable
    A lighter (on memory) hash map
    Advantages over HashMap:
    • Lower memory footprint
    • Everything is stored in a single array, this might improve cache performance (not verified)
    • Read-only operations on Key and Value iterators should be concurrency-safe (Entry iterators are not) 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
    • concurrent modification detection is not as fail-fast as HashMap as no modification counter is used and only structural differences are noted
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  LightHashMap.EntrySet  
      private class  LightHashMap.HashIterator  
      private class  LightHashMap.KeySet  
      private class  LightHashMap.Values  
      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private java.lang.Object add​(java.lang.Object key, java.lang.Object value, 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 containsKey​(java.lang.Object key)  
      boolean containsValue​(java.lang.Object value)  
      java.util.Set entrySet()  
      private int findIndex​(java.lang.Object keyToFind)  
      T get​(java.lang.Object key)  
      private boolean keysEqual​(java.lang.Object o1, java.lang.Object o2)  
      java.util.Set<S> keySet()  
      static void main​(java.lang.String[] args)  
      private int nonModifyingFindIndex​(java.lang.Object keyToFind)  
      T put​(java.lang.Object key, java.lang.Object value)  
      void putAll​(java.util.Map m)  
      T remove​(java.lang.Object key)  
      private java.lang.Object removeForIndex​(int idx)  
      (package private) static void test()  
      java.util.Collection<T> values()  
      • Methods inherited from class java.util.AbstractMap

        equals, hashCode, isEmpty, size, toString
      • Methods inherited from class java.lang.Object

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

        compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
    • 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

      • LightHashMap

        public LightHashMap()
      • LightHashMap

        public LightHashMap​(int initialCapacity)
      • LightHashMap

        public LightHashMap​(java.util.Map m)
      • LightHashMap

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

      • clone

        public java.lang.Object clone()
        Overrides:
        clone in class java.util.AbstractMap<S,​T>
      • entrySet

        public java.util.Set entrySet()
        Specified by:
        entrySet in interface java.util.Map<S,​T>
        Specified by:
        entrySet in class java.util.AbstractMap<S,​T>
      • put

        public T put​(java.lang.Object key,
                     java.lang.Object value)
        Specified by:
        put in interface java.util.Map<S,​T>
        Overrides:
        put in class java.util.AbstractMap<S,​T>
      • putAll

        public void putAll​(java.util.Map m)
        Specified by:
        putAll in interface java.util.Map<S,​T>
        Overrides:
        putAll in class java.util.AbstractMap<S,​T>
      • keySet

        public java.util.Set<S> keySet()
        Specified by:
        keySet in interface java.util.Map<S,​T>
        Overrides:
        keySet in class java.util.AbstractMap<S,​T>
      • values

        public java.util.Collection<T> values()
        Specified by:
        values in interface java.util.Map<S,​T>
        Overrides:
        values in class java.util.AbstractMap<S,​T>
      • capacity

        public int capacity()
      • get

        public T get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<S,​T>
        Overrides:
        get in class java.util.AbstractMap<S,​T>
      • add

        private java.lang.Object add​(java.lang.Object key,
                                     java.lang.Object value,
                                     boolean bulkAdd)
      • remove

        public T remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<S,​T>
        Overrides:
        remove in class java.util.AbstractMap<S,​T>
      • removeForIndex

        private java.lang.Object removeForIndex​(int idx)
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<S,​T>
        Overrides:
        clear in class java.util.AbstractMap<S,​T>
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<S,​T>
        Overrides:
        containsKey in class java.util.AbstractMap<S,​T>
      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<S,​T>
        Overrides:
        containsValue in class java.util.AbstractMap<S,​T>
      • 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)