**Introduction**
The purpose of this assignment is to investigate the dynamic hashing algorithm. A hash table uses a hash function to map keys to table addresses. If the keys are character string identifiers, then there is a very large number of possible keys, much greater than the size of a hash table. The hash function maps the large number of possible strings into table addresses. A good hash function spreads out the entries in the table, avoiding collision (keys mapping to the same table address) as much as possible. When the entries are spread out, the hash function can be used to quickly enter and find keys in the table, in about O(1) time. The dynamic (extendible) hashing allows increasing or decreasing the size of the data dynamically, allocating only requires space for hash table.
**Program**
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.
## Deliverables
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).
## Platform
Unix,WIndows ,c++