HashMap in Java
HashMap in Java is a part of the Java Collections Framework and implements the Map interface. It stores data in key-value pairs and uses a hashing technique to compute an index where the value is stored. This allows for fast retrieval of data based on the key, as it directly maps keys to values. HashMap is unordered, meaning it does not maintain the order of insertion, and it allows one null key and multiple null values. This class is not synchronized, making it unsuitable for concurrent use without external synchronization. HashMap is widely used due to its efficiency in storing and retrieving data, where the average time complexity for put and get operations is O(1) under normal conditions.
Functions of HashMap in Java:
-
put(K key, V value):
Associates a specific value with a specific key in the HashMap. If the map previously contained a mapping for the key, the old value is replaced.
-
get(Object key):
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
-
remove(Object key):
Removes the mapping for a key from this map if it is present, returning the value to which this map previously associated the key, or null if the map contained no mapping for the key.
-
containsKey(Object key):
Checks if the map contains a mapping for the specified key, returning true if it is present and false otherwise.
-
containsValue(Object value):
Checks if the map maps one or more keys to the specified value. Returns true if at least one such mapping exists.
- keySet():
Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
- values():
Returns a collection view of the values contained in this map. This provides a convenient way to access all values stored in the map.
- clear():
Removes all of the mappings from this map. The map will be empty after this call returns.
Example of HashMap in Java:
This example demonstrates how to create a HashMap, add entries to it, retrieve values, and iterate through the keys and values.
import java.util.HashMap;
import java.util.Map;
public class HashMapExample {
public static void main(String[] args) {
// Create a HashMap
HashMap<String, Integer> map = new HashMap<>();
// Adding elements to the map
map.put(“Alice”, 30);
map.put(“Bob”, 25);
map.put(“Charlie”, 35);
// Displaying the size of the map
System.out.println(“Total entries in map: ” + map.size());
// Getting a value
Integer age = map.get(“Alice”);
if (age != null) {
System.out.println(“Alice’s age: ” + age);
}
// Iterate over keys
System.out.println(“List of names:”);
for (String key : map.keySet()) {
System.out.println(key);
}
// Iterate over values
System.out.println(“List of ages:”);
for (Integer value : map.values()) {
System.out.println(value);
}
// Iterate over key-value pairs
System.out.println(“Entries in map:”);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ” : ” + entry.getValue());
}
// Remove an entry
map.remove(“Bob”);
System.out.println(“Map after removing Bob: ” + map);
}
}
TreeMap in Java
TreeMap in Java is a Map implementation that organizes its entries based on the natural ordering of its keys or via a custom Comparator provided at map creation. Unlike HashMap, TreeMap is sorted according to the natural order of its keys or by a Comparator, making it an excellent choice for applications where order needs to be maintained. It implements the NavigableMap interface and extends AbstractMap. Each key-value pair is stored as an entry in a red-black tree, which balances itself to maintain a consistent order. As a result, operations like put, get, and remove have a time complexity of O(log n). TreeMap does not allow null keys but can have null values and ensures that keys are in a predictable order.
Functions of TreeMap in Java:
-
put(K key, V value):
Inserts a key-value pair into the map. If the map previously contained a key, the old value is replaced by the specified value.
-
get(Object key):
Returns the value associated with the specified key, or null if the map contains no mapping for the key.
-
remove(Object key):
Removes the key-value pair associated with the specified key if it is present in the map, returning the value to which this map previously associated the key, or null if the map contained no mapping for the key.
- firstKey():
Returns the first (lowest) key currently in this map.
- lastKey():
Returns the last (highest) key currently in this map.
- subMap(K fromKey, K toKey):
Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
-
headMap(K toKey):
Returns a view of the portion of this map whose keys are strictly less than toKey.
-
tailMap(K fromKey):
Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
- comparator():
Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
- entrySet():
Returns a set view of the mappings contained in this map, which is useful for iterating over key-value pairs.
- keySet():
Returns a set view of the keys contained in this map.
- values():
Returns a collection view of the values contained in this map.
- ceilingKey(K key):
Returns the least key greater than or equal to the given key, or null if there is no such key.
-
floorKey(K key):
Returns the greatest key less than or equal to the given key, or null if there is no such key.
Example of TreeMap in Java:
Here’s an example demonstrating the usage of TreeMap in Java. In this example, we create a TreeMap to store student names as keys and their corresponding scores as values. We then add entries to the map, retrieve values based on keys, and demonstrate how the map maintains natural ordering of keys.
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
// Creating a TreeMap to store student names and scores
TreeMap<String, Integer> studentScores = new TreeMap<>();
// Adding entries to the TreeMap
studentScores.put(“Alice”, 85);
studentScores.put(“Bob”, 90);
studentScores.put(“Charlie”, 80);
studentScores.put(“David”, 95);
// Displaying the TreeMap
System.out.println(“Student scores: ” + studentScores);
// Retrieving and displaying score for a specific student
String studentName = “Bob”;
int score = studentScores.get(studentName);
System.out.println(studentName + “‘s score: ” + score);
// Demonstrating natural ordering of keys
System.out.println(“First student: ” + studentScores.firstKey());
System.out.println(“Last student: ” + studentScores.lastKey());
// Displaying all students with scores greater than or equal to Charlie
System.out.println(“Students with scores greater than or equal to Charlie:”);
studentScores.tailMap(“Charlie”).forEach((name, s) -> System.out.println(name + “: ” + s));
}
}
Output:
Student scores: {Alice=85, Bob=90, Charlie=80, David=95}
Bob’s score: 90
First student: Alice
Last student: David
Students with scores greater than or equal to Charlie:
Charlie: 80
David: 95
In this example:
- We create a TreeMap called studentScores to store student names and their corresponding scores.
- We add entries to the map using the put()
- We retrieve and display the score for a specific student using the get()
- We demonstrate the natural ordering of keys by retrieving the first and last student names using firstKey() and lastKey() methods, respectively.
- We display all students with scores greater than or equal to a certain threshold (Charlie) using the tailMap()
Key differences between HashMap and TreeMap in Java
Aspect | HashMap | TreeMap |
Ordering | No order | Sorted order |
Implementation | Hash table | Red-Black tree |
Null keys/values | Allows one null key, multiple null values | Only allows null values |
Performance (get/put/remove) | Constant time, average O(1) | Logarithmic time, O(log n) |
Sorting | Does not sort | Automatically sorts by natural order |
Iterator order | Unpredictable order | Sorted order |
Concurrency | Faster, supports unsynchronized concurrent access | Slower, no concurrent modifications |
Memory usage | Less memory efficient | More memory efficient due to structure |
API Methods | Basic HashMap operations | NavigableMap methods, sorting methods |
Map head/tail operations | Not supported | Supports headMap, tailMap, subMap |
First/Last keys | Not applicable | Provides firstKey(), lastKey() methods |
Interface | Implements Map | Implements NavigableMap, SortedMap |
Key Comparison | Uses equals() method | Uses compareTo() or Comparator |
Best use case | Rapid look-up without ordering | Sorted data manipulation |
Complexity | Simpler implementation | More complex due to sorting requirements |
Key Similarities between HashMap and TreeMap in Java
-
Both Implement Map Interface:
Both HashMap and TreeMap implement the Java Map interface, meaning they both provide a basic contract for map operations such as adding, removing, and containing keys.
-
Key-Value Storage:
Both structures store data as key-value pairs, which helps in associating values with keys for efficient retrieval.
-
Generics Support:
Both maps support generics, allowing them to store keys and values of any types while ensuring type safety.
-
Access to Entries:
Both provide access to their elements via key set, entry set, and values collection, allowing iterations over keys, values, or both.
-
Null Values:
Both HashMap and TreeMap allow storing null values (though TreeMap requires a compatible comparator that can handle null if used as keys).
- Modifiability:
Both maps are dynamically modifiable; you can add new key-value pairs, update existing ones, and remove pairs at runtime.
- Non-Synchronization:
Neither HashMap nor TreeMap is synchronized by default, meaning they are not suitable for use in multiple-thread environments unless externally synchronized.
-
Clonable and Serializable:
Both HashMap and TreeMap implement the Cloneable and Serializable interfaces, which makes them capable of being cloned and serialized respectively.