due: Tuesday December 3rd at 11:59pm (submit on Gradescope here).
In 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.
The starter code can be downloaded here.
Our main task is to calculate the total cost of a grocery cart using the price per pound of certain foods. The foods to consider are provided in the prices.csv file which is formatted as follows:
FoodName,Form,RetailPrice,RetailPriceUnit,Yield,CupEquivalentSize,CupEquivalentUnit,CupEquivalentPrice
The 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. Use Java's built-in HashMap to get started (you'll 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. Cents should be rounded down. 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 19.31. The total cost of all items in the store using a weight of 1 pound is 289.9496, but we will return 289.94.
DIYHashMap.Implement 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 slide 9 in the Lecture 10R notes as well as Lab 8. 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.
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.When debugging, I would recommend setting up a PSVM in DIYHashMap and use the examples from Lab 8 to test your implementation. Once your DIYHashMap is working, change your GroceryStore class to use your DIYHashMap.
Please upload GroceryStore.java and DIYHashMap.java to Gradescope. Remember to check the style of your code and add javadoc-style documentation for all methods you implement.
Last updated: 2024-12-10