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

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
readWriteLocks
chainIndexOf
lockIndexOfChainIndex
entryOf
put
get
computeIfAbsent
compute
package: hashtable.concurrent.exercise
source folder: student/src/main/java

None of the methods should be protected by synchronized. You will use the correct ReadWriteLock in the correct mode (Read or Write) to keep your ConcurrentHashTable thread-safe.

constructor

method: public ConcurrentHashTable(int chainCount, Supplier<Collection<Entry<K, V>>> chainCreator, BiFunction<K, V, Entry<K, V>> entryCreator, ToIntFunction<K> hashFunction) Sequential.svg (sequential implementation only)

Much like the constructor from the not-thread safe HashTable, with the added responsibility of creating the ReadWriteLocks.

For this assignment you will create one instance ReadWriteLock for each chain.

Notepad-117597 640.png Life After 231 Note: a

support methods

These methods are to remain unprotected by any Lock (intrinsic via synchronized or explicit via a Lock). That will be the responsibility of the public methods: put, get, computeIfAbsent, and compute.

hashFunction()

akin to the HashTable version.

entryCreator()

akin to the HashTable version.

createEntry(key,value)

akin to the HashTable version.

chains()

akin to the HashTable version.

readWriteLocks()

new to this exercise

chainIndexOf(key)

new to this exercise but similar to functionality of HashTable

lockIndexOfChainIndex(chainIndex)

provided:

private int lockIndexOfChainIndex(int chainIndex) {
	return chainIndex;
}

entryOf(chain, key)

akin to the HashTable version.

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.

Attention niels epting.svg Warning: Do NOT call get() from put, computeIfAbsent, or compute. It will result in a nonintuitive error. entryOf(chain, key) gives you everything you need.
Attention niels epting.svg Warning: Do NOT call any of your public methods from eachother. Simply use your unprotected utility methods.
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.

get(key)

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

spec

put(key, value)

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

spec

computeIfAbsent(key, mappingFunction)

method: public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) Sequential.svg (thread-safe required)

spec

compute(key, remappingFunction)

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

spec


Testing Your Solution

class: __ConcurrentHashTableTestSuite.java Junit.png
package: hashtable.concurrent.exercise
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: exercise-concurrent-hash-table-pledge-acknowledgments-citations.txt

More info about the Honor Pledge