Thread Safe Hashing
Budget: $10 – $30 USD
Please implement parallel open Hashing using Java thread (not preferred). C/C++
and pthread library, or Go. Your program will run with input (one per line) read
from stdin in the order of 1) manual or random mode, 2) number of threads to run
concurrently, 3) number of operations (put, get, or delete chosen randomly as
described below) a thread needs to handle, and 4) lines of “song name” and
“socket”.
The input to the hash function is a text string (i.e., the song’s name), and the output
of the hash function is an unsigned integer ranged from 0 to table size n. The input
string is divided into 4-byte chucks (fill with zeros if the last chunk is not full),
reverse the bits for all odd numbered chunks, exclusive OR of all those chunks
together, the result value is then mod by the table size to get hash index, and
return the index. For example, the input is “Listen to the music”, which is divided
into 5 chunks: “List”, “en t”, “o th”, “e mu”, and “sic”. Those 5 chunks are
represented in hex as 0x4C697374, 0x656E2074, 0x6F207468, 0x65206D75, and
0x73696300. Then reverse the bits of all odd chunks and return the exclusive OR of
all chunks: 0x2ECE9632 ^ 0x656E2074 ^ 0x162E04F6 ^ 0x65206D75 ^ 0x00C696CE.
The operations will be decided randomly for the random mode (the 3rd input
parameter) with average of 70% for get, 20% for put, and 10% for delete using
random number generated by calling random() in standard math library. For
manual mode, you program should ask user to enter the put/get/delete “song
name” and/or “socket” or quit manually and verify if output is correct for sequential
hashing. After manual mode works, try the random mode and make sure your
program works in parallel hashing.
• If the operation is put and the entry already in the hash table, output a warning
message (e.g., “<thread id>: put <song name> at <socket> already in the hash
table with index <index>”). Otherwise, output a message (e.g., “<thread id>:
put <song name> at <socket> in the hash table with index <index>”) and put
the song’s name and the socket into the hash table if the entry is not in the
hash table using the hash function defined above. If the hash collides, use open
hash to resolve collision by a linked list.
• If the operation is get, ignore the socket and only check if the song’s name is in
the hash table. If the song’s name is not in the hash table, output a warning
message (e.g., “<thread id>: get <song name> is not in the hash table”).
Otherwise, output a message (e.g., “ <thread id>: get <song name> can be
download from [<socket>]”), where the [<socket>] is the list of sockets for the
song’ name in the hash table.
• If the operation is delete and the <song name> and <socket> is not in the hash,
output a warning message (e.g., “<thread id>: delete <song name> at <socket>
is not in the hash table”). Otherwise, output a message (e.g., <thread id>:
delete <song name> at <socket> from the hash table”), and remove the entry
from the hash table.
The initial default table size is 7 (the closest prime number around 23
). If the total
numbers of entries is greater than roughly 110% of the table size, you need to do
rehash by doubling the table size and make the table size a closest prime number
(e.g., 17 is the closest prime for 24
). If the total numbers of the entries is less than
roughly 40% of the table size, you need to do rehash by half the table size to the
closest prime number. You can simply make table sizes as [7, 17, 31, 61, 127, …].
Each thread processes the list of <song name> and <socket> one by one for number
of operations (the second input number) times, then exit. If the number of
operations is more than the number of the name list, then the thread needs to
cycle the name list.
Example input for manual mode:
Manual
Example input for random mode:
Random
3
20
Listen to the music, http://foo.com:54321
Time to say goodbye, http://bar.com:12345
Sound of music, http://xyz.com:40000
Please find the attachments
and pthread library, or Go. Your program will run with input (one per line) read
from stdin in the order of 1) manual or random mode, 2) number of threads to run
concurrently, 3) number of operations (put, get, or delete chosen randomly as
described below) a thread needs to handle, and 4) lines of “song name” and
“socket”.
The input to the hash function is a text string (i.e., the song’s name), and the output
of the hash function is an unsigned integer ranged from 0 to table size n. The input
string is divided into 4-byte chucks (fill with zeros if the last chunk is not full),
reverse the bits for all odd numbered chunks, exclusive OR of all those chunks
together, the result value is then mod by the table size to get hash index, and
return the index. For example, the input is “Listen to the music”, which is divided
into 5 chunks: “List”, “en t”, “o th”, “e mu”, and “sic”. Those 5 chunks are
represented in hex as 0x4C697374, 0x656E2074, 0x6F207468, 0x65206D75, and
0x73696300. Then reverse the bits of all odd chunks and return the exclusive OR of
all chunks: 0x2ECE9632 ^ 0x656E2074 ^ 0x162E04F6 ^ 0x65206D75 ^ 0x00C696CE.
The operations will be decided randomly for the random mode (the 3rd input
parameter) with average of 70% for get, 20% for put, and 10% for delete using
random number generated by calling random() in standard math library. For
manual mode, you program should ask user to enter the put/get/delete “song
name” and/or “socket” or quit manually and verify if output is correct for sequential
hashing. After manual mode works, try the random mode and make sure your
program works in parallel hashing.
• If the operation is put and the entry already in the hash table, output a warning
message (e.g., “<thread id>: put <song name> at <socket> already in the hash
table with index <index>”). Otherwise, output a message (e.g., “<thread id>:
put <song name> at <socket> in the hash table with index <index>”) and put
the song’s name and the socket into the hash table if the entry is not in the
hash table using the hash function defined above. If the hash collides, use open
hash to resolve collision by a linked list.
• If the operation is get, ignore the socket and only check if the song’s name is in
the hash table. If the song’s name is not in the hash table, output a warning
message (e.g., “<thread id>: get <song name> is not in the hash table”).
Otherwise, output a message (e.g., “ <thread id>: get <song name> can be
download from [<socket>]”), where the [<socket>] is the list of sockets for the
song’ name in the hash table.
• If the operation is delete and the <song name> and <socket> is not in the hash,
output a warning message (e.g., “<thread id>: delete <song name> at <socket>
is not in the hash table”). Otherwise, output a message (e.g., <thread id>:
delete <song name> at <socket> from the hash table”), and remove the entry
from the hash table.
The initial default table size is 7 (the closest prime number around 23
). If the total
numbers of entries is greater than roughly 110% of the table size, you need to do
rehash by doubling the table size and make the table size a closest prime number
(e.g., 17 is the closest prime for 24
). If the total numbers of the entries is less than
roughly 40% of the table size, you need to do rehash by half the table size to the
closest prime number. You can simply make table sizes as [7, 17, 31, 61, 127, …].
Each thread processes the list of <song name> and <socket> one by one for number
of operations (the second input number) times, then exit. If the number of
operations is more than the number of the name list, then the thread needs to
cycle the name list.
Example input for manual mode:
Manual
Example input for random mode:
Random
3
20
Listen to the music, http://foo.com:54321
Time to say goodbye, http://bar.com:12345
Sound of music, http://xyz.com:40000
Please find the attachments