Hash Table

implement the chained hash tables. The key used for the operations specified as follows will be last names in string format, i.e., the American last names in the attached file. Assume a string consists of k characters. s[i] represents the i-th character from left to right. We will use the hash code function “sdbm” for strings: ( [login to view URL] 7eoz/[login to view URL] ) for chaining hash table. The actual hash function is H(s) = sdbm(s)modM . N is the size of the hash table. N is better chosen to be a prime number between n and 2n, where n is the total number of strings. Here, we chose N to be 88001. If you want to try a different hash table size, you can choose N to be 87991.

In the beginning of your main() function, you should create a hash table. Then you should open the input file, read the file that contain the strings of last names, and insert them into the the hash table using the specified hash code function. You should start with an empty Hash Table while inserting all the strings into the hash table. After all the strings are inserted into the the hash table, print the number of occupied buckets in the hash table, the number of empty hash table buckets, the load factor, and the length of the longest linked list of all the hash table buckets in the hash table to the screen.

You then should implement a user interface (MENU) that supports the following operations:

• Insert new Entry: prompt user for a last name, insert it into the Hash Table. Your implemen- tation should detect the insertion of a duplicated last name and reject the insertion. Display information telling whether or not the insertion is successful; if successful, display the bucket number that the last name is inserted.

• Delete an Entry: Ask the user for a last name and delete it from the Hash Table. Display information telling whether or not the deletion is successful. If successful, display the last name and the corresponding bucket number. Display information telling the delete is not successful, i.e., last name: not found.

• Search: Search for a last name given via the keyboard. If successful, display the last name and the bucket number that the last name is found. If not found, display information telling the search is not successful, i.e., last name: not found.

• Logfile: Write a formatted display of the hash table to the log file. The display should list each bucket of the Hash Table, indicating that the bucket is empty, or showing the key value.

• Quit.

3 Hash code function - sdbm

The hash code function sdbm is attached here too. Again, you are encouraged to check the original website ([login to view URL] 7eoz/[login to view URL]) for the hash code function.

sdbm: This algorithm was created for sdbm (a public-domain re-implementation of ndbm) database library. It was found to do well in scrambling bits, causing better distribution of the keys and fewer splits. It also happens to be a good general hashing function with good distribution. The actual function is hash(i) = hash(i − 1) ∗ 65599 + str[i]; what is included below is the faster version used in gawk. [there is even a faster, duff-device version] the magic constant 65599 was picked out of thin air while experimenting with different constants, and turns out to be a prime. this is one of the algorithms used in berkeley db (see sleepycat) and elsewhere.

• Pseudo code:

unsigned long sdbm(char *str)

{

unsigned long hash = 0;

int c;

while (c = *str++)

hash = c + (hash << 6) + (hash << 16) - hash; return hash;

}

Kemahiran: Pengaturcaraan C++

Lihat lagi: linux shell search logfile count message, search logfile windows service, tsql stored procedure table return, search engine write knuth morris pratt, java keyboard search box, vbscript search excel write text file, dictionary lookup binary search hash table, hash table implementation binary search tree, hash table using search tree, hash table search tree java, implementation hash table using binary search tree java, hash table binary search tree java, write program demonstrate hash table, hash table binary search tree, implement hash table with binary search tree c++, how to implement hash table with balanced binary search tree, implement hash table with binary search tree java, implement hash table with binary search tree, in what situation would you want to use between hash table and binary search tree ?

ID Projek: #28384992