Package com.zybooks.dsaj.map

Class ProbeHashMap<K,V>

java.lang.Object
com.zybooks.dsaj.map.AbstractMap<K,V>
com.zybooks.dsaj.map.AbstractHashMap<K,V>
com.zybooks.dsaj.map.ProbeHashMap<K,V>
Type Parameters:
K - The key type (keys must be unique and hashable)
V - The value type
All Implemented Interfaces:
Map<K,V>
public class ProbeHashMap<K,V> extends AbstractHashMap<K,V>
Map implementation using hash table with linear probing.

  • Nested Class Summary

    Nested classes/interfaces inherited from class com.zybooks.dsaj.map.AbstractMap

    AbstractMap.MapEntry<K,V>

  • Field Summary

    Fields inherited from class com.zybooks.dsaj.map.AbstractHashMap

    capacity, n

  • Constructor Summary

    Constructors
    Constructor
    Description
    ProbeHashMap()
    Creates a hash table with capacity 17 and prime factor 109345121.
    ProbeHashMap(int cap)
    Creates a hash table with given capacity and prime number 109345121.
    ProbeHashMap(int cap, int p)
    Creates a hash table.

  • Method Summary

    Modifier and Type
    Method
    Description
    protected V
    bucketGet(int h, K k)
    Returns value associated with key k in bucket with hash value h.
    protected V
    bucketPut(int h, K k, V v)
    Associates key k with value v in bucket with hash value h, returning the previously associated value, if any.
    protected V
    bucketRemove(int h, K k)
    Removes entry having key k from bucket with hash value h, returning the previously associated value, if found.
    protected void
    createTable()
    Creates an empty table having length equal to current capacity.
    Iterable<Entry<K,V>>
    entrySet()
    Returns an iterable collection of all key-value entries of the map.

    Methods inherited from class com.zybooks.dsaj.map.AbstractHashMap

    get, put, remove, size

    Methods inherited from class com.zybooks.dsaj.map.AbstractMap

    isEmpty, keySet, values

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • ProbeHashMap

      public ProbeHashMap()
      Creates a hash table with capacity 17 and prime factor 109345121.

    • ProbeHashMap

      public ProbeHashMap(int cap)
      Creates a hash table with given capacity and prime number 109345121.
      Parameters:
      cap - the initial length of the hash table

    • ProbeHashMap

      public ProbeHashMap(int cap, int p)
      Creates a hash table.
      Parameters:
      cap - the initial length of the hash table
      p - a prime number used for the hash function

  • Method Details

    • createTable

      protected void createTable()
      Creates an empty table having length equal to current capacity.
      Specified by:
      createTable in class AbstractHashMap<K,V>

    • bucketGet

      protected V bucketGet(int h, K k)
      Returns value associated with key k in bucket with hash value h. If no such entry exists, returns null.
      Specified by:
      bucketGet in class AbstractHashMap<K,V>
      Parameters:
      h - the hash value of the relevant bucket
      k - the key of interest
      Returns:
      associate value (or null, if no such entry)

    • bucketPut

      protected V bucketPut(int h, K k, V v)
      Associates key k with value v in bucket with hash value h, returning the previously associated value, if any.
      Specified by:
      bucketPut in class AbstractHashMap<K,V>
      Parameters:
      h - the hash value of the relevant bucket
      k - the key of interest
      v - the value to be associated
      Returns:
      previous value associated with k (or null, if no such entry)

    • bucketRemove

      protected V bucketRemove(int h, K k)
      Removes entry having key k from bucket with hash value h, returning the previously associated value, if found.
      Specified by:
      bucketRemove in class AbstractHashMap<K,V>
      Parameters:
      h - the hash value of the relevant bucket
      k - the key of interest
      Returns:
      previous value associated with k (or null, if no such entry)

    • entrySet

      public Iterable<Entry<K,V>> entrySet()
      Returns an iterable collection of all key-value entries of the map.
      Returns:
      iterable collection of the map's entries