simple hash map due to constraints (no resize, no remove)

lock free hash map.cpp

class HashMap {
  constexpr NumBuckets = Length * Factor;
  struct N {
    K key;
    N* next;
  };
  N nodes[Length];
  V values[Length];
  N* freeList;
  N* buckets[NumBuckets];
}
// Using indices instead of pointers in your impl will make things a lot smaller

HashMap() : buckets() // all buckets NULL
{
  // put all the nodes into the freelist
  freeList = &nodes[0];
  for( i=0; i<Length-1; ++i )
    nodes[i].next = &nodes[i+1];
  
  // fun trick: using "offset to next node minus one" instead of indices means that memset(0) creates a fully linked list of nodes
}

// Note: Most functions require sequentially-consistent memory ordering!!

private N* AllocNode() { // pop a node off the free list
  [atomic]
  {
    N* result = freeList;
    if( result != NULL )
    {
      [expect freeList == result] // i.e. retry the atomic block from the start if this atomic assignment fails
      freeList = result->next;
    }
    return result;
  }
}
private void FreeNode(N* node) { // push a node into the free list
  [atomic]
  {
    node->next = freeList;
    [expect freeList == node->next]
    freeList = node;
  }
}

private N* Find(K k, N* bucket) { // Search the bucket for the key
  for (N* n = bucket; n; n = n->next) {
    if( n->key == k )
      return n;
  }
  return NULL;
}

public V* Find(K k) { // pick a bucket that the key should be into, then search it
  int bucketIndex = Hash(k) % NumBuckets;
  N* bucket = buckets[bucketIndex];
  N* found = Find(k, bucket);
  if( !found ) {
    return NULL;
  }
  return &values[found - nodes];
}

public bool Insert(K k, V v) {
  // pick a bucket that the key should go into
  int bucketIndex = Hash(k) % NumBuckets;

  N* node = AllocNode();
  if( !node ) {
    return false; // we're out of space! throw out_of_memory, etc...
  }
  // write the key and value. make sure this hits memory before the atomic swap below!
  node->key = k;
  values[node - nodes] = v;

  // push the node onto the front of the bucket
  [atomic]
  {
    N* bucket = buckets[bucketIndex];
    if( Find(k, buckets[bucket]) ) { // make sure it's not already in there
      FreeNode(node); // undo the alloc!
      return false; // key already present
    }
    node->next = bucket;
    [expect bucket == node->next] // i.e. retry atomic block if atomic assignment fails
    bucket = node;
    // new node containing the key was added
    return true;
  }
}

void ForEach(Fn fn) // iterating the entire map is straightforward
{
  for (int bucketIndex = 0; bucketIndex != NumBuckets; ++bucketIndex) {
    N* bucket = buckets[bucketIndex];
    for (N* n = bucket; n; n = n->next) {
      fn(n->key, values[n - nodes]);
    }
  }
}