Package com.zybooks.dsaj.map

Class AbstractHashMap<K,V>

java.lang.Object
com.zybooks.dsaj.map.AbstractMap<K,V>
com.zybooks.dsaj.map.AbstractHashMap<K,V>
Type Parameters:
K - The key type (keys must be unique and hashable)
V - The value type
All Implemented Interfaces:
Map<K,V>
Direct Known Subclasses:
ChainHashMap, ProbeHashMap
public abstract class AbstractHashMap<K,V> extends AbstractMap<K,V>
An abstract base class supporting Map implementations that use hash tables with MAD compression. The base class provides the following means of support: 1) Support for calculating hash values with MAD compression 2) Support for resizing table when load factor reaches 1/2 Subclass is responsible for providing abstract methods: createTable(), bucketGet(h,k), bucketPut(h,k,v), bucketRemove(h,k), and entrySet() and for accurately maintaining the protected member, n, to reflect changes within bucketPut and bucketRemove.

  • Nested Class Summary

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

    AbstractMap.MapEntry<K,V>

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    capacity
    length of the table
    protected int
    n
    number of entries in the dictionary

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    protected abstract V
    bucketGet(int h, K k)
    Returns value associated with key k in bucket with hash value h.
    protected abstract 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 abstract 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 abstract void
    createTable()
    Creates an empty table having length equal to current capacity.
    V
    get(K key)
    Returns the value associated with the specified key, or null if no such entry exists.
    V
    put(K key, V value)
    Associates the given value with the given key.
    V
    remove(K key)
    Removes the entry with the specified key, if present, and returns its associated value.
    int
    size()
    Tests whether the map is empty.

    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

    Methods inherited from interface com.zybooks.dsaj.map.Map

    entrySet

  • Field Details

    • n

      protected int n
      number of entries in the dictionary

    • capacity

      protected int capacity
      length of the table

  • Constructor Details

    • AbstractHashMap

      public AbstractHashMap(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

    • AbstractHashMap

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

    • AbstractHashMap

      public AbstractHashMap()
      Creates a hash table with capacity 17 and prime number 109345121.

  • Method Details

    • size

      public int size()
      Tests whether the map is empty.
      Returns:
      true if the map is empty, false otherwise

    • get

      public V get(K key)
      Returns the value associated with the specified key, or null if no such entry exists.
      Parameters:
      key - the key whose associated value is to be returned
      Returns:
      the associated value, or null if no such entry exists

    • remove

      public V remove(K key)
      Removes the entry with the specified key, if present, and returns its associated value. Otherwise does nothing and returns null.
      Parameters:
      key - the key whose entry is to be removed from the map
      Returns:
      the previous value associated with the removed key, or null if no such entry exists

    • put

      public V put(K key, V value)
      Associates the given value with the given key. If an entry with the key was already in the map, this replaced the previous value with the new one and returns the old value. Otherwise, a new entry is added and null is returned.
      Parameters:
      key - key with which the specified value is to be associated
      value - value to be associated with the specified key
      Returns:
      the previous value associated with the key (or null, if no such entry)

    • createTable

      protected abstract void createTable()
      Creates an empty table having length equal to current capacity.

    • bucketGet

      protected abstract 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.
      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 abstract 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.
      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 abstract V bucketRemove(int h, K k)
      Removes entry having key k from bucket with hash value h, returning the previously associated value, if found.
      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)