Hashtable

From CSE231 Wiki
Revision as of 12:13, 15 February 2020 by Cosgroved (talk | contribs) (put(key, value))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Motivation

We gain experience with interfaces and classes. In addition we will deal with generic types.

We implement our own @NotThreadSafe Map class. Later in the semester we will implement a @ThreadSafe version of a Map.

In the creation of our Map class, we will gain experience with hashing which we will leverage throughout the semester.

Background

Mistakes To Avoid

Attention niels epting.svg Warning: Do NOT use == when comparing Objects (except when comparing to null). Use Objects.equals(a,b).
Attention niels epting.svg Warning: Do NOT use % which can return a negative number. Use Math.floorMod(x,y).
Attention niels epting.svg Warning: Do NOT parallelize.
Attention niels epting.svg Warning: Do NOT simply remove and add for put on a Map. Look for the entry and set its value if you find it. Otherwise add it.
Circle-information.svg Tip: It is good practice to declare variables, parameters, and fields to be of the least specific type possible (but no less specific :). This is commonly an interface.
Attention niels epting.svg Warning: A common mistake we see is students attempting to create an instance of an interface when they need to create an instance of a class (e.g. List<String> states = new LinkedList<>();).

Code to Implement

HashUtils

class: HashUtils.java Java.png
methods: toIndex
package: hash.studio
source folder: src/main/java

toIndex(key,maxExclusive)

HashTableMap

HashTableMap will use an entry’s key to place an entry into one of several buckets.

In short, these buckets exist to cut down the runtime of searching for entries within the map, as it is much quicker to search 1/total number of buckets than one large bucket which contains every entry.

hash table on wikipedia

In this class, you will use the entry’s key’s hashcode to determine which of the buckets it should fall into. In order to calculate the index of the bucket that the entry belongs in, we will make use of the hash function, which in turn uses Math.floorMod to calculate a modulo (remainder or % in Java) based on the number of buckets and the key’s hashcode.

reference material: Concept of Hashing

A Map (also sometimes referred to as a Dictionary or a Hashtable) is an abstract data structure which has the capabilities of associating a value with a key: map.put(key, value), looking up the associated value with a key: map.get(key), and removing map.remove(key).

The standard Java Collections Framework Map provides a number of other nice methods, but put, get, and remove are the core of any Map in any programming language.

Since your class will implement Map<K,V>, it must meet the specification of that interface. The links to the javadocs are provided for the details of each methods spec.

The standard interface for a key value pair is Map's Entry with the critical methods:

  • K getKey()
  • V getValue()
  • V setValue(V value)

We have provided an implementation of Entry for you called KeyMutableValuePair<K,V>.

Attention niels epting.svg Warning: Note the specifications of the return values.
class: HashTableMap.java Java.png
methods: constructor
getBucketIndex
getBucketFor
size
put
remove
get
package: hashtable.studio
source folder: src/main/java

Constructor: HashTableMap(capacity, collectionSupplier)

method: public HashTableMap(int capacity, Supplier<Collection<Entry<K, V>>> collectionSupplier) Sequential.svg (sequential implementation only)

Implementing the constructor has a couple of tricky parts.

Parameterized Type Array Tip

First, you will encounter a much dreaded problem in Java. One cannot instantiate a new generic array. While there is a reason for this limitation, it is still frustrating.

So while you might think you should enter:

buckets = new Collection<Entry<K, V>>[capacity]; // NOTE: this will not compile

the error reported says it all "Cannot create a generic array of Collection<Map.Entry<K,V>>".

You must instead create the array without the generic type parameter:

buckets = new Collection[capacity];

This results in a warning which the @SuppressWarnings("unchecked") annotation we added to the constructor takes care of.

Collection Supplier

Second, there is what to make of the collectionSupplier parameter. When creating a bucket for each slot in the array you should invoke the collectionSupplier's get() method instead of directly creating instances of java.util.LinkedList, for example. This allows us to gain some experience with Supplier that will hopefully pay off later on in the semester. Further, it allows the tests to enforce some good practices in your implementation.

getBucketIndex(key)

method: private int getBucketIndex(Object key) Sequential.svg (sequential implementation only)

For a given key return the index into the array of buckets. The correct implementation should leverage the key's hash code to generate a valid index of the bucket array.

Circle-information.svg Tip: You should have just built a utility method which should be useful here.

getBucketFor(key)

method: private Collection<Entry<K, V>> getBucketFor(Object key) Sequential.svg (sequential implementation only)

getBucketIndex(key) returns the index. getBucketFor(key) returns the bucket at that index.

size()

method: public int size() Sequential.svg (sequential implementation only)

size() spec

put(key, value)

method: public V put(K key, V value) Sequential.svg (sequential implementation only)

put(key,value) spec

Circle-information.svg Tip: Do NOT implement put as a remove followed by an add. While will produce the correct state, it is undesirable. First look for the key and set its value if you find it before resorting to adding a new entry when you cannot find a previous entry with the key.
Circle-information.svg Tip: Only a single bucket's collection should be iterated over once with a single for-each loop.
Circle-information.svg Tip: We have provided an implementation of Entry<K,V>: KeyMutableValuePair<K,V>.

remove(key)

method: public V remove(Object key) Sequential.svg (sequential implementation only)

remove(key) spec

Attention niels epting.svg Warning: For an efficient solution (and to avoid a possible ConcurrentModificationException) you will want to use the bucket's iterator directly and leverage its remove method.
Circle-information.svg Tip: Only a single bucket's collection should be iterated over once via the iterator() method on appropriate bucket.

get(key)

method: public V get(Object key) Sequential.svg (sequential implementation only)

get(key) spec

Circle-information.svg Tip: Only a single bucket's collection should be iterated over once with a single for-each loop.

Testing Your Solution

Correctness

class: HashUtilsToIndexTestSuite.java Junit.png
package: hash.studio
source folder: src/test/java
class: HashTableMapTestSuite.java Junit.png
package: hashtable.studio
source folder: src/test/java