Package org.processmining.earthmoversstochasticconformancechecking.datastructures

Class HashMapLinearProbing<Key,​Value>

  • All Implemented Interfaces:
    java.util.Map<Key,​Value>
    public class HashMapLinearProbing<Key,​Value>
extends java.lang.Object
implements java.util.Map<Key,​Value>
    The HashMapLinearProbing class represents a symbol table of generic key-value pairs. It supports the usual put, get, contains, delete, size, and is-empty methods. It also provides a keys method for iterating over all of the keys. A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike Map, this class uses the convention that values cannot be null-setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

    This implementation uses a linear probing hash table. It requires that the key type overrides the equals() and hashCode() methods. The expected time per put, contains, or remove operation is constant, subject to the uniform hashing assumption. The size, and is-empty operations take constant time. Construction takes constant time.

    For additional documentation, see Section 3.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. For other implementations, see ST, BinarySearchST, SequentialSearchST, BST, RedBlackBST, and SeparateChainingHashST,

    Author:
    brockhoff, Robert Sedgewick, Kevin Wayne
    See Also:
    https://algs4.cs.princeton.edu/34hash/LinearProbingHashST.java.html

    • Nested Class Summary

      • 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
      HashMapLinearProbing()
      Initializes an empty symbol table.
      HashMapLinearProbing​(int capacity)
      Initializes an empty symbol table with the specified initial capacity.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()  
      boolean containsKey​(java.lang.Object key)
      Returns true if this symbol table contains the specified key.
      boolean containsValue​(java.lang.Object value)  
      java.util.Set<java.util.Map.Entry<Key,​Value>> entrySet()  
      Value get​(java.lang.Object key)
      Returns the value associated with the specified key.
      boolean isEmpty()
      Returns true if this symbol table is empty.
      java.lang.Iterable<Key> keys()
      Returns all keys in this symbol table as an Iterable.
      java.util.Set<Key> keySet()  
      Value put​(Key key, Value val)
      Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key.
      void putAll​(java.util.Map<? extends Key,​? extends Value> m)  
      Value remove​(java.lang.Object key)
      Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
      int size()
      Returns the number of key-value pairs in this symbol table.
      java.util.Collection<Value> values()  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

    • Constructor Detail

      • HashMapLinearProbing

        public HashMapLinearProbing()
        Initializes an empty symbol table.

      • HashMapLinearProbing

        public HashMapLinearProbing​(int capacity)
        Initializes an empty symbol table with the specified initial capacity.
        Parameters:
        capacity - the initial capacity

    • Method Detail

      • size

        public int size()
        Returns the number of key-value pairs in this symbol table.
        Specified by:
        size in interface java.util.Map<Key,​Value>
        Returns:
        the number of key-value pairs in this symbol table

      • isEmpty

        public boolean isEmpty()
        Returns true if this symbol table is empty.
        Specified by:
        isEmpty in interface java.util.Map<Key,​Value>
        Returns:
        true if this symbol table is empty; false otherwise

      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Returns true if this symbol table contains the specified key.
        Specified by:
        containsKey in interface java.util.Map<Key,​Value>
        Parameters:
        key - the key
        Returns:
        true if this symbol table contains key; false otherwise

      • put

        public Value put​(Key key,
                 Value val)
        Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is null.
        Specified by:
        put in interface java.util.Map<Key,​Value>
        Parameters:
        key - the key
        val - the value

      • get

        public Value get​(java.lang.Object key)
        Returns the value associated with the specified key.
        Specified by:
        get in interface java.util.Map<Key,​Value>
        Parameters:
        key - the key
        Returns:
        the value associated with key; null if no such value

      • remove

        public Value remove​(java.lang.Object key)
        Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
        Specified by:
        remove in interface java.util.Map<Key,​Value>
        Parameters:
        key - the key

      • keys

        public java.lang.Iterable<Key> keys()
        Returns all keys in this symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).
        Returns:
        all keys in this symbol table

      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<Key,​Value>

      • putAll

        public void putAll​(java.util.Map<? extends Key,​? extends Value> m)
        Specified by:
        putAll in interface java.util.Map<Key,​Value>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<Key,​Value>

      • keySet

        public java.util.Set<Key> keySet()
        Specified by:
        keySet in interface java.util.Map<Key,​Value>

      • values

        public java.util.Collection<Value> values()
        Specified by:
        values in interface java.util.Map<Key,​Value>

      • entrySet

        public java.util.Set<java.util.Map.Entry<Key,​Value>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<Key,​Value>