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
- Don't use chatgpt or any other AIarrow_forwardGiven a relation schema R = (A, B, C, D, E,G) with a set of functional dependencies F {ABCD BC → DE B→ D D→ A}. (a) Show that R is not in BCNF using the functional dependency A → BCD. (b) Show that AG is a superkey for R (c) Compute a canonical cover Fc for the set of functional dependencies F. Show your work. (d) Give a 3NF decomposition of R based on the canonical cover found in (c). Show your work. (e) Give a BCNF decomposition of R using F. Show your work.arrow_forwardThe following entity-relationship (ER) diagram models a database that helps car deal- ers maintain records of customers and cars in their inventory. Construct a relational database schema from the ER diagram. Your set of schemas should include primary-key and foreign-key constraints and you should ensure there are no redundant schemas. has_model model modelID name vehicle has_vehicle VIN dealer_ID brand name has_available_option has_option has_dealer options options_ID specification dealer dealer ID name customer_ID owned_by customer customer ID namearrow_forward
- A relation schema R = (A, B, C, D, E) with a set of functional dependencies F= {D A CAB} is decomposed into R₁ = (A, B, C) and R2 = (C, D, E). (a) Is this a lossless-join decomposition? Why or why not? (b) Is the decomposition dependency preserving? Why or why not?arrow_forwardNo chatgpt pleasearrow_forwardPlease help draw alu diagraarrow_forward
- 1. Level the resources (R) for the following network. Show exactly which activity is being moved at each cycle and how many days it is being moved. Show all cycles required to utilize the free float and the back float. B H 3 3 L 2 0-0-0 A C F G K N P Q T 0 3 2 2 1 2-2-2 7R 8R 4R 6R 4R 2R 5R 4R D 1 2R 2 M 000 4R 2 4R 1 2 3 4 B5 B BE B 5 5 7 D 2003 C NO C MBSCM В H 5 2 F 7 7 8 SH2F80 5 Н Н 6 7 7L3G4+ 6H2G4 J 4 4 14 8 L K 00 36 9 10 11 12 13 14 15 P 2 Z+ N N 4 4 Z t 2334 4 Σ + M M 4 +arrow_forward2. Perform resource allocation for the following project. Resource limits are 6 labors and 2 helpers. Legend: Activity Dur Resources G H 2 3 2L 1H 2L OH A 1 3L 1H + B D F J K 3 4 6 2 4 4L 2H 3L OH 4L 1H 2L 2H 4L 2H C E 2 2 I 1 2L 1H 3L 1H 5L 1Harrow_forwardNeed Java method please. Thank you.arrow_forward
- Need Java method please. Thank you.arrow_forward3. Write two nested loops to generate the following output. (Note: There is one space between each number, and any extra line shown is intentional.) 12 10 8 6 18 15 12 24 20 30 2 3 3 6 48 12 5 10 15 20 6 12 18 24 30arrow_forwardWrite in verilog coding languagearrow_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