Hash Map vs Array vs Linked List for Lookup in DSA Java - Trade-offs & Analysis

Mental Model

Lookup means finding a value quickly by its key or position. Different structures store data differently, affecting how fast we find things.

Analogy: Imagine looking for a book in a library: an array is like books on a shelf in order, a linked list is like books chained hand-to-hand, and a hash map is like a librarian who knows exactly where each book is.

Array: [0]1 -> [1]2 -> [2]3 -> null
LinkedList: 1 -> 2 -> 3 -> null
HashMap: {key1 -> val1, key2 -> val2, key3 -> val3}

Dry Run Walkthrough

Input: Data: values 1, 2, 3 stored in Array, Linked List, and Hash Map; lookup key/index 2

Goal: Compare how each structure finds the value at key/index 2

Step 1: Lookup index 2 in Array directly

[0]1 -> [1]2 -> [2]3 -> null

Why: Array allows direct access by index, so we get value 3 immediately

Step 2: Traverse Linked List from head to find 3rd element

1 -> 2 -> [3] -> null

Why: Linked List requires moving node by node until we reach index 2

Step 3: Use Hash function on key 2 to find bucket and retrieve value

{key1 -> val1, key2 -> val2, key3 -> val3}

Why: Hash Map uses key to jump directly to value without scanning all

Result:

Array: value 3 found instantly at index 2
Linked List: value 3 found after 3 steps
Hash Map: value val2 found instantly by key2

Annotated Code

DSA Java

import java.util.*;

public class LookupComparison {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; this.next = null; }
    }

    // Lookup in Array
    static int lookupArray(int[] arr, int index) {
        if (index < 0 || index >= arr.length) return -1; // guard
        return arr[index];
    }

    // Lookup in Linked List
    static int lookupLinkedList(Node head, int index) {
        Node curr = head;
        int count = 0;
        while (curr != null) {
            if (count == index) return curr.val; // found
            curr = curr.next; // advance
            count++;
        }
        return -1; // not found
    }

    // Lookup in Hash Map
    static String lookupHashMap(Map<Integer, String> map, int key) {
        return map.getOrDefault(key, "Not found");
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3};

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        Map<Integer, String> hashMap = new HashMap<>();
        hashMap.put(1, "val1");
        hashMap.put(2, "val2");
        hashMap.put(3, "val3");

        int indexToLookup = 2;

        System.out.println("Array lookup at index 2: " + lookupArray(array, indexToLookup));
        System.out.println("Linked List lookup at index 2: " + lookupLinkedList(head, indexToLookup));
        System.out.println("Hash Map lookup for key 2: " + lookupHashMap(hashMap, 2));
    }
}

if (index < 0 || index >= arr.length) return -1; // guard

check index bounds to avoid errors

return arr[index];

direct access to array element by index

while (curr != null) {

traverse linked list nodes one by one

if (count == index) return curr.val; // found

return value when target index reached

curr = curr.next; // advance

move to next node in linked list

return map.getOrDefault(key, "Not found");

retrieve value by key from hash map or default

Output

Array lookup at index 2: 3

Linked List lookup at index 2: 3

Hash Map lookup for key 2: val2

Complexity Analysis

Time: Array: O(1) because direct index access; Linked List: O(n) because traversal needed; Hash Map: O(1) average due to hashing

Space: Array and Linked List use O(n) space for n elements; Hash Map uses O(n) plus extra for hashing overhead

vs Alternative: Array is fastest for index lookup but fixed size; Linked List is slow for lookup but flexible size; Hash Map is fast for key lookup but uses more memory

Edge Cases

Lookup index/key out of range or missing

Array returns -1; Linked List returns -1; Hash Map returns 'Not found'

DSA Java

if (index < 0 || index >= arr.length) return -1; // guard

Empty data structures

All return not found or -1 safely

DSA Java

while (curr != null) { ... } handles empty linked list

When to Use This Pattern

When a problem asks for fast lookup by key or index, consider if array, linked list, or hash map fits best based on speed and flexibility needs.

Common Mistakes

Mistake: Trying to access linked list by index directly without traversal
Fix: Traverse node by node until reaching the target index

Mistake: Assuming hash map lookup is always O(1) without considering collisions
Fix: Remember hash map average is O(1), worst case can degrade; choose good hash functions

Summary

Compares how array, linked list, and hash map find values by index or key.

Use array for fixed-size fast index access, linked list for flexible size but slower lookup, and hash map for fast key-based lookup.

The key insight is that data structure layout affects how quickly you can find data.

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