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
MyLab Programming with Pearson eText -- Access Card -- for Introduction to Java Programming and Data Structures, Comprehensive Version
- Minimum Study Hours per Week per Class Grade 15 A 12 B 9 C 6 D 0 F Application must be menu driven, and contain the following options: A. Determine Hours to Study B. Determine Grade C. Display Averages and Totals D. Quit Note: The user must be able to select any menu option in any order they want. And only exits the application when they choose. Menu option A -- Determine Hours to Study The program will READ in data from a text file named StudyHours.txt. This text file is created by you and will be submitted with your project. Your file must include 5 additional records in addition to the example at the end of this document (10 total). StudyHours.txt contains the following format: First line: Full name Second line: Number of credits Third line: Grade desired for each class The user must correct any bad data in the application. For example, if the file contains a letter grade of 'K', which is not a possible letter grade, they are asked to correct the information. You DO NOT need to…arrow_forwardNO AI USE PLEASEarrow_forwardRSA decryption: You are given the following RSA values: n = 9797, e = 7, d = 4111. Some ciphertext was received: c = 7321. Based on that information, compute the plaintext message m. Show all your work along the way. No Use of AI pleasearrow_forward
- (25 points) What are the use cases in which public key encryption would be useless? In light of what we discussed in class. would the internet be where it is today without the COIS-4370H-A-F01-2025FA-OSH Computer & Info Security Ords. City any sources you use. Remember to frame your answer in light of what was discussed in class.arrow_forward2) You have learned in class the major steps that occur when a laptop requests a webpage after connecting to a network. In this assignment, you will apply that knowledge to another scenario: opening and playing a YouTube video that resides in Google's data-center infrastructure. Explain, in as much detail as you can, all the steps involved from your device's initial connection to the home/university network, to DNS resolution, routing across multiple networks, reaching Google's servers, and finally receiving the video data. To support your explanation, use tools such as ipconfig, nslookup, and tracert on your own computer, as well as any online IP-lookup tools of your choice. For each stage, include relevant information such as IP addresses, MAC addresses, router hops, and any other details you can gather. You are not expected to find every piece of information, but be as comprehensive as possible based on what you have learned in class, and justify your reasoning with screenshots from…arrow_forwardPlease no use of AIarrow_forward
- help me with this project. provide what I should put on each slide (words, example images, etc); example Slide 1: Intro. here are the directions: Submit a report that includes the source code, compiled code, description of the algorithm(s) implemented, data structures used, implementation details including time complexity analysis, sample inputs/outputs, and a conclusion section.arrow_forwardThese questions are for a Computer Science course called "Theory of Computation". Provide the answers and process to the answers by using steps without little to no explanations. Provide drawings if necessary based on the questions for 1, 2a-c, and 3 based on these images provided.arrow_forwardObjective: The objective of this assignment is to gain practice with pen testing a live web application running on a remote server. The live web application is a known vulnerable web application called DVWA (Damn Vulnerable Web Application) with security settings set to low. The web app is running on an AWS EC2 (Elastic Compute Cloud) instance running Ubuntu 22. Note: The point of this assignment is to step it up a notch, we learnt about different web application vulnerabilities and applied that knowledge, now we are going to pen test and enumerable the vulnerabilities of a web app + the underlying infrastructure it is running on. Before you begin please find out what your IP address is and place it in this sheet so that I can track who is doing what: IP Addresses.docx . Tasks: 1- Start by connecting to the target, I did not install a TLS certificate on purpose that is why you are going to connect via http and not via https: http://3.99.221.134/dvwa/login.php 2- Broken Authentication:…arrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage Learning
Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning
Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage
EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT