Key Concepts
Directions: Fill in the blanks, this is a Popcorn HACK
Hashing
- HashMap uses a hash function to map keys to their respective bukets .
- A good hash function generates a unique hash code for each key, but collisions can still occur.
- The hash map in Java does not maintain insertion order.
Performance
- HashMap provides constant-time performance (O(1)) for get() and put() operations.
- Performance can degrade to O(n) in the worst case, especially if there are many hash collisions.
Key and Value Types
- HashMap allows any non null object as a key and any object (including null) as a value.
- For a class to be used as a key, it must implement the get and puts methods.
Iteration:
- HashMap provides methods like keySet(), values(), and entrySet() for iterating over key-value pairs.
- The entrySet() method returns a Set view of key-value pairs, allowing key vlaue sets and model pairs .
Thread Safety
- HashMap is not thread-safe. For thread-safe operations, use ConcurrentHashMap.
What is HashMap
A HashMap store items in “key/value” pairs, and you can access them by an index of another type (e.g. a String).
One object is used as a key (index) to another object (value). It can store different types: String keys and Integer values, or the same type, like: String keys and String values:
Creating HashMap in Java
import java.util.HashMap; // import the HashMap class
public class CreateHashMap{
public static void main(String[] args){
// Generating the HashMap
HashMap<String, String> capitalCities = new HashMap<String, String>();
// Adding key/value pairs tothe HashMap to store
capitalCities.put("America", "D.C");
capitalCities.put("Germany", "Berlin");
capitalCities.put("United Kingdom", "London");
capitalCities.put("India", "Delhi");
capitalCities.put("Afghanistan", "Delhi");
capitalCities.put("Bangladesh", "Dhaka");
System.out.println("Successfully created a HashMap which stores items in key/value pairs");
}
}
CreateHashMap.main(null);
Successfully created a HashMap which stores items in key/value pairs
Methods in HashMap
import java.util.HashMap;
public class ExampleHashMap {
public static void main(String[] args) {
// Create a HashMap
HashMap<String, Integer> hashMap = new HashMap<>();
// Add elements to the HashMap
hashMap.put("Shivansh", 25);
hashMap.put("Shaurya", 30);
hashMap.put("Patrick Mahomes", 28);
hashMap.put("Travis Kelce", 34);
hashMap.put("Tom Brady", 46);
// HashMap put() method in Java (Access elements in the HashMap)
System.out.println(hashMap.get("Shivansh"));
// HashMap remove() method in Java (Remove an element from the HashMap)
hashMap.remove("Tom Brady");
// HashMap size() method in Java (Get the size of the HashMap)
System.out.println(hashMap.size());
// HashMap entrySet() method in Java (Get the Entry Set)
System.out.println("The set is: " + hashMap.entrySet());
// HashMap containsKey() method in Java (check whether a particular key is being mapped into the HashMap or not)
System.out.println("Is the key 'Shivansh' present? " + hashMap.containsKey("Shivansh"));
}
}
ExampleHashMap.main(null);
25
4
The set is: [Travis Kelce=34, Shivansh=25, Shaurya=30, Patrick Mahomes=28]
Is the key 'Shivansh' present? true
Popcorn Hack 1
Declare a Hashmap, and then research 5 different HashMap method which were not listed above and use them in your code just like the one above.
import java.util.HashMap;
import java.util.Map;
public class HashMapExample {
public static void main(String[] args) {
// Declare a HashMap
Map<Integer, String> hashMap = new HashMap<>();
// Add elements to the HashMap
hashMap.put(1, "One");
hashMap.put(2, "Two");
hashMap.put(3, "Three");
// Using putIfAbsent method
hashMap.putIfAbsent(4, "Four"); // Adds the entry only if the key is not present
// Using computeIfAbsent method
hashMap.computeIfAbsent(5, k -> "Five"); // Computes and adds the value if the key is absent
// Using keySet method
System.out.println("Keys in the HashMap:");
for (Integer key : hashMap.keySet()) {
System.out.println(key);
}
// Using values method
System.out.println("\nValues in the HashMap:");
for (String value : hashMap.values()) {
System.out.println(value);
}
// Using entrySet method
System.out.println("\nEntries in the HashMap:");
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
}
}
Traversing through HashMap
In the code below, hash_map.entrySet() is used to return a set view of the mapped elements. Now, getValue() and getKey() functions, key-value pairs can be iterated.
import java.util.HashMap;
import java.util.Map;
public class TraverseHashMap {
public static void main(String[] args) {
// Week 15 NFL Quarterback Rankings
HashMap<Integer, String> hash_map = new HashMap<>();
hash_map.put(1, "Jalen Hurts");
hash_map.put(2, "Dak Prescott");
hash_map.put(3, "Josh Allen");
hash_map.put(4, "Lamar Jackson");
hash_map.put(5, "Brock Purdy");
for (Map.Entry<Integer, String> set : hash_map.entrySet()) {
System.out.println(set.getKey() + " = " + set.getValue());
}
}
}
1 = Jalen Hurts
2 = Dak Prescott
3 = Josh Allen
4 = Lamar Jackson
5 = Brock Purdy
Popcorn Hack 2 (Extra Credit)
Try to find a different way to traverse a HashMap (Hint: try using a forEach function)
import java.util.HashMap;
public class TraverseHashMap {
public static void main(String[] args) {
// Week 15 NFL Quarterback Rankings
HashMap<Integer, String> hash_map = new HashMap<>();
hash_map.put(1, "Jalen Hurts");
hash_map.put(2, "Dak Prescott");
hash_map.put(3, "Josh Allen");
hash_map.put(4, "Lamar Jackson");
hash_map.put(5, "Brock Purdy");
// Using forEach to traverse the HashMap
hash_map.forEach((key, value) -> System.out.println(key + " = " + value));
}
}
TraverseHashMap.main(null)
1 = Jalen Hurts
2 = Dak Prescott
3 = Josh Allen
4 = Lamar Jackson
5 = Brock Purdy
HashMaps in Java - Pet Registry Example
public class Pet {
private final String name;
private final int age;
private final String color;
public Pet(String name, int age, String color) {
this.name = name;
this.age = age;
this.color = color;
}
public String getName() {
return this.name;
}
public int getAge() {
return this.age;
}
public String getColor() {
return this.color;
}
}
public class PetsRegistry {
private HashMap<String, Pet> petRegistry = new HashMap<>(); // declares a private HashMap instance variable petRegistry
// Key Type String and Value Type Pet
public PetsRegistry() {
// Add some pets to the registry
petRegistry.put("Leo", new Pet("Lion", 8, "Gold"));
petRegistry.put("Porky", new Pet("Pig", 3, "Pink"));
petRegistry.put("Ro-Ro", new Pet("Robin", 7, "Red"));
petRegistry.put("Midnight", new Pet("Cat", 10, "Black"));
petRegistry.put("Hobbes", new Pet("Kitty", 1, "Calico"));
petRegistry.put("Duke", new Pet("Dog", 14, "Brown"));
}
public Pet removePet(String name) {
// Remove a pet by name
return petRegistry.remove(name);
}
public void printRegistry() {
// Iterate over the registry and print pet information
for (String name : petRegistry.keySet()) { // for each loop
Pet pet = petRegistry.get(name);
System.out.println(name + " is a " + pet.getColor() + " " + pet.getName() +
" and is " + pet.getAge() + " years old.");
}
System.out.println();
}
public static void main(String[] args) {
// Initialize the pet registry
PetsRegistry petsRegistry = new PetsRegistry();
petsRegistry.printRegistry();
// Remove a pet
String petNameToRemove = "Hobbes";
Pet removedPet = petsRegistry.removePet(petNameToRemove);
if (removedPet == null) {
System.out.println(petNameToRemove + " not found");
} else {
System.out.println("Removed: " + petNameToRemove + ", " + removedPet);
}
// Print the updated registry
petsRegistry.printRegistry();
}
}
PetsRegistry.main(null)
Hobbes is a Calico Kitty and is 1 years old.
Leo is a Gold Lion and is 8 years old.
Porky is a Pink Pig and is 3 years old.
Ro-Ro is a Red Robin and is 7 years old.
Duke is a Brown Dog and is 14 years old.
Midnight is a Black Cat and is 10 years old.
Removed: Hobbes, REPL.$JShell$13$Pet@41a890b3
Leo is a Gold Lion and is 8 years old.
Porky is a Pink Pig and is 3 years old.
Ro-Ro is a Red Robin and is 7 years old.
Duke is a Brown Dog and is 14 years old.
Midnight is a Black Cat and is 10 years old.
Popcorn HACK 3 (Shaurya)
import java.util.HashMap;
import java.util.Map;
public class HashMapTest {
public static void main(String[] args) {
// Create a new HashMap with Integer keys and String values
Map<Integer, String> myMap = new HashMap<>();
// Add some key-value pairs to the HashMap
myMap.put(1, "Apple");
myMap.put(2, "Banana");
myMap.put(3, "Cherry");
// Fill in the blanks: Retrieve and print the value for key 2
String valueForKey2 = myMap.get(2);
System.out.println("Value for key 2: " + valueForKey2);
// Fill in the blanks: Check if the HashMap contains key 4
boolean containsKey4 = myMap.containsKey(4);
System.out.println("Does the map contain key 4? " + containsKey4);
// Fill in the blanks: Remove the entry with key 1 from the HashMap
myMap.remove(1);
// Print the updated contents of the HashMap
System.out.println("Updated HashMap:");
for (Map.Entry<Integer, String> entry : myMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
}
}
HashMapTest.main(null)
Value for key 2: Banana
Does the map contain key 4? false
Updated HashMap:
Key: 2, Value: Banana
Key: 3, Value: Cherry
Popcorn HACK 4 - Quiz (Shaurya)
Multiple Choice:
Question 1: Hashing in HashMap
What is the primary purpose of a hash function in a HashMap?
- A) To encrypt the keys
- B) To map keys to corresponding buckets
- C) To validate the keys
- D) To generate random numbers
Answer: B) To map keys to corresponding buckets
The primary purpose of a hash function in a HashMap is to map keys to specific indices (buckets) within the underlying array-based data structure. This mapping allows for efficient retrieval and storage of key-value pairs.
Question 2: Performance of HashMap
What is the time complexity of the get() and put() operations in a well-distributed HashMap?
- A) O(log n)
- B) O(n)
- C) O(1)
- D) O(n^2)
Answer: C) O(1)
In a well-distributed HashMap, both get()
and put()
operations have a time complexity of O(1) on average, assuming a good hash function and minimal collisions. This means that the time taken for these operations is constant and independent of the size of the HashMap.
Free Response:
Question 3: Key and Value Types in HashMap
Describe the types of objects that can be used as keys and values in a HashMap. Additionally, explain the methods that a class should implement if used as a key.
In a HashMap:
- Keys: Any object that implements the
hashCode()
andequals()
methods can be used as keys. These methods are crucial for generating hash codes and comparing keys for equality in hash-based data structures. - Values: Can be any object type, including primitives (which are auto-boxed into their corresponding wrapper classes).
For a class to be used as a key, it should implement:
hashCode()
: Generates a unique hash code for the object.equals(Object obj)
: Compares the object with another for equality.
Question 4: Iteration in HashMap
Provide brief explanations for two methods in HashMap that can be used to iterate over its key-value pairs.
Two methods for iterating over key-value pairs in a HashMap are:
entrySet()
: Returns a set view of the mappings contained in the map. It allows iterating through the entries using a for-each loop or an iterator.forEach()
: Introduced in Java 8, this method accepts a BiConsumer functional interface and can be used to perform an action for each key-value pair in the map.
Question 5: Thread Safety in HashMap
Explain why HashMap is not thread-safe and what issues might arise when multiple threads access the same HashMap instance concurrently. Suggest an alternative class that can be used for concurrent access and explain its benefits.
HashMap is not thread-safe because it’s not synchronized. When multiple threads access the same HashMap concurrently, issues like data corruption or inconsistency might arise due to simultaneous modifications to the HashMap.
An alternative class for concurrent access is ConcurrentHashMap
. It provides thread safety without a significant performance overhead. ConcurrentHashMap
achieves this by dividing the map into segments, allowing multiple threads to operate on different segments concurrently without blocking each other. This improves performance in scenarios where multiple threads need to access the map simultaneously.
HACKS (Shaurya)
1) Finish Popcorn HACKS 2) Develop a Java application that utilizes a HashMap to manage a sports team roster. Each player on the team should have attributes like name, position, and jersey number. The program should enable functionalities such as adding new players, updating player information, and searching for players based on their jersey numbers using the HashMap implementation. 3) Reflection
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Player {
private String name;
private String position;
public Player(String name, String position) {
this.name = name;
this.position = position;
}
public String getName() {
return name;
}
public String getPosition() {
return position;
}
@Override
public String toString() {
return "Name: " + name + ", Position: " + position;
}
}
public class TeamRoster {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Map<Integer, Player> roster = new HashMap<>();
boolean running = true;
while (running) {
System.out.println("\n1. Add a new player");
System.out.println("2. Update player information");
System.out.println("3. Search player by jersey number");
System.out.println("4. Exit");
System.out.print("Enter your choice: ");
int choice = scanner.nextInt();
scanner.nextLine(); // Consume the newline character
switch (choice) {
case 1:
System.out.print("Enter player's name: ");
String playerName = scanner.nextLine();
System.out.print("Enter player's position: ");
String playerPosition = scanner.nextLine();
System.out.print("Enter player's jersey number: ");
int jerseyNumber = scanner.nextInt();
Player newPlayer = new Player(playerName, playerPosition);
roster.put(jerseyNumber, newPlayer);
System.out.println("Player added successfully.");
break;
case 2:
System.out.print("Enter jersey number to update player information: ");
int updateNumber = scanner.nextInt();
if (roster.containsKey(updateNumber)) {
System.out.print("Enter new name: ");
String newName = scanner.next();
System.out.print("Enter new position: ");
String newPosition = scanner.next();
Player updatedPlayer = new Player(newName, newPosition);
roster.put(updateNumber, updatedPlayer);
System.out.println("Player information updated successfully.");
} else {
System.out.println("Player with jersey number " + updateNumber + " does not exist.");
}
break;
case 3:
System.out.print("Enter jersey number to search for player: ");
int searchNumber = scanner.nextInt();
if (roster.containsKey(searchNumber)) {
Player foundPlayer = roster.get(searchNumber);
System.out.println("Player found: " + foundPlayer);
} else {
System.out.println("Player with jersey number " + searchNumber + " not found.");
}
break;
case 4:
running = false;
break;
default:
System.out.println("Invalid choice. Please enter a valid option.");
break;
}
}
System.out.println("Exiting the program. Thank you!");
scanner.close();
}
}
Reflection
- Something I learned from this is that I learned howto initialize key and valus within a hashmap. Before the lis lesson I was quite unsuere about hashmaps as it is a compllex topic that causes however i felt that i was able to complte this hacks mostly on my own wiht some help. initially i struggled with the for each loop as i have some confuion in that area as it is a topic i need to review.