HashMaps in Java

HashMaps are a fundamental data structure in Java and are widely used in Leetcode problems. They store key-value pairs and provide efficient lookup, insertion, and deletion operations.

Table of Contents

1. HashMap Basics
2. Common HashMap Operations
3. Common Leetcode Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

HashMap Basics

• Definition: A HashMap is a collection that stores key-value pairs. It uses hashing to compute an index into an array of buckets or slots, from which the desired value can be found.

• Declaration:

  HashMap<Integer, String> map = new HashMap<>();

• Key Characteristics:

  • Keys are unique.
  • Allows one null key and multiple null values.
  • Unordered collection (no guarantee of order).

Common HashMap Operations

1. Inserting a Key-Value Pair

• Method: put(K key, V value)

• Example:

  map.put(1, "Apple");
  map.put(2, "Banana");

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

2. Accessing a Value by Key

• Method: get(K key)

• Example:

  String value = map.get(1); // value = "Apple"

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

3. Checking if a Key Exists

• Method: containsKey(K key)

• Example:

  boolean exists = map.containsKey(1); // exists = true

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

4. Removing a Key-Value Pair

• Method: remove(K key)

• Example:

  map.remove(1); // Removes the key 1 and its value

• Time Complexity: O(1) (average case), O(n) (worst case due to collisions)

• Space Complexity: O(1)

5. Iterating Over a HashMap

• Using KeySet:

  for (Integer key : map.keySet()) {
      System.out.println("Key: " + key + ", Value: " + map.get(key));
  }

• Using EntrySet:

  for (Map.Entry<Integer, String> entry : map.entrySet()) {
      System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
  }

• Time Complexity: O(n)

• Space Complexity: O(1)

6. Size of the HashMap

• Method: size()

• Example:

  int size = map.size(); // size = 1

• Time Complexity: O(1)

• Space Complexity: O(1)

7. Checking if the HashMap is Empty

• Method: isEmpty()

• Example:

  boolean isEmpty = map.isEmpty(); // isEmpty = false

• Time Complexity: O(1)

• Space Complexity: O(1)

Common Leetcode Patterns

1. Frequency Counting

• Used for problems like counting character frequencies, finding duplicates, etc.

• Example:

  HashMap<Character, Integer> freqMap = new HashMap<>();
  for (char c : s.toCharArray()) {
      freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
  }

• Related Questions:

  • Valid Anagram
  • First Unique Character in a String
  • Group Anagrams

2. Two-Sum and Variants

• Used for problems like finding pairs that sum to a target, checking for complements, etc.

• Example:

  HashMap<Integer, Integer> map = new HashMap<>();
  for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (map.containsKey(complement)) {
          return new int[]{map.get(complement), i};
      }
      map.put(nums[i], i);
  }

• Related Questions:

  • Two Sum
  • 3Sum
  • 4Sum

3. Subarray Sum Equals K

• Used for problems like finding subarrays with a given sum, prefix sum problems, etc.

• Example:

  HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
  prefixSumMap.put(0, 1);
  int sum = 0, count = 0;
  for (int num : nums) {
      sum += num;
      if (prefixSumMap.containsKey(sum - k)) {
          count += prefixSumMap.get(sum - k);
      }
      prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0) + 1);
  }
  return count;

• Related Questions:

  • Subarray Sum Equals K
  • Continuous Subarray Sum

4. Sliding Window with HashMap

• Used for problems like longest substring without repeating characters, minimum window substring, etc.

• Example:

  HashMap<Character, Integer> map = new HashMap<>();
  int left = 0, maxLen = 0;
  for (int right = 0; right < s.length(); right++) {
      char c = s.charAt(right);
      if (map.containsKey(c)) {
          left = Math.max(left, map.get(c) + 1);
      }
      map.put(c, right);
      maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;

• Related Questions:

  • Longest Substring Without Repeating Characters
  • Minimum Window Substring

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Insert (put())	O(1) (average)	O(1)
Access (get())	O(1) (average)	O(1)
Contains Key (containsKey())	O(1) (average)	O(1)
Remove (remove())	O(1) (average)	O(1)
Iteration	O(n)	O(1)
Size (size())	O(1)	O(1)
Is Empty (isEmpty())	O(1)	O(1)

Related Leetcode Questions

Easy

1. Two Sum
2. Valid Anagram
3. First Unique Character in a String

Medium

1. Group Anagrams
2. Subarray Sum Equals K
3. Longest Substring Without Repeating Characters

Hard

1. Minimum Window Substring
2. LRU Cache
3. LFU Cache