Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Hash Map with chaining. I have a problem in resize method. Please help me. There are several error messeges. 1. 2. public class MapEntry {
Hash Map with chaining.
I have a problem in resize method. Please help me.
There are several error messeges.
1.
2.
public class MapEntry { private K key; private V value; private MapEntry next; /** * Create a MapEntry object with the given key and value. * * @param key key for this entry * @param value value for this entry */ public MapEntry(K key, V value) { this(key, value, null); } /** * Create a MapEntry object with the given key, value and next reference. * * @param key key for this entry * @param value value for this entry * @param next next entry in the external chain */ public MapEntry(K key, V value, MapEntry next) { this.key = key; this.value = value; this.next = next; } /** * Gets the key held by this entry. * * @return key in this entry. */ public K getKey() { return key; } /** * Sets the key held by this entry. * * @param key key to store in this entry. */ public void setKey(K key) { this.key = key; } /** * Gets the value held by this entry. * * @return value in this entry */ public V getValue() { return value; } /** * Sets the value held by this entry. * * @param value value to store in this entry */ public void setValue(V value) { this.value = value; } /** * Gets the next entry in the external chain. * * @return the next entry */ public MapEntry getNext() { return next; } /** * Sets the next reference in this external chain. * * @param next the new next entry */ public void setNext(MapEntry next) { this.next = next; } @Override public boolean equals(Object o) { // DO NOT USE THIS METHOD IN YOUR CODE! This is for testing ONLY! if (!(o instanceof MapEntry)) { return false; } else { MapEntry that = (MapEntry) o; return that.getKey().equals(key) && that.getValue().equals(value); } } @Override public String toString() { return String.format("%s: %s", key.toString(), value.toString()); } }
public interface HashMapInterface { int INITIAL_CAPACITY = 13; double MAX_LOAD_FACTOR = 0.67; /** * Adds the given key-value pair to the HashMap. * If an entry in the HashMap already has this key, replace the entry's * value with the new one passed in. * * In the case of a collision, use external chaining as your resolution * strategy. Add new entries to the front of an existing chain, but don't * forget to check the entire chain for duplicates first. * * Check to see if the backing array needs to be regrown BEFORE adding. For * example, if my HashMap has an array of length 5, with 3 elements in * it, I should regrow at the start of the next add operation since * (3 + 1) / 5 = 0.8 > 0.67 (even if it is a key that is already in the * hash map). This means you must account for the data pending insertion * when calculating the load factor. * * When regrowing, resize the length of the backing table to * 2 * old length + 1. You must use the resizeBackingTable method to do so. * * Return null if the key was not already in the map. If it was in the map, * return the old value associated with it. * * @param key key to add into the HashMap * @param value value to add into the HashMap * @throws IllegalArgumentException if key or value is null * @return null if the key was not already in the map. If it was in the * map, return the old value associated with it */ V put(K key, V value); /** * Removes the entry with a matching key from the HashMap. * * @param key the key to remove * @throws IllegalArgumentException if key is null * @throws java.util.NoSuchElementException if the key does not exist * @return the value previously associated with the key */ V remove(K key); /** * Gets the value associated with the given key. * * @param key the key to search for * @throws IllegalArgumentException if key is null * @throws java.util.NoSuchElementException if the key is not in the map * @return the value associated with the given key */ V get(K key); /** * Returns whether or not the key is in the map. * * @param key the key to search for * @throws IllegalArgumentException if key is null * @return whether or not the key is in the map */ boolean containsKey(K key); /** * Clears the table and resets it to the default length. */ void clear(); /** * Returns the number of elements in the map. * * @return number of elements in the HashMap */ int size(); /** * Returns a Set view of the keys contained in this map. * Use {@code java.util.HashSet}. * * @return set of keys in this map */ Set keySet(); /** * Returns a List view of the values contained in this map. * Use any class that implements the List interface * This includes {@code java.util.ArrayList} and * {@code java.util.LinkedList}. * * You should iterate over the table in order of increasing index, and * iterate over each chain from front to back. Add entries to the List in * the order in which they are traversed. * * @return list of values in this map */ List values(); /** * Resize the backing table to {@code length}. * * Disregard the load factor for this method. So, if the passed in length is * smaller than the current capacity, and this new length cause the table's * load factor to exceed MAX_LOAD_FACTOR, you should still resize the table * to the specified length and leave it at that capacity. * * You should iterate over the old table in order of increasing index, and * iterate over each chain from front to back. Add entries to the new table * in the order in which they are traversed. * * Remember that you cannot just simply copy the entries over to the new * array. * * Also, since resizing the backing table is working with the non-duplicate * data already in the table, you shouldn't explicitly check for * duplicates. * * @param length new length of the backing table * @throws IllegalArgumentException if length is non-positive or less than * the number of items in the hash map. */ void resizeBackingTable(int length); /** * DO NOT USE THIS METHOD IN YOUR CODE. IT IS FOR TESTING ONLY. * * @return the backing array of the data structure, not a copy. INCLUDE * EMPTY SPACES */ MapEntry[] getTable(); }public V put(K key, V value) i == nu throw new IllegaLArgumentException("Key or Value cannot be null") if (((size + 1. O) table . length) >=MAX LOAD FACTOR) { resizeBackingTable( length: this.table.length * 2 1)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started