[Solved]Mymap Public Interface Mymap Remove Entries Map Public Void Clear Return True Specified Ke Q37181590

MyMap:

public interface MyMap<K, V> { /** Remove all of the entries from this map */ public void clear(); /** Return true if the specified key is in the map */ public boolean containsKey(K key); /** Return true if this map contains the specified value */ public boolean containsValue(V value); /** Return a set of entries in the map */ public java.util.Set<Entry<K, V>> entrySet(); /** Return the first value that matches the specified key */ public V get(K key); /** Return true if this map contains no entries */ public boolean isEmpty(); /** Return a set consisting of the keys in this map */ public java.util.Set<K> keySet(); /** Add an entry (key, value) into the map */ public V put(K key, V value); /** Remove the entries for the specified key */ public void remove(K key); /** Return the number of mappings in this map */ public int size(); /** Return a set consisting of the values in this map */ public java.util.Set<V> values(); /** Define inner class for Entry */ public static class Entry<K, V> { K key; V value; public Entry(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } @Override public String toString() { return “[” + key + “, ” + value + “]”; } }}

MyHashMap:

import java.util.LinkedList;public class MyHashMap<K, V> implements MyMap<K, V> { // Define the default hash table size. Must be a power of 2 private static int DEFAULT_INITIAL_CAPACITY = 4; // Define the maximum hash table size. 1 << 30 is same as 2^30 private static int MAXIMUM_CAPACITY = 1 << 30; // Current hash table capacity. Capacity is a power of 2 private int capacity; // Define default load factor private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f; // Specify a load factor used in the hash table private float loadFactorThreshold; // The number of entries in the map private int size = 0; // Hash table is an array with each cell that is a linked list LinkedList<MyMap.Entry<K,V>>[] table; /** Construct a map with the default capacity and load factor */ public MyHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR); } /** Construct a map with the specified initial capacity and * default load factor */ public MyHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR); } /** Construct a map with the specified initial capacity * and load factor */ public MyHashMap(int initialCapacity, float loadFactorThreshold) { if (initialCapacity > MAXIMUM_CAPACITY) this.capacity = MAXIMUM_CAPACITY; else this.capacity = trimToPowerOf2(initialCapacity); this.loadFactorThreshold = loadFactorThreshold; table = new LinkedList[capacity]; } @Override /** Remove all of the entries from this map */ public void clear() { size = 0; removeEntries(); } @Override /** Return true if the specified key is in the map */ public boolean containsKey(K key) { if (get(key) != null) return true; else return false; } @Override /** Return true if this map contains the value */ public boolean containsValue(V value) { for (int i = 0; i < capacity; i++) { if (table[i] != null) { LinkedList<Entry<K, V>> bucket = table[i]; for (Entry<K, V> entry: bucket) if (entry.getValue().equals(value)) return true; } } return false; } @Override /** Return a set of entries in the map */ public java.util.Set<MyMap.Entry<K,V>> entrySet() { java.util.Set<MyMap.Entry<K, V>> set = new java.util.HashSet<>(); for (int i = 0; i < capacity; i++) { if (table[i] != null) { LinkedList<Entry<K, V>> bucket = table[i]; for (Entry<K, V> entry: bucket) set.add(entry); } } return set; } @Override /** Return the value that matches the specified key */ public V get(K key) { int bucketIndex = hash(key.hashCode()); if (table[bucketIndex] != null) { LinkedList<Entry<K, V>> bucket = table[bucketIndex]; for (Entry<K, V> entry: bucket) if (entry.getKey().equals(key)) return entry.getValue(); } return null; } @Override /** Return true if this map contains no entries */ public boolean isEmpty() { return size == 0; } @Override /** Return a set consisting of the keys in this map */ public java.util.Set<K> keySet() { java.util.Set<K> set = new java.util.HashSet<>(); for (int i = 0; i < capacity; i++) { if (table[i] != null) { LinkedList<Entry<K, V>> bucket = table[i]; for (Entry<K, V> entry: bucket) set.add(entry.getKey()); } } return set; } @Override /** Add an entry (key, value) into the map */ public V put(K key, V value) { if (get(key) != null) { // The key is already in the map int bucketIndex = hash(key.hashCode()); LinkedList<Entry<K, V>> bucket = table[bucketIndex]; for (Entry<K, V> entry: bucket) if (entry.getKey().equals(key)) { V oldValue = entry.getValue(); // Replace old value with new value entry.value = value; // Return the old value for the key return oldValue; } } // Check load factor if (size >= capacity * loadFactorThreshold) { if (capacity == MAXIMUM_CAPACITY) throw new RuntimeException(“Exceeding maximum capacity”); rehash(); } int bucketIndex = hash(key.hashCode()); // Create a linked list for the bucket if it is not created if (table[bucketIndex] == null) { table[bucketIndex] = new LinkedList<Entry<K, V>>(); } // Add a new entry (key, value) to hashTable[index] table[bucketIndex].add(new MyMap.Entry<K, V>(key, value)); size++; // Increase size return value; } @Override /** Remove the entries for the specified key */ public void remove(K key) { int bucketIndex = hash(key.hashCode()); // Remove the first entry that matches the key from a bucket if (table[bucketIndex] != null) { LinkedList<Entry<K, V>> bucket = table[bucketIndex]; for (Entry<K, V> entry: bucket) if (entry.getKey().equals(key)) { bucket.remove(entry); size–; // Decrease size break; // Remove just one entry that matches the key } } } @Override /** Return the number of entries in this map */ public int size() { return size; } @Override /** Return a set consisting of the values in this map */ public java.util.Set<V> values() { java.util.Set<V> set = new java.util.HashSet<>(); for (int i = 0; i < capacity; i++) { if (table[i] != null) { LinkedList<Entry<K, V>> bucket = table[i]; for (Entry<K, V> entry: bucket) set.add(entry.getValue()); } } return set; } /** Hash function */ private int hash(int hashCode) { return supplementalHash(hashCode) & (capacity – 1); } /** Ensure the hashing is evenly distributed */ private static int supplementalHash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** Return a power of 2 for initialCapacity */ private int trimToPowerOf2(int initialCapacity) { int capacity = 1; while (capacity < initialCapacity) { capacity <<= 1; } return capacity; } /** Remove all entries from each bucket */ private void removeEntries() { for (int i = 0; i < capacity; i++) { if (table[i] != null) { table[i].clear(); } } } /** Rehash the map */ private void rehash() { java.util.Set<Entry<K, V>> set = entrySet(); // Get entries capacity <<= 1; // Double capacity table = new LinkedList[capacity]; // Create a new hash table size = 0; // Reset size to 0 for (Entry<K, V> entry: set) { put(entry.getKey(), entry.getValue()); // Store to new table } } @Override public String toString() { StringBuilder builder = new StringBuilder(“[“); for (int i = 0; i < capacity; i++) { if (table[i] != null && table[i].size() > 0) for (Entry<K, V> entry: table[i]) builder.append(entry); } builder.append(“]”); return builder.toString(); }}The code in Chapter 27 implements the MyMap interface using separate chaining. For this assignment, you will implement МХмар using open addressing with linear probing. Create a new concrete class named MyHashMap that implements MyMap using open addressing with linear probing. For l simplicity, use f (key) -key % size as the hash function, where size is the hash-table size. Initially, the hash-table size is 4. The table size is doubled whenever the load factor exceeds the threshold (0.5) Modify TestMyHashMap.java in the text (Listiing 27.3) slightly and use it to test MyHashMap. Your output should be as follows: Entries in map: [[Anderson, 31][Smith, 65] [Lewis, 29] [Cook, 29]) The age for Lewis is 29 Is Smith in the map? true Is age 33 in the map? false Entries in map after removing Smith: [[Anderson, 31] [Lewis, 29) [Cook, 291] Entries after clearing map: [l Hii: The hash table will be an array of map entries. The hash code of a string can be negative. It should be made positive before hashing it to produce an index that lies within the bounds of the array: 1. 2. int index hash(Math.abs(key.hashCode())); Show transcribed image text The code in Chapter 27 implements the MyMap interface using separate chaining. For this assignment, you will implement МХмар using open addressing with linear probing. Create a new concrete class named MyHashMap that implements MyMap using open addressing with linear probing. For l simplicity, use f (key) -key % size as the hash function, where size is the hash-table size. Initially, the hash-table size is 4. The table size is doubled whenever the load factor exceeds the threshold (0.5) Modify TestMyHashMap.java in the text (Listiing 27.3) slightly and use it to test MyHashMap. Your output should be as follows: Entries in map: [[Anderson, 31][Smith, 65] [Lewis, 29] [Cook, 29]) The age for Lewis is 29 Is Smith in the map? true Is age 33 in the map? false Entries in map after removing Smith: [[Anderson, 31] [Lewis, 29) [Cook, 291] Entries after clearing map: [l Hii: The hash table will be an array of map entries. The hash code of a string can be negative. It should be made positive before hashing it to produce an index that lies within the bounds of the array: 1. 2. int index hash(Math.abs(key.hashCode()));

Expert Answer

---

Answer to MyMap: public interface MyMap { /** Remove all of the entries from this map */ public void clear(); /** Return true if … . . .