due: Thursday May 1 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.
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,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. (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. 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 would return 289.94.
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 slide 9 in the Lecture 10W 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. 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 10W).
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.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.
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.
Upload GroceryStore.java and DIYHashMap.java to Gradescope. Pre-submission check-list:
javadoc-style documentation for public methods you implement;import java.util.HashMap; at the top of GroceryStore.java when completing Part 2.