Complexity Note

Hash Map Basics

Both arrays and hash maps can give O(1) lookup. The difference is what you know: an array finds by position, while a hash map finds by key.

The Confusing Part

Both arrays and hash maps can give O(1) lookup. A hash map is not simply “faster than an array.”

The real difference is what information you know when searching.

Array → know the position / index
Hash Map → know the key / name / ID

Array = Find by Position

names := []string{"Alice", "Bob", "Charlie"}
index     0         1         2
          ↓         ↓         ↓
value   Alice      Bob     Charlie

“Give me the person at index 1.”

names[1] // "Bob"

You know the exact position, so array index lookup is O(1).

“At which position is Charlie?”

Alice   ❌
Bob     ❌
Charlie ✅

You know the value but not its position. The array may check every item, so this is O(n).

Hash Map = Find by Key

ages := map[string]int{
    "Alice":   20,
    "Bob":     25,
    "Charlie": 30,
}
key          value

Alice   →     20
Bob     →     25
Charlie →     30

“What is Charlie's age?”

ages["Charlie"] // 30

You already know the key, "Charlie". Hash-map lookup by a known key is O(1) on average.

Core Difference
ARRAY
index → value

0 → Alice
1 → Bob
2 → Charlie

HASH MAP
key → value

"Alice"   → 20
"Bob"     → 25
"Charlie" → 30

One Example That Makes It Click

Suppose you store scores in an array:

scores := []int{90, 75, 88}
0 means Alice
1 means Bob
2 means Charlie

If you know Bob is at index 1, scores[1] gives 75. But if you only know "Bob", this is impossible:

scores["Bob"] // ❌ arrays need a numeric index

A hash map stores the name directly as the key:

scores := map[string]int{
    "Alice":   90,
    "Bob":     75,
    "Charlie": 88,
}

scores["Bob"] // 75

That is why hash maps exist: they give fast lookup when you know a key instead of a numeric position.

Key and Value

Key

The name used to find something.

"Charlie"

Value

The data stored under that key.

30

Pair

The key and value together.

"Charlie" → 30

A key is unique inside one map. Assigning the same key again replaces its previous value.

Basic Operations

Insert

Add a new key and value.

Read

Get the value stored by a key.

Update

Assign a new value to an existing key.

Exists?

Check whether a key is present.

Delete

Remove a key and its value.

👉 Insert, read, update, existence check, and delete are O(1) on average.

Go Quick Reference — Hash Map

ages := make(map[string]int)

// Insert
ages["Charlie"] = 30

// Read and check existence
age, exists := ages["Charlie"]
if exists {
    fmt.Println(age) // 30
}

// Update: same key, new value
ages["Charlie"] = 31

// Delete
delete(ages, "Charlie")

Use the two-value lookup when a missing key must be different from a stored zero value.

value, exists := ages[name]

// exists == false → key is missing
// exists == true  → key is present

When to Use It

Use a hash map when

  • • You know a name or ID and need its value.
  • • You repeatedly check whether a key exists.
  • • You store a count or setting by name.

Prefer an array when

  • • Position and order are important.
  • • Numeric indexes are enough.
  • • You want compact sequential storage.

Production Thinking

A student system can use a student ID as the key and the student record as the value. A cache can use a request ID as the key and previously computed data as the value.

Production warning: hash maps use extra memory, do not guarantee sorted order, and O(1) is an average—not an absolute worst-case promise.

Remember This

Do I know the POSITION?
Yes → Array
      arr[2]

Do I know a KEY / NAME / ID?
Yes → Hash Map
      map["Bob"]

Array:
Known index → O(1)
Search for value → O(n)

Hash Map:
Known key → O(1) average

💡 Golden Rule: Array gives fast lookup by index. Hash Map gives fast lookup by key.

Next: understand Hash Map vs Hash Set →