Key differences between HashMap and TreeMap in Java

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.

error: Content is protected !!