Concurrent Hash Table Assignment

From CSE231 Wiki
Jump to navigation Jump to search

Motivation

For this exercise you will create a thread safe data structure. You have previously created a non-thread safe HashTable. Now, with the help of multiple ReentrantReadWriteLocks you will create a thread safe Map that both deals with contention and allows simultaneous gets.

Previous Exercise

You will directly use DefaultCollectionCreator, DefaultEntry, DefaultEntryCreator, DefaultHashFunction, and HashUtils from the Hashtable exercise.

Further, you will be implementing thread-safe versions of put, get, computeIfAbsent, and compute methods (along with many of the utility methods) from HashTable.

Code To Implement

ConcurrentHashTable

class: ConcurrentHashTable.java Java.png
methods: constructor
hashFunction
entryCreator
createEntry
chains
chainIndexOf
chainOf
entryOf
put
get
computeIfAbsent
compute
package: hashtable.concurrent.exercise
source folder: student/src/main/java

constructor

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

bucketCount can be treated as a hint of how many entries the Map can expect to receive.

private support methods

Circle-information.svg Tip:Use HashUtils.toIndex(key,N)

getBucket(key)

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

getLock(key)

method: private ReadWriteLock getLock(Object key) Sequential.svg (sequential implementation only)

getEntry(bucket, key)

method: private static <K, V> Optional<Entry<K, V>> getEntry(List<Entry<K, V>> bucket, Object key) Sequential.svg (sequential implementation only)

Refer to Optional<T> Class documentation.

public methods

Be sure to make each of these methods thread safe by acquiring the appropriate (read or write) lock for the appropriate bucket.

Which method, lock() or tryLock(), is the appropriate one to use for creating a thread safe data structure such as this?

Whenever you acquire a lock, but sure to leverage try finally and unlock() the lock within the finally block.

method: public V get(Object key) Sequential.svg (thread-safe required)

spec

method: public V put(K key, V value) Sequential.svg (thread-safe required)

spec

method: public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) Sequential.svg (thread-safe required)

spec

advice

Attention niels epting.svg Warning: Do NOT call get() from compute(). It will result in a nonintuitive error. getEntry(bucket, key) gives you everything you need.
Attention niels epting.svg Warning: Do NOT call put() from compute() either. Just do the work within the compute method.
Circle-information.svg Tip: Be sure to make your ConcurrentBucketHashMap thread-safe. If any code is going to access shared mutable data, it needs to do so in a thread-safe manner.