GroceryStore.java,DIYHashMap.javaIn this assignment you'll start by using Java's internal HashMap to solve a problem (Part 1), and then replace the use of the HashMap with your own hash table (Part 2). We will use linear probing to handle collisions.
In Part 1 our task is to read data from a file, store aspects of it in a Java HashMap, and then perform a calculation using the information in your filled HashMap.
The HashMap will be a variable prices that maps Strings to Doubles. The String keys will be a food (and its form) such as “Corn-Frozen” and the Double key will be a price per pound for that food.
After populating the HashMap we will use its data to calculate the total cost of a grocery cart using the price per pound of foods in an array.
Data file prices.csv Data about the foods and prices are provided in the prices.csv file which is formatted as follows:
FoodName,Form,RetailPrice,RetailPriceUnit,Yield,CupEquivalentSize,CupEquivalentUnit,CupEquivalentPriceThe data in this file was originally obtained from this USDA website. Not all the columns are needed here. To uniquely identify foods in our grocery store, we will create String keys from the FoodName and Form columns as FoodName-Form. For example, the FoodName Corn appears in three rows, but in different forms. So we will create three String keys: "Corn-Fresh", "Corn-Canned" and "Corn-Frozen". The value to associate with the keys is the RetailPrice, which is the price per pound (a Double).
Part 1A: Start by completing the GroceryStore constructor which should read the prices.csv file and create the prices map. (In Part 1 use Java’s built-in HashMap and then replace this with DIYHashMap in Part 2). See the starter code from Homework 8 for an example of how to read a file line-by-line. The packages you need to read a file and handle a FileNotFoundException are already imported in GroceryStore.java. When processing a line, split it at the commas (,) and then create keys using the format described above. You can use Double.valueOf to extract the RetailPrice.
Part 1B: Next, complete the calculateTotal method which uses two arrays: (1) food names (in the same format described above) and (2) the weight of each food. This method will return the total price of all the items in cents. Cents should be rounded down to get to an integer. For example, for the cart with items = {"Kale-Frozen", "Kidney beans-Dried", "Butternut squash-Fresh", "Mangoes-Fresh", "Grapefruit-Fresh", "Cranberries-Dried", "Pomegranate-Fresh", "Clementines-Fresh"} and weights = {0.8, 0.25, 2, 1.3, 1.6, 0.75, 1.0, 2.5}, the price comes out to 19.31007 and we should return 1931. The total cost of all items in the store using a weight of 1 pound is 289.9496, but we would return 28994.
DIYHashMapImplement your own hash table in DIYHashMap.java. This hash table should use open addressing with linear probing to insert and search for items in the table, so please review page 8 in the Lecture 11T slides. Use the division method for your hash function: key.hashCode() % capacity(). Start with an initial capacity of 8 and double the capacity of the table when the load factor is > 0.5. You are free to store key-value pairs in the table as you wish. For example, you could define separate arrays (of type Object) to hold the keys and the values. Or, you could define a subclass such as Pair that would contain a key of type K and a value of type V; then the HashMap would be stored as a single array (of type Object) where the entries are Pairs (similar to the Nodes we used in Lecture 11T).
The DIYHashMap class should provide the following public methods:
public DIYHashMap(): default constructor, which initializes a hash table with an initial capacity of 8 slots.public int capacity(): returns the total number of slots in the hash table, whether they are filled or not. This is not in the HashMap specification but is needed for testing.public V get(K key): returns the value associated with a particular key (null if the key is not in the hash table).public K getKey(int i): retrieves the key at index i in the table. For example, if the table keys are [null, null, 2, null, 12, null, null, 15], then getKey(0) would return null, getKey(3) returns null, and getKey(4) returns 12. This is not in the HashMap specification but is needed for testing.public void put(K key, V value): adds a key-value pair to the hash table, possibly updating the value if the key already exists in the table. You can modify the signature to return the previously mapped value similar to what Oracle says the HashMap put method should be, but void is okay for our purposes.public int size(): returns the number of key-value pairs in the hash table.Remember you can define private helper methods to be called by the public methods. You may find it helpful to have a private version of getKey and put so you can add a parameter for the current table (eg, for use during rehashing).
You will want to define methods private void rehash() and private int hash(K key, int m).
It may be helpful to define a method such as private int find(Object[] table, K key, int index) that could be used by both get and put (or the private versions of them). The find method could search for key in table starting in position index, then return either the location where key was found, or the first null location, whichever comes first. If you have a loop variable i that starts at index, remember to increment i with (i + 1) % table.length so that the search wraps around to the beginning of the table.
I strongly recommend that you write comprehensive test cases for your code in DIYHashMap’s main method. Additionally, you should update GroceryStore to use DIYHashMap and confirm that it still behaves as expected. There are no automated tests to evaluate your test cases for this assignment, but I suggest that your tests include at least the following:
DIYHashMap is initializedget is called on a DIYHashMapput is called at least 5 times on a DIYHashMap with different keys. Why 5? You’ll want to make sure your rehash works! You should also try putting an key that is already present with a new value.size is called on a DIYHashMap and returns the number of elements in the mapCheckstyle will run automatically when you submit to gradescope; up to 10% will be deducted by the autograder from the programming portion of your grade if you have > 2 types of checkstyle problems. Remember you can see more details on checkstyle on this page, including how to run it in vscode.
Note that because starter code is not provided for this assignment, you will need to write all of your javadoc comments from scratch!
I will do a manual review for design. Up to 5% may be deducted from your final score due to design problems. This will also include checking the quality (rather than just the form) of your javadoc comments!
For debugging, we recommend setting up a PSVM in DIYHashMap and using the examples from Lab 8 to test your implementation. Once your DIYHashMap is working, change your GroceryStore class to use your DIYHashMap.