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 Plus MyProgrammingLab with Pearson EText -- Access Card Package
- No AI solutions pleasearrow_forwardCreate an original network topology consisting of at least seven routers and twelve links, assigning arbitrary positive weights to each link. Using this topology, apply Dijkstra's Link-State Algorithm to compute the shortest paths from a source router of your choice to all other routers in the network. Your topology must be entirely your own design and should not resemble any examples from the textbook, lecture slides, or other students' work. Al-generated topologies are not permitted. Create a PowerPoint presentation that follows the format and style of slides 11 to 23 from Lecture Slide Set 06 (LS06). You should copy those slides and make any necessary changes, additions, or deletions to reflect your own topology, shortest-path calculations, and update tables. Do not alter the original slide style, layout, or formatting.arrow_forwardCreate an original network topology consisting of at least seven routers and twelve links, assigning arbitrary positive weights to each link. Using this topology, apply Dijkstra's Link-State Algorithm to compute the shortest paths from a source router of your choice to all other routers in the network. Your topology must be entirely your own design and should not resemble any examples from the textbook, lecture slides, or other students' work. Al-generated topologies are not permitted. Createarrow_forward
- x3003 x3008 1110 0000 0000 1100 1110 0010 0001 0000 0101 0100 1010 0000 x3004 0010 0100 0001 0011 x3005 0110 0110 0000 0000 X3006 0110 1000 0100 0000 x3007 0001 0110 1100 0100 0111 0110 0000 What does the following LC-3 program do? Trace Step by Step, SHOW ALL YOUR WORK. x3001 x3002 0000 x3009 0001 0000 0010 0001 X300A 0001 0010 0110 0001 x300B 0001 0100 1011 1111 x300C 0000 0011 1111 1000 X300D 1111 0000 0010 0101 x300E 0000 0000 0000 0101 x300F 0000 0000 0000 0100 x3010 0000 0000 0000 0011 x3011 0000 0000 0000 0110 x3012 0000 0000 0000 0010 x3013 x3014 0000 0000 0000 0000 0000 0100 0000 0111 x3015 0000 0000 0000 0110 x3016 0000 0000 0000 1000 x3017 0000 0000 0000 0111 x3018 0000 0000 0000 0101arrow_forward2) Assume a local area network has four host computers (h1, h2, h3 & h4) and they are connected to the internet through a NAT router (s1). The host computers use private IP address space: 192.168.2/24. Each host is trying to establish 2 TCP connections to a remote webserver through the NAT router. The IP address of the webserver is: 130.12.11.9. Now do the following: 1 a. Assign IP addresses to the interfaces of the hosts and the router. For the router, assign arbitrary addresses. List these addresses. b. Now create a NAT translation table as taught in the class for all TCP connections. Assign arbitrary port numbers as required.arrow_forward1) Consider the following network. Host h6 10.3.0.6 Host h5 10.3.0.5 Host h1 10.1.0.1 OpenFlow controller m 2 3 4 Host h4 10.2.0.4 Host h2 10.1.0.2 Host h3 10.2.0.3 The desired forwarding behavior for the datagrams arriving at s2 is as follows: a) any datagrams arriving on input port 1 from hosts h5 or h6 that are destined to hosts h1 or h2 should be forwarded over output port 2; b) any datagrams arriving on input port 2 from hosts h1 or h2 that are destined to hosts h5 or h6 should be forwarded over output port 1; c) any arriving datagrams on input ports 1 or 2 and destined to hosts h3 or h4 should be delivered to the host specified; d) hosts h3 and h4 should be able to send datagrams to each other. Create a flow table for s2 that implement these forwarding behaviors. Your table should have 2 columns one for match and the other for actions, as taught in the class.arrow_forward
- Based on the last digit of your Kean ID: Create an LC-3 program that compares 3 personally assigned to you numbers stored in memory and finds the maximum of them. Compile and run on https://wchargin.com/lc3web/. Screenshot and explain your result. ID 0 A 7 B с -3 12 1 0 5 -1 Expected max 12 5 2 -8 -2 6 9 My Kean ID: 1233321 3 14 3 6 14 4 -5 -6 -1 -1 сл 5 10 0 4 10 6 2 11 1 11 7 -9 7 -4 7 8 00 66 00 8 5 13 13 9 -2 3 0 3arrow_forward8 9 See the program below that we worked on in class and that multiplies A=4 by B=5, the result 20 is stored in a particular register: Address 15 14 པPy"BI" ༦ དད་པས་ས་་ 12 11 11 10 9 8 7 6 109876543210 13 12 x3000 0 0 0 0 0 1000 000110 x3001 0 0 1 0 0 1 0000 000110 x3002 0 1 0 1 0 1 101 1 100000 x3003 0 0 0 1 0 1 x3004 0 0 0 1 0 101 1 000001 10010 111111 x3005 0 0 0 0 1 01 1 11 1 1 1 1 0 1 x3006 1 1 1 1 0 00000100101 x3007 0 0 0 0 0 00000000101 x3008 0 00 00 0 0000 0000100 Based on the last digit of your Kean ID, you need to modify it to multiply the personally assigned A and B to you and store the result exactly in the register assigned. Write a program in machine language (in binary) so it looks similar to the above. 3 4 ID 0 A 3 B Result Register 6 R4 1 4 7 R5 2 7 3 R6 My Kean ID: 1233321 2 2 00 8 6 5 9 1 6 R7 33 34 R4 6 0 7 R5 55 7 5 5 R6 6 1 12 R7 RR 7 R3 Trace the program/loop step by step and provide the result of your tracing. SHOW ALL YOUR WORK.arrow_forwardYou are tasked with developing a portable system that can be worn to collect health and fitness data. The challenge is to integrate all functions into the smaller form of an ear clip. The device should include heart rate, movement and temperature sensor and wireless communication with a mobile app. Draw a diagram- hardware architecture of the system- including the selection of suitable sensors, communication modules, and an energy-efficient microcontroller. (visualize the components and their connections)arrow_forward
- Draw out an example of 3 systems using Lamport’s logical clock and explain the steps in words.arrow_forward“Systems have become very powerful and sophisticated, providing quality information fordecisions that enable the firm to coordinate both internally and externally.”With reference to the above statement compare the operations of any three data gatheringsystems today’s organisations use to aid decision making.arrow_forwardlabmas Course Home XDocument courses/13810469/menu/a2c41aca-b4d9-4809-ac2e-eef29897ce04 There are three ionizable groups (weak acids and/or bases) in glutamic acid. Label them on the structure below Drag the appropriate labels to their respective targets. OOH [] CH³N CH CH2 CH2 IC HO Reset Helparrow_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