Hash Maps/AbstractHashMap

Notes

To recap, here is how these classes are organized:

• Map is an interface class that defines the public interfaces that any Map data container must implement
• AbstractMap is an abstract class that does the following:
  • Define a map item (utility) class
  • This is designed to take a K,V key value pair
  • Also defines four more classes:
  • Two Iterators and two Iterables - the key and value Iterator and Iterable classes.

itemSet() method:

• The itemSet() method returns an iterator over the set of all MapItems
• itemSet() returns an iterator over MapItem types, so keySet() and valueSet() both utilize this and unwrap only the key or value from the MapItem object.
• We aren't defining itemSet anywhere in this class - just using it. Then we implement it as an abstract method, requiring concrete classes to implement it.
• itemSet must be defined in our concrete class
• This means that eventually our concrete class will have three total Iterators and three total Iterables - two Iterators and two Iterables defined in the abstract class, for the keys and values, and one Iterator and one Iterable defined in the concrete class, when we know more about how the actual hash map is being implemented under the hood.

More iterators vs iterables:

• Iterable just says, this thing can be used with for-each syntax (it has a specific way to return an iterator). It is part of the core language.
• Iterator has to be defined for each container.

Exceptions:

• NoSuchElementException
• UnsupportedOperationException
• Don't forget to check for size!
• Especially if you are not wraapping someone else's iterator

Ordering of class declaration and undeclared class declarations

• I could not use MapItem class undefined in the Map interface (most generic of all)
• MapItem class was actually protected and lived in AbstractMap class
• Therefore, we had to hold off declaring an abstract MapItem iterator until the AbstractMap class, not the Map interface

Code

Link to code on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/hash/AbstractHashMap.java

We start with the class declaration, where we take two generic types (K for key and V for value), and require key types to be comparable.

import java.util.*;

/** Abstract Hash Map implementation.
 *
 * This implements the Map interface and extends the 
 * AbstractMap abstract base type.
 *
 * The AbstractHashMap provides mathematical support 
 * for hash compression function, 
 * 
 * The AbstractHashMap also provides support for automatically
 * resizing the hash table.
 */
public abstract class AbstractHashMap<K extends Comparable<K>,V> 
	extends AbstractMap<K,V> { 

Protected class fields:

	// Fields:
	protected int size; // number of elements in map
	protected int capacity; // capacity of map
	protected int prime; // prime number
	protected int shift, scale; // hash function parameters

The constructors:

	// Public constructors:
	/** Default constructor, initializes map with capacity 11. */
	public AbstractHashMap() { 
		// Default constructor starts with capacity of 11
		this(11); 
	} 
	/** Constructor taking initial capacity of map. */
	public AbstractHashMap(int cap) { 
		// Constructor taking only init capacity as arg
		this(cap, 1789); 
	}
	/** Constructor taking initial capacity of map and prime p for hash function. */
	public AbstractHashMap(int cap, int p) { 
		prime = p;
		capacity = cap;
		size = 0;

		// Initialize the hash function parameter values
		Random r = new Random();
		scale = r.nextInt(prime-1)+1;
		shift = r.nextInt(prime);

		// Create the initial hash table
		createTable();
	}

Here is the list of methods:

	// Public methods:
	/** Returns the number of elements in this map. */
	public int size() { return size; }

	/** Public method to get the value corresponding to this key. */
	public V get(K key) {
		return bucketGet( hashValue(key), key );
	}
	/** Public (abstract) method to remove the item with this key from the map. */
	public abstract V remove(K key);

	/** Public (abstract) method to put the item with this key and value into the map. */
	public abstract void put(K key, V value);

Now, the protected methods:

	// Protected methods:
	/** Compute the hash code for a key object. */
	protected int hashValue(K k) { 
		// Universal (MAD) hash function:
		//       ( (ax + b) mod p ) mod n
		int h = (int)((Math.abs(k.hashCode()*scale + shift) % prime) % capacity);
		return h; 
	}

	/** Create a new hash table with capacity this.capacity. */
	protected abstract void createTable();

	/** Get the value corresponding to this key, and look in the bucket corresponding to this hash code. */
	protected abstract V bucketGet(int hashCode, K key);
	
	/** Remove the value corresponding to this key from the bucket corresponding to this hash code. */
	protected abstract V bucketRemove(int hashCode, K key);
	
	/** Put the key-value pair into the map bucket corresponding to this hash code. */
	protected abstract void bucketPut(int hashCode, K key, V value);

}