Data Structures

Hash Lookup

A tiny table can scan slots to find the value stored for a key.

key slot Each occupied slot stores a key and a matching value.
miss value The lookup keeps a fallback value when no slot contains the target key.

Hash Lookup

target
hash_lookup.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int main(void) {
    int target = 7;
    int keys[4] = {3, 7, 11, 0};
    int values[4] = {30, 70, 110, 0};
    int found = -1;

    for (int i = 0; i < 4; i++) {
        if (keys[i] == target) {
            found = values[i];
        }
    }

    printf("found=%d\n", found);
    return 0;
}

#include <stdio.h>

int main(void) {
    int target = 3;
    int keys[4] = {3, 7, 11, 0};
    int values[4] = {30, 70, 110, 0};
    int found = -1;

    for (int i = 0; i < 4; i++) {
        if (keys[i] == target) {
            found = values[i];
        }
    }

    printf("found=%d\n", found);
    return 0;
}

#include <stdio.h>

int main(void) {
    int target = 9;
    int keys[4] = {3, 7, 11, 0};
    int values[4] = {30, 70, 110, 0};
    int found = -1;

    for (int i = 0; i < 4; i++) {
        if (keys[i] == target) {
            found = values[i];
        }
    }

    printf("found=%d\n", found);
    return 0;
}

  1. target ← 7, keys ← ⟨addr A⟩, values ← ⟨addr B⟩, found ← -1

    3int main(void) {4    int target→ 7 = 7; //@target=3, 95    int keys→ ⟨addr A⟩[4] = {3, 7, 11, 0};6    int values→ ⟨addr B⟩[4] = {30, 70, 110, 0};7    int found→ -1 = -1;

  2. for (int i = 0; i < 4; i++)

    pass 1 of 4
    9for (int i0 = 0; i < 4; i++) {10    if (keys[i] == target) {
    All 4 passes — pass 1 is the card above
    passikeys[i]targetvalues[i]found
    10————
    217770-1 → 70
    32————
    43————

  3. found ← 70

    9for (int i = 0; i < 4; i++) {10    if (keys[i]7 == target7) {11        found→ 70 = values[i]70;12    }

  4. printf("found=%d ", found);

    15    printf("found=%d\n", found70);16    return 0;17}
    outputfound=70

  1. target ← 3, keys ← ⟨addr A⟩, values ← ⟨addr B⟩, found ← -1

    3int main(void) {4    int target→ 3 = 3;5    int keys→ ⟨addr A⟩[4] = {3, 7, 11, 0};6    int values→ ⟨addr B⟩[4] = {30, 70, 110, 0};7    int found→ -1 = -1;

  2. for (int i = 0; i < 4; i++)

    pass 1 of 4
    9for (int i0 = 0; i < 4; i++) {10    if (keys[i] == target) {
    All 4 passes — pass 1 is the card above
    passikeys[i]targetvalues[i]found
    103330-1 → 30
    21————
    32————
    43————

  3. found ← 30

    9for (int i = 0; i < 4; i++) {10    if (keys[i]3 == target3) {11        found→ 30 = values[i]30;12    }

  4. printf("found=%d ", found);

    15    printf("found=%d\n", found30);16    return 0;17}
    outputfound=30

  1. target ← 9, keys ← ⟨addr A⟩, values ← ⟨addr B⟩, found ← -1

    3int main(void) {4    int target→ 9 = 9;5    int keys→ ⟨addr A⟩[4] = {3, 7, 11, 0};6    int values→ ⟨addr B⟩[4] = {30, 70, 110, 0};7    int found→ -1 = -1;

  2. for (int i = 0; i < 4; i++)

    pass 1 of 4
    9for (int i0 = 0; i < 4; i++) {10    if (keys[i] == target) {
    All 4 passes — pass 1 is the card above
    passi
    10
    21
    32
    43

  3. printf("found=%d ", found);

    15    printf("found=%d\n", found-1);16    return 0;17}
    outputfound=-1