Package com.zybooks.dsaj.map

Class ChainHashMap<K,V>

java.lang.Object
com.zybooks.dsaj.map.AbstractMap<K,V>
com.zybooks.dsaj.map.AbstractHashMap<K,V>
com.zybooks.dsaj.map.ChainHashMap<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 ChainHashMap<K,V> extends AbstractHashMap<K,V>
Map implementation using hash table with separate chaining.

  • 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
    ChainHashMap()
    Creates a hash table with capacity 17 and prime number 109345121.
    ChainHashMap(int cap)
    Creates a hash table with given capacity and prime number 109345121.
    ChainHashMap(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

    • ChainHashMap

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

    • ChainHashMap

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

    • ChainHashMap

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