HashMap

Deterministic open-addressed hash map with linear probing.

Overview

HashMap<K, V> stores keys and values in parallel contiguous buffers. Lookup uses:

• deterministic hashing via std::hash::Hasher
• open addressing
• linear probing
• tombstones for removed entries

The map grows when the configured load factor would be exceeded. Capacity is always managed in buckets, not bytes.

Key Requirements

Keys must satisfy Hash & Eq.

In practice that means user-defined key types usually provide:

• @implements(Hash, Eq) on the record
• a hash(&self, hasher: &mut Hasher): void method
• an equals(&self, other: &K): boolean method

Bucket States

  state = 0  -> empty
  state = 1  -> occupied
  state = 2  -> tombstone

Empty buckets stop probing. Tombstones preserve probe chains after remove.

Memory Layout

  HashMap<K, V>
  ┌────────────────────────────────────────────────────────────┐
  │ states:  [E|O|T|O|...]                                    │
  │ hashes:  [0|h|0|h|...]                                    │
  │ keys:    [ |K| |K|...]                                    │
  │ values:  [ |V| |V|...]                                    │
  │ length: active occupied buckets                           │
  │ tombstones: removed buckets still participating in probe  │
  │ capacity: total bucket count                              │
  └────────────────────────────────────────────────────────────┘

keys and values are manual-storage buffers. Only buckets marked as occupied contain initialized logical elements.

Probe Sequence

A lookup starts at hash % capacity and advances one slot at a time until:

• it finds an empty bucket (not present)
• it finds a matching occupied bucket (present)
• it has examined every bucket (full-table miss)

  capacity = 8
  start = hash % 8 = 3

  index:   0   1   2   3   4   5   6   7
  state:   E   T   O   O   T   O   E   E
                       ^
                       start

  probe order: 3 -> 4 -> 5 -> 6

  - slot 3: occupied, different key
  - slot 4: tombstone, continue
  - slot 5: occupied, different key
  - slot 6: empty, stop -> key does not exist

Insert / Replace Rules

Insert first reserves enough capacity, then probes exactly like lookup.

During probing it tracks:

• the first tombstone encountered
• whether an existing matching key was found

That gives three possible outcomes:

1. matching key found -> replace value
2. no key found, tombstone seen -> reuse first tombstone
3. no key found, no tombstone seen -> use first empty bucket

Drop Behavior

HashMap owns both the key and the value stored in an occupied bucket.

That means:

• replacing an entry drops the previous key and returns the previous value
• removing an entry drops the key and returns the value
• clear() drops every occupied key/value pair
• drop() calls clear() and then frees the backing buffers

Tombstones do not hold logical values anymore; they only preserve probing structure until the next rehash.

Complexity

Average-case complexity:

• insert -> O(1)
• get -> O(1)
• remove -> O(1)
• reserve -> O(n) when rehashing occurs

Worst-case probe chains are linear in the bucket count.

Example

import Eq from "std::collections";
import Hash from "std::collections";
import HashMap from "std::collections";
import Hasher from "std::hash";

@implements(Hash, Eq)
record Key {
  id: i32;

  hash(&self, hasher: &mut Hasher): void {
    let mut state: &mut Hasher = hasher;
    state.writeI32(self.id);
  }

  equals(&self, other: &Key): boolean {
    return self.id == other.id;
  }
}

function main(): i32 {
  let mut map: HashMap<Key, i32> = HashMap::new<Key, i32>();
  map.insert(Key { id: 1 }, 10);
  map.insert(Key { id: 2 }, 20);

  let lookup: Key = Key { id: 2 };
  let value: i32 = match (map.get(&lookup)) {
    Option::SOME(found) -> *found,
    Option::NONE -> -1,
  };

  return value;
}