Data Structures and Algorithms(DSA) Concept — Hashmaps — Part 1.

Topics : Hashmap Intro, DSA interview questions based on hashmap.

What is a Hashmap?.

A HashMap, also known as a hash table, is a data structure that provides efficient storage and retrieval of data based on key-value pairs.

It allows for fast access to data because it uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Key Concepts of a HashMap

1. Key-Value Pairs: Each entry in a HashMap consists of a key and a value. Keys are unique identifiers used to retrieve the corresponding value.
2. Hash Function: A function that takes an input (the key) and returns an integer (the hash code). This hash code determines the index at which the key-value pair is stored in the internal array.

How Does a HashMap Work?

1. Initialization: A HashMap starts with an initial array of buckets (default size). Each bucket can hold multiple key-value pairs.
2. Hashing the Key: When a new key-value pair is added, the key is passed through a hash function, which computes an index based on the key.
3. Storing the Entry: The key-value pair is stored in the bucket at the computed index. If the bucket already contains other pairs (collision), the new pair is typically added to the end of a linked list in that bucket.
4. Retrieving a Value: To retrieve a value associated with a key, the key is hashed to find the index, and then the bucket at that index is searched for the key.

Example Code in Java

Here’s a simple example of how a HashMap can be used in Java:

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // Create a HashMap
        HashMap<String, Integer> map = new HashMap<>();

        // Insert key-value pairs
        map.put("apple", 100);
        map.put("banana", 150);
        map.put("orange", 120);

        // Retrieve a value
        int appleValue = map.get("apple");
        System.out.println("Value associated with 'apple': " + appleValue);

        // Check if a key exists
        boolean hasBanana = map.containsKey("banana");
        System.out.println("Contains key 'banana': " + hasBanana);

        // Remove a key-value pair
        map.remove("orange");

        // Iterate over the HashMap
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

lets see some basic interview questions based on hashmaps.

Q 1 . Given N student Id’s and Marks for each student and Q queries of three types.

Type 1 : Given id ,check if id exists or not.

Type 2 : Given id , return mark of that student , if id not present return Id does not exsist.

Type 3 : Given id , Increase the mark of that student by 10 , if id not present no need to update.

Eg 

id    = [  24,  67,  90,  40,  67,  77,  44,  20,  19,  28 ]

marks = [ 678, 890, 400, 364, 700, 435, 729, 850, 600, 296 ]

//[TYPE, ID]
Q = [                       Ans :
     [ 1, 40],              true
     [ 1, 65],              0
     [ 2, 44],              729
     [ 3, 24],              688 
    ] 

Approach 

step 1 : load the id and marks as key vaue pair onto a hash map
step 2 : Iterate Q, check type and search or edit the hashmap accordingly.

Lets see this in code.

import java.util.HashMap;

public class StudentMarks {
    public static void main(int[] id, int[] marks) {
        // Create a HashMap
        HashMap<Integer, Integer> map = new HashMap<>();

        // Insert key-value pairs
        for( int i =0 ; i<id.length ; i++){
            
          map.put(id[i],marks[i]);

        } 

        // Iterate Q 

        for (int i =0 ;i<Q.length; i++) {

             int type = Q[i][0];

             if ( type==1){
                
                boolean hasId = map.containsKey(Q[i][1]);
                if (hasId == true){
                    System.out.println("Contains id" + Q[i][1]);
                }else{
                    System.out.println(" Does not Contains id" + Q[i][1]);
                  }
              }
              else if( type == 2 ){
                    
                boolean hasId = map.containsKey(Q[i][1]);
                if (hasId == true){
                    int mark = map.get(Q[i][1]);
                    System.out.println("Mark of id " + Q[i][1] + "Is "+ mark);
                }else{
                    System.out.println(" Does not Contains id" + Q[i][1]);
                  }
                  
                }
              else if( type == 3){
                    
                boolean hasId = map.containsKey(Q[i][1]);
                if (hasId == true){
                    int mark = map.get(Q[i][1]);
                    mark +=10;
                    map.put(Q[i][1],mark);

                    System.out.println("Updated mark of id " + Q[i][1] + "is "+ mark);
                }else{
                    System.out.println(" Does not Contains id" + Q[i][1]);
                  }
                  
                }         
        }


    }
}

In the next section we will see more complex question based on Hashmaps.

Up next :

Data Structures and Algorithms(DSA) Concept — Hashmaps — Part 2.