Class HopscotchHashMap<K,​V>

  • All Implemented Interfaces:
    java.util.Map<K,​V>

    public class HopscotchHashMap<K,​V>
    extends ArrayMap<K,​V>
    Lookup on a table without collisions will require only single access, if there are collisions it will be limited to (number of collisions to particular bin + 1) and all those will lie in proximity (32 * reference size). Inserts can be O(n) in the worst case when we have to rehash whole table or search through close-to-full for an empty spot.

    Not thread safe (though, look-ups are safe when there are no concurrent modifications).

    See Also:
    Hopscotch hashing
    • Nested Class Summary

      • 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>
    • Constructor Summary

      Constructors 
      Constructor Description
      HopscotchHashMap​(int initialCapacity)  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      V get​(java.lang.Object key)  
      V put​(K key, V value)  
      V remove​(java.lang.Object key)  
      • Methods inherited from class java.util.AbstractMap

        clone, equals, hashCode, isEmpty, putAll, 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
    • Constructor Detail

      • HopscotchHashMap

        public HopscotchHashMap​(int initialCapacity)
    • Method Detail

      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Specified by:
        get in class ArrayMap<K,​V>
      • put

        public V put​(K key,
                     V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Specified by:
        put in class ArrayMap<K,​V>
      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Specified by:
        remove in class ArrayMap<K,​V>