Write a program (C++) that implements a dynamically hashed symbol table. You are free to choose whichever hash function you like that returns the bitmask of the size of 32 bits for each word hashed. You will be graded on its quality. Your program should do the following:
1. Take the following two parameters from the command line: the name of the file to take the keys from *file_name*, the number of keys to hash *number_keys* and the size of the bucket *bucket_size*. The program should be named *as1*. The keys are represented as words. For this assignment you can assume that the size of a word is limited to 20 characters.
2. A file containing over 10000 English words used by the gnu *ispell* program is posted on the Course web site. You can use this file to test your program. The second data set from the Horowitz book is also provided. You can use it for debugging.
2. Read keys from the file *file_name* sequentially. Enter each of the keys into the extendible hash table. Start with the table containing one key only, and grow to the number of keys to hash identified by the user: *number_keys.*
3. Set up the bucket size to 128 bytes, select an algorithm to index words inside this bucket, and select a good hash function to hash a word into the 32 bitmask (32 bits).
4. Re-read the set of keys of the specified size from the file, and look up each one in the hash table. Compute and print the average number of comparisons required to look up a word in the input file.
Type and submit an **electronic report** (1-2 pages) that includes the following:
A brief description of your hash function and justification of your choice.
A brief description of your indexing method (within a bucket) and justification of your choice.
A brief description of the dynamic hashing method, including any specific decisions during its implementation.
The average number of probes required to look up keys in a large data file (say, one million words in the file).
Analysis of how changing the bucket size would influence the number of probes required to look up keys and influence efficiency of hashing. (Note: Bonus points for detailed experimental analysis).
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):
a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.
b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.
3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).
Unix or Windows