Jargon

Think of parking spots painted for specific car sizes. A sedan fits cleanly in a sedan-sized spot. Park a truck across two spots and you’ve blocked traffic.

aligned:                      misaligned:
│────│────│────│              │────│────│────│
0    8    16                   0    4    12
     ▲                              ▲
 fits in 1 spot               straddles 2 — slow

Compilers insert padding between struct fields so every field lands on its proper boundary.

Monthly rent is cheap. Once a year the boiler dies and it’s expensive. Amortized is the per-month cost once you spread the boiler bill back across the year.

A hash table insert is O(1) most of the time. Once in a while, it triggers a full rehash costing O(n). Spread across all the cheap inserts that came before, the average is still O(1). That’s “amortized O(1).”

Different from “average case”. Amortized is a worst-case guarantee on a sequence of operations, not a probabilistic claim about one.

Think of the mail slots at a hotel. Each room has one, but the staff might drop several letters in the same slot if several guests share a name. The slot itself is a bucket; the letters inside form a chain.

buckets[3] ─→ ┌─────┐     ┌─────┐
              │ key │ ──→ │ key │ ──→ NULL
              └─────┘     └─────┘

More buckets than entries → most buckets empty, lookups fast. Fewer buckets than entries → long chains, lookups drag.

malloc(16) gives you 16 bytes of garbage. calloc(4, 4) gives you 16 bytes of zeros. Same size, different starting state.

malloc(16)           calloc(4, 4)
┌─────────────┐      ┌─────────────┐
│ ???garbage? │      │ 0 0 0 0 0 … │
└─────────────┘      └─────────────┘

Useful for pointer arrays where you want every slot to start as NULL, or large buffers you’d otherwise have to memset yourself.

When two keys collide, chaining strings them up in the same bucket and walks the chain on lookup.

buckets[2] ─→ [ "apple" | 3 ] ─→ [ "ant" | 1 ] ─→ NULL

Simple, forgiving of mediocre hash functions, but spends memory on every next pointer. The other common strategy is open addressing, which keeps entries inside the bucket array itself.

Two different strings, same hash slot. Like two different people with different last names sharing a mailbox on a shared apartment line. The postbox doesn’t care. It just delivers both.

A good hash spreads keys evenly, so collisions are rare. A bad hash piles everything into a few slots and turns O(1) lookups into a linear walk.

Two main strategies for dealing with collisions: chaining (each bucket is a linked list) and open addressing (probe the next slot).

Like a business card for a shop that closed. The address is real, but nothing useful is there anymore. Dereference it and you get a use-after-free.

Defensive move: set the pointer to NULL right after free, so a later mistake crashes loudly instead of silently reading garbage.

Like returning a rented car twice. The rental company’s records break. The next customer ends up “renting” a car already handed to someone else.

Usually crashes somewhere far away from the actual bug, which is what makes it painful to track down.

Picture writing the number 305,419,896 as 12 34 56 78 or 78 56 34 12. Same number, opposite byte order in memory.

little-endian (x86, ARM64 usual):   78 56 34 12
big-endian    (network order):       12 34 56 78

Almost every CPU you’ll meet is little-endian. Network protocols insist on big-endian, which is why htonl and ntohl exist.

Hand the key back to the warehouse. After free, the space belongs to someone else. Still reading through the old key is how programs corrupt themselves.

malloc ──> [ . . . . ]   got it
free   ──> [         ]   gave it back, now stay away

Like a hotel housekeeper: you leave your room, they tidy it, the room is ready for the next guest. Java, Go, Python, JavaScript, C# all run one while your program executes.

Trade-off: convenience vs. tiny unpredictable pauses while the cleaner works.

your code        GC
  │              │
  ▼              ▼
allocate      look around,
  …           sweep what's
  …           nobody using

Like a coat-check with numbered hooks. You hand over a coat (key), a machine spits out a hook number (hash), you hang it there (bucket). Two coats end up on the same hook? Chain them.

key ─→ hash ─→ index ─→ buckets[index]
                         └─→ [key|val] → [key|val] → NULL

The dict, the map, the object in every language. Almost always this underneath.

Not a pile — a warehouse. You request a spot, you get a key. Forget to return the key, the space is lost forever.

  malloc ──> [ . . . . ]   got a slot
                  │
                  ▼
              use it
                  │
                  ▼
  free   ──> [         ]   returned

Like a scavenger hunt: each clue tells you where to find the next clue. Lose one, and you lose everything after it.

head
 │
 ▼
┌────┐     ┌────┐     ┌────┐
│ 10 │──→  │ 20 │──→  │ 30 │──→ NULL
└────┘     └────┘     └────┘

Cheap to insert at the head. Expensive to jump to the middle — you have to walk from the start.

A gym with 100 lockers and 50 members is fine. 100 lockers, 90 members. Now everyone’s waiting for the same row. The load factor tells you when to build a bigger gym.

load_factor = entries / buckets

0.25 → lots of empty buckets, great lookup speed
0.75 → the usual resize trigger
1.50 → chains 1–2 long on average; lookups crawl

When it crosses the threshold, the table grows and everything is rehashed into the bigger array.

