View source for Concurrent Hash Table Assignment


=Motivation=
[[File:Hash_table_5_0_1_1_1_1_1_LL.svg|frame|[https://commons.wikimedia.org/wiki/File:Hash_table_5_0_1_1_1_1_1_LL.svg mediawiki hash table image]]]

For this exercise you will create a thread safe data structure.  You have previously created a [[Hashtable|non-thread safe HashTable]].  Now, with the help of multiple  [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html ReentrantReadWriteLocks] you will create a thread safe Map that both deals with contention and allows simultaneous gets. 

=Previous Exercise=
You will directly [[Hashtable#DefaultEntry.3CK.2CV.3E|DefaultEntry]] and [[Hashtable#HashUtils|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#HashTable|HashTable]].

=Java Utilities To Investigate=
{{LockWithLockMethodsLinks}}

{{ReadWriteLockWithMethodsLinks}}

class {{ReentrantReadWriteLockLink}} implements {{ReadWriteLockLink}}

=Code To Implement=
==ConcurrentHashTable==
{{CodeToImplement|ConcurrentHashTable|constructor<br/>hashFunction<br/>chains<br/>readWriteLocks<br/>chainIndexOf<br/>lockIndexOfChainIndex<br/>entryOf<br/>put<br/>get<br/>computeIfAbsent<br/>compute|hashtable.concurrent.exercise}}

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==
{{Sequential|public ConcurrentHashTable(int chainCount, ToIntFunction<K> hashFunction)}}

Much like the constructor from the not-thread safe HashTable, with the added responsibility of creating the {{ReadWriteLockLink}}s.

For this assignment you will create one instance of {{ReadWriteLockLink}} for each chain.  Each ReadWriteLock will be responsible for the chain with the same array index.

{{LifeAfter231|<br/>In this assignment we will simply allocate a ReadWriteLock for each chain.  Each lock will be responsible for the chain with the same array index.<br/>However, it is reasonable in some circumstances to have more than one chain protected by a single lock.  For example, if you had 1024 chains and only wanted to allocate 16 Locks, each Lock would be responsible for 1024/16 (64) chains.  The reduced cost in allocating Locks might be worth if you were willing to accept that tasks on separate chains would block if they were protected by the same lock.<br/>Again, for this assignment, we will simply allocate a ReadWriteLock for each chain.}}

==support methods==
Many of these methods are equivalent to their counterparts in the [[Hash_Table_Assignment|HashTable assignment]].  One exception is that chainOf(key) is replaced by chainIndexOf(key) due to the fact that the chain index is used for both the chain and also the ReadWriteLock protecting it..

These support methods must remain unprotected by any Lock (either intrinsic via synchronized or explicit via a Lock).  Ensuring thread-safety will be the responsibility of the public methods: put, get, computeIfAbsent, and compute.

===hashFunction()===
akin to the [[Hash_Table_Assignment#hashFunction.28.29|HashTable version of hashFunction()]].
===chains()===
akin to the [[Hash_Table_Assignment#chains.28.29|HashTable version of chains()]].
===readWriteLocks()===
A standard getter for your private instance variable of ReadWriteLock's

===chainIndexOf(key)===
One of the methods you built on [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/hash/exercise/HashUtils.html HashUtils] should be useful here.

Note: In the prior [[Hash_Table_Assignment|NotThreadSafeHashTable]] exercise, we only needed the chain for a particular key so directly asking for it via one of the [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/hash/exercise/HashUtils.html HashUtils] methods made sense.  Here we will need the index of the chain for both the chain and for determining the lock responsible for protecting that chain, so we ask for the index of the chain in its array.

===lockIndexOfChainIndex(chainIndex)===
As previously stated we will be creating a ReadWriteLock for each chain, so lockIndexOfChainIndex(chainIndex) simply returns the chainIndex.

provided:
<syntaxhighlight lang="java">
private int lockIndexOfChainIndex(int chainIndex) {
	return chainIndex;
}
</syntaxhighlight>

===entryOf(chain, key)===
akin to the [[Hash_Table_Assignment#entryOf.28chain.2C_key.29|HashTable version of entryOf(chain, key)]].

==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, [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#lock-- lock()] or [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#tryLock-- tryLock()], is the appropriate one to use for creating a thread safe data structure such as this?

<spoiler show="spoiler" hide="spoiler">[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#lock-- lock()]</spoiler>

Whenever you acquire a lock, but sure to leverage [https://docs.oracle.com/javase/tutorial/essential/exceptions/finally.html try finally] and [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#unlock-- unlock()] the lock within the finally block.

{{ 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. }}

{{ warning | Do '''NOT''' call any of your public methods from eachother.  Simply use your unprotected utility methods. }}

{{ 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. }}

===put(key, value)===
{{ThreadSafe|public V put(K key, V value)}}

akin to the [[Hash_Table_Assignment#put.28key.2C_value.29|HashTable version of put(key, value)]] with the critical add requirement of thread-safety.

===get(key)===
{{ThreadSafe|public V get(K key)}}

akin to the [[Hash_Table_Assignment#get.28key.29|HashTable version of get(key)]] with the critical add requirement of thread-safety.

===computeIfAbsent(key, mappingFunction)===
{{ThreadSafe|public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)}}

akin to the [[Hash_Table_Assignment#computeIfAbsent.put.28key.2C_mappingFunction.29|HashTable version of computeIfAbsent(key, mappingFunction)]] with the critical add requirement of thread-safety.

===compute(key, remappingFunction)===
{{ThreadSafe|public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)}}

akin to the [[Hash_Table_Assignment#compute.put.28key.2C_remappingFunction.29|HashTable version of compute(key, remappingFunction)]] with the critical add requirement of thread-safety.

=Testing Your Solution=
{{TestSuite|__ConcurrentHashTableTestSuite|hashtable.concurrent.exercise}}

=Pledge, Acknowledgments, Citations=
{{Pledge|exercise-concurrent-hash-table}}