[Solved]Java Programming Lab Using Array Linked Lists Implement Hash Table Hash Table Data Structu Q37200705

JAVA PROGRAMMING

In this lab, you will be using an array of linkedlists to implement a hash table.  
A hashtable is a data structure in which the location of an itemis determined directly as a function of the item rather than by asequence of trial-and-error comparisons and is used when fastsearching is needed.  Ideally, search time is O(1); i.e., itis constant and independent of the number of items to be searched. Here we will use the method known as chaining, inwhich the hash table is implemented using an array of linkedlists.
When an item is to be inserted into the table, a hashingfunction h is applied to the item to determine where it is tobe placed in the table; for example, a common one is
h(item) = item % table-size
where the table-size is usually taken to be a prime number (toscatter (“hash”) the items throughout the table.  Fornon-numeric items, numeric codes e,g., ASCII are used.  Thelinked list at location h(item) is searched for the item.  Ifit is not found, the item is inserted into the linked list at thislocation.

Design a HashTable class for processing hash tables.  Use asmall prime number such as 11 or 13 for the table size.  Twoof the basic operations it must provide are:
1.  Insert an item into the hash table as just described. It doesn’t matter where in the linked list it isinserted.
2.  Display each index in the hash table and a list of all theitems stored at that location.
For this particular problem, the hash table is to store strings anduse the following hash function:
h(str) = (sum of the ASCII codes of the first 3 characters of str)% table_size.
For strings with fewer than 3 characters, just use whatevercharacters there are in the string.
Assignment:  Use an array of linked lists to implement a hashtable.  You may use the linklist that we learned in thisChapter.    
Write a driver program to test your class.  It should readseveral strings, storing each in the hash table.  After allthe strings are input, it should display the hash table by listingthe indices and for each index, a list of all the words in thelinked list at that location (sort of like the diagramabove).
After you have thoroughly tested your class, then use it to processthe strings in the piece of text(read them from fileclab15.txt):
DEAR MARLIN
THE AARDVARKS AND THE CAMELS WERE MISTAKENLY SHIPPED TO THEAZORES
SORRY ABOUT THAT   
SINCERELY   JIM
PS  ANTS AND BATS AND COWS AND CATS ARE ANIMALS
COWS ARE BIG BUT ANTS ARE SMALL AND BATS AND CATS ARE INBETWEEN
Submission: Follow our class coding standard to complete this lab,check out for credit.

Expert Answer

---

Answer to JAVA PROGRAMMING In this lab, you will be using an array of linked lists to implement a hash table. A hash table is a d… . . .