Hash Map vs Array vs Linked List for Lookup in DSA Java - Key Differences

Recall & Review

beginner

What is the average time complexity for lookup in a Hash Map?

The average time complexity for lookup in a Hash Map is O(1), meaning it can find an element very quickly using a key.

beginner

How does lookup work in an Array?

Lookup in an Array is O(1) if you know the index because you can directly access the element. But if you search by value without index, it is O(n) because you may need to check each element.

beginner

Why is lookup in a Linked List slower than in an Array or Hash Map?

Lookup in a Linked List is O(n) because you must start at the head and check each node one by one until you find the value or reach the end.

intermediate

What is a key advantage of using a Hash Map over an Array or Linked List for lookup?

A Hash Map allows fast lookup by key with average time complexity O(1), which is much faster than searching through an Array or Linked List when you don't know the index.

intermediate

When might you prefer using an Array over a Hash Map or Linked List for lookup?

You might prefer an Array when you have fixed-size data and know the index of elements, allowing very fast direct access with O(1) time complexity.

What is the average time complexity of lookup in a Hash Map?

A O(1)

B O(n)

C O(log n)

D O(n log n)

Hash Maps provide average O(1) lookup time by using keys and hashing.

If you want to find a value in an unsorted Array without knowing the index, what is the time complexity?

A O(n)

B O(1)

C O(log n)

D O(n^2)

You must check each element until you find the value, so it takes O(n) time.

Which data structure requires checking nodes one by one for lookup?

A Hash Map

B Array

C Linked List

D Binary Search Tree

Linked Lists require sequential traversal, so lookup is O(n).

Which data structure is best for fast lookup by key?

A Stack

B Linked List

C Array

D Hash Map

Hash Maps use keys and hashing to provide fast O(1) lookup.

When is an Array lookup fastest?

A When searching by value

B When index is known

C When data is unsorted

D When data is linked

Knowing the index allows direct access in O(1) time.

Explain the differences in lookup time complexity between Hash Map, Array, and Linked List.

Think about how each data structure finds an element.

Describe scenarios where you would choose an Array, Linked List, or Hash Map for lookup operations.

Consider speed and type of access needed.

Practice

1. Which data structure provides the fastest average lookup time for a key-value pair?

easy

A. Hash Map

B. Array

C. Linked List

D. Stack

Solution

1. Step 1: Understand lookup times for each data structure

   Hash Map uses hashing to find keys quickly, usually in constant time O(1). Arrays require searching by index or linear search for values, O(1) for index but O(n) for value lookup. Linked Lists require linear search O(n).

2. Step 2: Compare average lookup times

   Hash Map average lookup is O(1), Array lookup by index is O(1) but by value is O(n), Linked List lookup is O(n).

3. Final Answer:

   Hash Map -> Option A

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map uses keys for O(1) lookup, arrays and lists do not [OK]

Common Mistakes:

• Confusing array index lookup with value lookup
• Assuming linked list lookup is fast
• Thinking stack is for key-value lookup

2. Which of the following is the correct way to declare a HashMap in Java for storing Integer keys and String values?

easy

A. HashMap map = new HashMap();

B. HashMap map = new HashMap<>();

C. HashMap map = new HashMap();

D. HashMap map = new HashMap<>();

Solution

1. Step 1: Check generic types in HashMap declaration

   Java uses wrapper classes like Integer, not primitive int, for generics. So HashMap is invalid.

2. Step 2: Check constructor syntax

   Using diamond operator <> is correct for type inference. HashMap map = new HashMap<>(); is valid and preferred.

3. Final Answer:

   HashMap map = new HashMap<>(); -> Option D

4. Quick Check:

   Correct generic syntax = HashMap map = new HashMap<>(); [OK]

Hint: Use wrapper classes and diamond operator for HashMap declaration [OK]

Common Mistakes:

• Using primitive types like int in generics
• Omitting diamond operator causing raw type warning
• Swapping key and value types in constructor

3. What will be the output of the following Java code snippet?

import java.util.*;
public class Test {
  public static void main(String[] args) {
    List<Integer> list = Arrays.asList(10, 20, 30);
    Map map = new HashMap<>();
    for (int i = 0; i < list.size(); i++) {
      map.put(list.get(i), "Value" + i);
    }
    System.out.println(map.get(20));
  }
}

medium

A. Value0

B. 20

C. Value1

D. null

Solution

1. Step 1: Understand the loop and map population

   The loop runs i from 0 to 2. For each i, map puts key list.get(i) and value "Value" + i. So keys 10, 20, 30 map to "Value0", "Value1", "Value2" respectively.

2. Step 2: Check the output of map.get(20)

   Key 20 maps to "Value1" so printing map.get(20) outputs "Value1".

3. Final Answer:

   Value1 -> Option C

4. Quick Check:

   map.get(20) = Value1 [OK]

Hint: Map keys match list values; index i forms value string [OK]

Common Mistakes:

• Confusing key with value in map.get()
• Assuming map stores values in insertion order
• Expecting numeric output instead of string

4. Identify the error in the following Java code snippet that tries to find if a value exists in a LinkedList:

LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add("banana");
if (list.contains("orange")) {
  System.out.println("Found orange");
} else {
  System.out.println("Orange not found");
}

medium

A. No error; code works correctly

B. LinkedList does not have contains() method

C. Must use list.search("orange") instead of contains()

D. Contains method only works for integers

Solution

1. Step 1: Check LinkedList methods

   Java's LinkedList class inherits from Collection and has a contains() method to check if an element exists.

2. Step 2: Verify code logic

   The code adds "apple" and "banana" to list, then checks if "orange" is contained. Since "orange" is not in list, it prints "Orange not found". This is correct behavior.

3. Final Answer:

   No error; code works correctly -> Option A

4. Quick Check:

   LinkedList.contains() works as expected [OK]

Hint: LinkedList inherits contains() from Collection interface [OK]

Common Mistakes:

• Thinking contains() is not available for LinkedList
• Using non-existent search() method
• Assuming contains() only works for integers

5. You need to store a large dataset of user IDs (integers) and their names (strings) for fast lookup by user ID. Which data structure is best and why? Choose the best option considering lookup speed, memory, and insertion time.

hard

A. Array, because it provides O(1) lookup by index

B. Hash Map, because it provides average O(1) lookup by key

C. Linked List, because it allows easy insertion and deletion

D. Binary Search Tree, because it keeps data sorted

Solution

1. Step 1: Analyze lookup requirements

   We need fast lookup by user ID (key). Array lookup by index is O(1), but user IDs are not guaranteed to be continuous indices.

2. Step 2: Compare data structures for key-based lookup

   Linked List lookup is O(n), too slow. Binary Search Tree lookup is O(log n), slower than Hash Map average O(1). Hash Map stores key-value pairs with fast average lookup.

3. Step 3: Consider insertion and memory

   Hash Map has good insertion time and reasonable memory overhead. Array wastes memory if IDs are sparse. BST keeps data sorted but slower lookup.

4. Final Answer:

   Hash Map, because it provides average O(1) lookup by key -> Option B

5. Quick Check:

   Best for fast key lookup = Hash Map [OK]

Hint: Use Hash Map for fast key-based lookup, not arrays or lists [OK]

Common Mistakes:

• Choosing array assuming user IDs are continuous
• Ignoring lookup time differences
• Preferring BST for speed over Hash Map