Concept explainers
MyMap using Open Addressing with Linear Probing
Program Plan:
- Define a class named “Sample” to implement MyMap using open addressing with linear probing.
- Define function main.
- Define an integer HashMap named “map”.
- Put ‘2, 2” into the map.
- Remove “2” from the map.
- Define a static class named “MyHashMap” and implement “MyMap”.
- Define required variables.
- Define a function named “MyHashMap”.
- Construct a map with the default capacity and load factor.
- Define a function named “MyHashMap” with one parameter.
- Construct a map with the specific initial capacity and default load factor.
- Define a function named “MyHashMap” with two parameters.
- Construct a map with the default capacity and load factor.
- Define a function named “clear”.
- Remove all of the entries from this map.
- Define a function named “containsKey”.
- Return true if the specified key is in the map.
- Define a function named “containsValue”.
- Return true if this map contains the specific value.
- Define a function named “entrySet”.
- Return a set of entries in the map.
- Define a function named “get”.
- Return the first value that matches the specific key.
- Define a function named “getAll”.
- Return all values for the specified key in this map.
- Define a function named “isEmpty”.
- Return true if this map contains no entries.
- Define a function named “keyset”.
- Return a set consisting of the keys in this map.
- Define a function named “put”.
- Add an entry (key, value) into the map and return the value.
- Define a function named “remove”.
- Remove the element for the specific key.
- Define a function named “size”.
- Return the number of mappings in this map.
- Define a function named “values”.
- Return a set consisting of the values in this map.
- Define a function named “hash”.
- Return “hashCode % capacity” value.
- Define a function named “supplmentHash”.
- Ensure the hashing is evenly distributed and return the result.
- Define a function named “removeEntries”.
- Remove all entries from each bucket.
- Define a function named “rehash”.
- Rehash this map.
- Define a function named “toString”.
- Return a string representing for this map.
- Define an interface name “MyMap”.
- Declare function prototypes for the functions which are created at the class “MyHashMap”.
- Define function main.
The below program creates a new concrete class that implements MyMap using open addressing with linear probing, whose hash table size is 4 and the table size get doubled when the load factor exceeds the threshold 0.5.
Explanation of Solution
Program:
public class Sample {
/** Main method */
public static void main(String[] args) {
MyHashMap<Integer, Integer> map = new MyHashMap<>();
map.put(2, 2);
System.out.println("Is key 2 in the map? " + map.containsKey(2));
map.remove(2);
System.out.println("Is key 2 in the map? " + map.containsKey(2));
}
static class MyHashMap<K, V> implements MyMap<K, V> {
// Define the default hash table size.
private static int INITIAL_CAPACITY = 4;
// Define the maximum hash table size. 1 << 30 is same as 2^30
private static int MAX_CAPACITY = 1 << 30;
// Current hash table capacity.
private int capacity;
// Define default load factor
private static float MAX_LOAD_FACTOR = 0.5f;
// 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
MyMap.Entry<K, V>[] table;
/** Construct a map with the default capacity and load factor */
public MyHashMap() {
this(INITIAL_CAPACITY, MAX_LOAD_FACTOR);
}
/**
* Construct a map with the specified initial capacity and default load
* factor
*/
public MyHashMap(int initialCapacity) {
this(initialCapacity, MAX_LOAD_FACTOR);
}
/**
* Construct a map with the specified initial capacity and load factor
*/
public MyHashMap(int initialCapacity, float loadFactorThreshold) {
this.capacity = initialCapacity;
this.loadFactorThreshold = loadFactorThreshold;
table = new MyMap.Entry[capacity];
}
/** Remove all of the entries from this map */
public void clear() {
size = 0;
removeEntries();
}
/** Return true if the specified key is in the map */
public boolean containsKey(K key) {
if (get(key) != null)
return true;
else
return false;
}
/** Return true if this map contains the specified value */
public boolean containsValue(V value) {
for (int i = 0; i < table.length; i++)
if (table[i] != null && table[i].value.equals(value))
return true;
return false;
}
/** 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<MyMap.Entry<K, V>>();
for (int i = 0; i < capacity; i++)
if (table[i] != null)
set.add(table[i]);
return set;
}
/** Return the first value that matches the specified key */
public V get(K key) {
// Perform linear probing
int i = hash(key.hashCode());
while (table[i] != null) {
if (table[i].key != null && table[i].key.equals(key))
return table[i].value;
i = (i + 1) % table.length;
}
return null;
}
/** Return all values for the specified key in this map */
public java.util.Set<V> getAll(K key) {
java.util.Set<V> set = new java.util.HashSet<V>();
for (int i = 0; i < capacity; i++)
if (table[i] != null && table[i].key.equals(key))
set.add(table[i].value);
return set;
}
/** Return true if this map contains no entries */
public boolean isEmpty() {
return size == 0;
}
/** 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<K>();
for (int i = 0; i < capacity; i++)
if (table[i] != null)
set.add(table[i].key);
return set;
}
/** Add an entry (key, value) into the map */
public V put(K key, V value) {
if (size >= capacity * loadFactorThreshold) {
if (capacity == MAX_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int i = hash(key.hashCode());
while (table[i] != null && table[i].key != null)
i = (i + 1) % table.length;
// Add an entry (key, value) to the table
table[i] = new MyMap.Entry<K, V>(key, value);
size++; // Increase size
return value;
}
/** Remove the element for the specified key */
public void remove(K key) {
int i = hash(key.hashCode());
while (table[i] != null
&& (table[i].key == null || !table[i].key.equals(key)))
i = (i + 1) % table.length;
if (table[i] != null && table[i].key.equals(key)) {
// A special marker Entry(null, null) is placed for the deleted
// entry
table[i] = new MyMap.Entry<K, V>(null, null);
size--;
}
}
/** Return the number of mappings in this map */
public int size() {
return size;
}
/** 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<V>();
for (int i = 0; i < capacity; i++)
if (table[i] != null)
set.add(table[i].value);
return set;
}
/** Hash function */
private int hash(int hashCode) {
return hashCode % capacity;
// return supplementHash(hashCode) & (capacity - 1);
}
/** Ensure the hashing is evenly distributed */
private static int supplementHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** Remove all entries from each bucket */
private void removeEntries() {
for (int i = 0; i < capacity; i++)
table[i] = null;
}
/** Rehash the map */
private void rehash() {
java.util.Set<Entry<K, V>> set = entrySet(); // Get entries
capacity <<= 1; // Double capacity
table = new Entry[capacity]; // Create a new hash table
size = 0; // Clear size
for (Entry<K, V> entry : set) {
put(entry.getKey(), entry.getValue()); // Store to new table
}
}
@Override
/** Return a string representation for this map */
public String toString() {
StringBuilder builder = new StringBuilder("[");
for (int i = 0; i < capacity; i++) {
if (table[i] != null && table[i].key != null)
builder.append(table[i].toString());
}
return builder.append("]").toString();
}
}
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 all values for the specified key in this map */
public java.util.Set<V> getAll(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 + "]";
}
}
}
}
Is key 2 in the map? true
Is key 2 in the map? false
Want to see more full solutions like this?
Chapter 27 Solutions
Introduction to Java Programming and Data Structures, Comprehensive Version (11th Edition)
- - Write a Polynomial class that has methods for creating a polynomial, reading and writing a polynomial, and adding a pair of polymomials - In order to add 2 polynomials, traverse both lists, If a particular exponent value is present in either one, it should also be present In the resulting polynomial unless its coefficient is zero. java submit as a text dont use others answers please attach screenshot of output Thank you!!!arrow_forward(Sort ArrayList) Write the following method that sorts an ArrayList: public static <E extends Comparable<E>> void sort(ArrayList<E> list) Write a test program that prompts the user to enter 10 integers, invokes this method to sort the numbers, and displays the numbers in increasing order. Sample Run Enter 10 integers: 3 4 12 7 3 4 5 6 4 7 The sorted numbers are 3 3 4 4 4 5 6 7 7 12 Class Name: Exercise19_09arrow_forward(Please Help. My professor did not teach us any of this and will not answer my emails) Design a class named Queue for storing integers. Like a stack, a queue holds elements. In a stack, the elements are retreived in a last-in-first-out fashion. In a queue, the elements are retrieved in a first-in-first-out fashion. The class contains: An int[] data field named elements that stores the int values in the queue A data field named size that stores the number of elements in the queue A constructor that creates a Queue object with defult capacity 8 The method enqueue(int v) that adds v into the queue The method empty () that returns true if the queue is empty The method getSize() that returns the size of the queuearrow_forward
- java program: If in the ArrayStack, the first element that we push to the stack, is stored in location capacity – 1 (capacity is the capacity of the array theData) in the array theData and the subsequent elements that we push, we keep on adding before the last element added in the array. That is, in the constructor of class ArrayStack, we initialize the topOfStack to capacity and we write the push method as follows: public E push(E obj) { if (topOfStack == 0) reallocate(); topOfStack--; theData[topOfStack] = obj; return obj; } This push method can work but the if statement should be: if (topOfStack == theData.length - 1) reallocate(); This push method will work provided we modify the reallocate method. This push method can work, but topOfStack-- ; should come after theData[topOfStack] = obj; This push method can work, but topOfStack-- ; should be topOfStack++;arrow_forward(Generic binary search) Implement the following method using binary search. public static > int binarySearch(E[] list, E key)arrow_forwardWrite a function that is passed an array of numbers and returns a hash table containing the minimum, maximum and average value. @{min=????; max-???; average=???} Test by passing the function 3 different arrays of randomly generated numbers. If the array is empty set all 3 values to zero. (3)arrow_forward
- Write the following method in Java: public void reverse() The method will reverse the linked list. Head will point to the last node of the linked list and all the pointers (addresses) will be reversed. The last node (a new head) will point to the second last node and so on. The old head node will become the tail node in the reversed LinkedList. Use the LinkedList class discussed in the video lecture and write the reverse() method in the same class. Test your method in the main method. Following picture depicts the reversal of the LinkedList. NULL Head I V R I ↑ Head > NULLarrow_forward(Test perfect binary tree) JAVA A perfect binary tree is a complete binary tree with all levels fully filled. Define a new class named BSTWithTestPerfect that extends BST with the following methods: (Hint: The number of nodes in a perfect binary tree is 2^(height+1) - 1.) /** Returns true if the tree is a perfect binary tree */public boolean isPerfectBST() Use https://liveexample.pearsoncmg.com/test/Exercise25_03.txt to test your code. Class Name: Exercise25_03arrow_forwardJust do the Simulation please. No need to write the Code.arrow_forward
- Question 7: Write a method for the ArrayBoundedStack class that creates and returns a stack copy of this. (Hint: use topIndex and elements) Use following method signature: public ArrayBoundedStack<T> copy()arrow_forwardGo program using generics Output True Falsearrow_forwardPROGRAM IN C++ Our BoardArray will store 5 entries maximum. Improve the following existing methods: bool add(entry* e) Improve the add method where you will return true if the entry has been successfully added (i.e. the entry is placed in the top 10), otherwise return false (i.e. if the entry did not make it to the top 10). bool remove(const char* person) Improve the remove method where you return true if an entry is successfully deleted (i.e. we have found an entry that matches the person), otherwise return false. Add the following additional methods: bool ban_country(const char* nation) Removes all the entries bearing the country equal to the given nation. Return true if at least one entry has been removed, otherwise return false. int country_wins(const char* nation) Returns the number of entries in the scoreboard who represents the given nation. int exemplary(int score) Returns how many entries in the scoreboard are greater than or equal to the given score. double…arrow_forward
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education