Short for “memory allocate.” Like renting a storage unit: you tell the warehouse how many square feet, they hand you a key. Lose the key, the space is lost forever.

malloc(16)  ──>  [ . . . . . . ]   16 bytes, all yours
                  ▲
                  key (pointer)

Like renting storage units and losing the keys one by one. The warehouse stays full, you can’t reach any of it, and eventually there’s nowhere to put new stuff.

Short programs get away with it. Servers that run for months don’t.

The basic building block. In a linked list, a node carries one value and one next pointer. In a tree, two pointers (left and right). In a graph, any number.

┌───────┐
│ value │     what it holds
├───────┤
│ next ─┼──→  where to go from here
└───────┘

Like writing “N/A” on a form. It marks a pointer as empty on purpose, so you can tell “not set yet” apart from “points at junk.”

Dereferencing a NULL pointer — trying to read what’s at address zero — crashes the program on every real operating system. That crash is called a segfault.

The opposite of chaining. No linked lists, just one big array. If the slot for your key is taken by someone else, walk forward until you find an empty one (linear probing) or jump in a pattern (quadratic probing, double hashing).

want to place "ant" at index 3
buckets:  [ . . . [apple] [ . ] . . . ]
index:     0 1 2    3       4   5 6 7

index 3 taken → try 4 → empty → place "ant" there

Better cache behaviour than chaining, trickier deletion (you can’t just blank a slot, you’d break the probe chain). Python’s dict uses it.

The compiler tracks who holds what at compile time and refuses to build if the rules are broken. No garbage collector needed, no manual free, no use-after-free — the code simply won’t compile.

Trade-off: steeper learning curve (the “borrow checker” gets in your way until you internalise it), zero runtime cost once it does.

Like gaps on a bookshelf to make sure the next book starts at a neat edge. Wasted space, but the shelf works faster.

struct:   │ int (4 B) │ pad (4 B) │ pointer (8 B) │
                         ▲
                    nobody uses these bytes — they exist
                    so the pointer lands on offset 8

Think of it as a house number. The number isn’t the house — it just tells you where to find it.

x ──> [ 42 ]
      0x1a2b

x holds the address.
0x1a2b is where 42 actually lives.

Like a library tracking how many people have borrowed a book. When the last copy comes back, the book goes to storage.

Used by Python (CPython), Swift, Objective-C. Weakness: two objects pointing at each other trap each other’s counts above zero forever (a “cycle”), so these runtimes usually bolt on a small cycle detector.

hash(key) % 16 and hash(key) % 32 are almost always different buckets. When the array grows, every entry has to be placed again in its new home.

old capacity 8:                  new capacity 16:
buckets[3] → "apple"    ──→      buckets[11] → "apple"
                                 (index changes because capacity changed)

Expensive. O(n). But you only pay it when the table crosses the load factor threshold, so averaged across all inserts, each insert is still O(1). See amortized.

Every program gets a set of regions it’s allowed to read and write. Step outside — dereferencing NULL, reading a freed chunk the OS has reclaimed, running off the end of an array — and the OS pulls the plug.

your program  →  reads 0x0
                     │
                     ▼
               OS: "nope"  →  CRASH

The first sign something is deeply wrong.

Like stacking plates. You can’t grab the bottom plate without lifting the ones above it.

push ──>  ┌───┐
          │ C │  <- top
          ├───┤
          │ B │
          ├───┤
          │ A │  <- bottom
          └───┘
                <-- pop takes C first

Call a function, push a box onto the stack. Inside the box: your locals, the return address, the arguments. Function returns, the box pops off, memory reclaimed for free — no allocator involved.

call f()    call g() from inside f()
┌──────┐    ┌──────┐
│  f   │    │  g   │  ← new frame on top
└──────┘    ├──────┤
            │  f   │
            └──────┘

strdup("hello") is malloc(6) + strcpy in one call. Use it when you’re storing a caller’s string and don’t trust them not to free it or overwrite it behind your back.

char *copy = strdup(user_input);   // owns its own buffer
free(copy);                        // forget this, leak

If the input disappears, your copy still stands. Short POSIX function, but not strictly C99. Some strict compilers need -D_POSIX_C_SOURCE=200809L to see it.

Like a form with labelled boxes: name, age, email. Fill in each box, carry the form around, pass it to functions.

struct point {
    int x;
    int y;
};

Memory-wise it’s the fields laid out one after the other, with padding between them if alignment requires it.

Abbreviated UB. Things like reading uninitialised memory, signed integer overflow, or dereferencing a freed pointer. The compiler is allowed to assume you never do these, and will sometimes optimise your code in ways that make no sense once you do.

Rule of thumb: if you’re not sure whether something is UB, it probably is. Check before you ship.

Like still using the storage unit after you handed back the key. Someone else has it now. What you read is whatever they left behind.

free(p)             then later…
 │                       │
 ▼                       ▼
[released]           read *p → garbage,
                         or someone else's data

Like a surveillance camera on every malloc and free. Slower than normal execution (10× or so), but it catches bugs that would otherwise surface months later in production.

$ valgrind --leak-check=full ./myprog
...
definitely lost: 48 bytes in 2 blocks

Linux-native. On macOS use leaks or AddressSanitizer.