Multikey zero gc Map TypeScript

map.ts

export class LowLevelCoordinateMap<V> {
  private capacity: number;
  private mask: number;
  private size: number = 0;
  private maxLoadFactor = 0.7;

  // Stores structural composite keys flat in memory: [x0, y0, z0, x1, y1, z1, ...]
  private keys: Int32Array;
  // Standard array storing the mapped values, aligning perfectly with the key slots
  private values: Array<V | undefined>;
  // Bitset array to explicitly track if a slot is filled (handles default 0,0,0 coordinates)
  private occupied: Uint8Array;

  /**
   * @param initialCapacity Must be a power of 2 (e.g., 256, 512, 1024, 2048)
   */
  constructor(initialCapacity = 1024) {
    // Force capacity to be a power of 2 for ultra-fast bitwise masking instead of division
    this.capacity = this.isPowerOfTwo(initialCapacity) ? initialCapacity : this.nextPowerOfTwo(initialCapacity);
    this.mask = this.capacity - 1;

    this.keys = new Int32Array(this.capacity * 3); // 3 slots per key (x, y, z)
    this.values = new Array<V | undefined>(this.capacity);
    this.occupied = new Uint8Array(this.capacity);
  }

  /**
   * Deterministic 32-bit FNV-1a inspired hash using Math.imul.
   * Math.imul forces CPU-level 32-bit integer math, bypassing JS float allocations.
   */
  private hash(x: number, y: number, z: number): number {
    let h = 2166136261;
    
    h = Math.imul(h ^ x, 16777619);
    h = Math.imul(h ^ y, 16777619);
    h = Math.imul(h ^ z, 16777619);
    
    return (h ^ (h >>> 16)) & this.mask;
  }

  /**
   * Maps a composite 3D coordinate to a value.
   */
  set(x: number, y: number, z: number, value: V): void {
    // If the table is getting too full, double the size to avoid heavy collision chains
    if (this.size >= this.capacity * this.maxLoadFactor) {
      this.resize(this.capacity * 2);
    }

    let slot = this.hash(x, y, z);

    while (true) {
      // If the slot is empty, we can safely write here
      if (this.occupied[slot] === 0) {
        const stride = slot * 3;
        this.keys[stride] = x;
        this.keys[stride + 1] = y;
        this.keys[stride + 2] = z;
        this.values[slot] = value;
        this.occupied[slot] = 1;
        this.size++;
        return;
      }

      // If the slot is already occupied, check if it's the exact same coordinate (an update)
      const stride = slot * 3;
      if (this.keys[stride] === x && this.keys[stride + 1] === y && this.keys[stride + 2] === z) {
        this.values[slot] = value;
        return;
      }

      // Linear probing: collision occurred, check the immediate next slot
      slot = (slot + 1) & this.mask;
    }
  }

  /**
   * Zero-Allocation Lookup. Accepts primitives directly so no objects/strings are created.
   */
  get(x: number, y: number, z: number): V | undefined {
    let slot = this.hash(x, y, z);

    while (true) {
      // If we hit a completely empty slot, the structural key definitely does not exist
      if (this.occupied[slot] === 0) {
        return undefined;
      }

      const stride = slot * 3;
      // Compare primitives extracted straight out of the flat TypedArray
      if (this.keys[stride] === x && this.keys[stride + 1] === y && this.keys[stride + 2] === z) {
        return this.values[slot];
      }

      // Keep stepping forward if a collision previously pushed our target further down
      slot = (slot + 1) & this.mask;
    }
  }

  /**
   * Checks for structural key existence without allocating data.
   */
  has(x: number, y: number, z: number): boolean {
    return this.get(x, y, z) !== undefined;
  }

  /**
   * Automatically doubles memory buffers and rehashes all current values.
   */
  private resize(newCapacity: number): void {
    const oldKeys = this.keys;
    const oldValues = this.values;
    const oldOccupied = this.occupied;
    const oldCapacity = this.capacity;

    this.capacity = newCapacity;
    this.mask = newCapacity - 1;
    this.size = 0;

    this.keys = new Int32Array(this.capacity * 3);
    this.values = new Array<V | undefined>(this.capacity);
    this.occupied = new Uint8Array(this.capacity);

    // Rehash everything into the expanded arrays
    for (let i = 0; i < oldCapacity; i++) {
      if (oldOccupied[i] === 1) {
        const stride = i * 3;
        this.set(oldKeys[stride], oldKeys[stride + 1], oldKeys[stride + 2], oldValues[i]!);
      }
    }
  }

  private isPowerOfTwo(n: number): boolean {
    return (n & (n - 1)) === 0 && n !== 0;
  }

  private nextPowerOfTwo(n: number): number {
    let p = 1;
    while (p < n) p <<= 1;
    return p;
  }
}