《游戏引擎实现原理》7.1 动态数组与开放寻址哈希

// file: src/core/dyn-array.ts
// tier: L1
// verify: npx vitest run src/core/dyn-array.test.ts
//
// 动态数组：容量不足时按固定因子扩容。增长因子可配（1.25 / 1.5 / 2），
// 并统计「扩容次数」与「累计搬运元素数」——这两个数直接决定增长因子的取舍。

export class DynArray<T> {
  #data: (T | undefined)[];
  #len = 0;
  #cap: number;
  #factor: number;
  #minCap: number;

  /** 扩容次数：容量每翻一次加一。 */
  reallocations = 0;
  /** 累计搬运元素数：每次扩容要把旧内容拷到新 buffer。 */
  copies = 0;

  constructor(growFactor = 2, minCap = 8) {
    this.#factor = growFactor;
    this.#minCap = minCap;
    this.#cap = 0;
    this.#data = [];
  }

  get length(): number {
    return this.#len;
  }

  get capacity(): number {
    return this.#cap;
  }

  /** 把容量至少抬到 need，仍不足则按因子继续翻。 */
  #grow(need: number): void {
    let cap = this.#cap === 0 ? this.#minCap : this.#cap;
    while (cap < need) cap = Math.ceil(cap * this.#factor);
    const next: (T | undefined)[] = new Array(cap);
    for (let i = 0; i < this.#len; i++) next[i] = this.#data[i];
    this.copies += this.#len;
    this.reallocations++;
    this.#data = next;
    this.#cap = cap;
  }

  /** 预留容量，避免后续多次扩容。 */
  reserve(need: number): void {
    if (need > this.#cap) this.#grow(need);
  }

  push(value: T): void {
    if (this.#len === this.#cap) this.#grow(this.#len + 1);
    this.#data[this.#len++] = value;
  }

  pop(): T | undefined {
    if (this.#len === 0) return undefined;
    const v = this.#data[--this.#len];
    this.#data[this.#len] = undefined;
    return v;
  }

  get(index: number): T | undefined {
    if (index < 0 || index >= this.#len) return undefined;
    return this.#data[index];
  }

  set(index: number, value: T): void {
    if (index < 0 || index >= this.#len) throw new RangeError(`index ${index} out of range`);
    this.#data[index] = value;
  }

  /** 就地清零，容量保留（下次 push 不再扩容）。 */
  clear(): void {
    for (let i = 0; i < this.#len; i++) this.#data[i] = undefined;
    this.#len = 0;
  }

  /** 顺序遍历有效区间，不越界到预留容量。 */
  *[Symbol.iterator](): Generator<T> {
    for (let i = 0; i < this.#len; i++) yield this.#data[i] as T;
  }

  toArray(): T[] {
    return [...this];
  }
}

// file: src/core/hash-map.ts
// tier: L1
// verify: npx vitest run src/core/hash-map.test.ts
//
// 开放寻址哈希表（字符串键）。线性探测 + 墓碑删除，可选 Robin Hood 抢占。
// 不靠链地址，所有槽位都在同一段连续数组里，缓存友好。
// 统计总探测步数，用来量化「装载因子升高时查找代价怎么涨」。

export const ProbeMode = { LINEAR: 'linear', ROBIN_HOOD: 'robinhood' } as const;
export type ProbeMode = (typeof ProbeMode)[keyof typeof ProbeMode];

const EMPTY = 0;
const OCCUPIED = 1;
const TOMB = 2;

/** FNV-1a 32 位哈希：字符串 → 无符号整数。 */
export function fnv1a(s: string): number {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

export class HashMap<V> {
  #keys: (string | undefined)[];
  #values: (V | undefined)[];
  #state: Uint8Array;
  #dist: Int32Array; // 探测距离（Robin Hood 用）
  #mask: number;
  #size = 0;
  #tombstones = 0;
  #mode: ProbeMode;
  #maxLoad: number;

  /** 总探测步数：每访问一个槽位计一步。 */
  probes = 0;

  constructor(mode: ProbeMode = ProbeMode.LINEAR, initialCap = 16, maxLoad = 0.75) {
    let cap = 1;
    while (cap < initialCap) cap <<= 1;
    this.#mode = mode;
    this.#maxLoad = maxLoad;
    this.#mask = cap - 1;
    this.#keys = new Array(cap);
    this.#values = new Array(cap);
    this.#state = new Uint8Array(cap);
    this.#dist = new Int32Array(cap);
  }

  get size(): number {
    return this.#size;
  }

  get capacity(): number {
    return this.#mask + 1;
  }

  #rehash(cap: number): void {
    const oldKeys = this.#keys;
    const oldValues = this.#values;
    const oldState = this.#state;
    this.#keys = new Array(cap);
    this.#values = new Array(cap);
    this.#state = new Uint8Array(cap);
    this.#dist = new Int32Array(cap);
    this.#mask = cap - 1;
    this.#size = 0;
    this.#tombstones = 0;
    for (let i = 0; i < oldKeys.length; i++) {
      if (oldState[i] === OCCUPIED) this.#insert(oldKeys[i] as string, oldValues[i] as V);
    }
  }

  /** 返回键所在的槽位下标；不存在返回 -1。遇到 EMPTY 才停（墓碑不停）。 */
  #find(key: string): number {
    let slot = fnv1a(key) & this.#mask;
    for (;;) {
      this.probes++;
      const st = this.#state[slot];
      if (st === EMPTY) return -1;
      if (st === OCCUPIED && this.#keys[slot] === key) return slot;
      slot = (slot + 1) & this.#mask;
    }
  }

  /** 插入一个「确认不存在」的新键，占第一个 EMPTY 或 TOMB 槽。 */
  #insert(key: string, value: V): void {
    let slot = fnv1a(key) & this.#mask;
    let dist = 0;
    let curKey = key;
    let curValue = value;
    for (;;) {
      this.probes++;
      const st = this.#state[slot];
      if (st === EMPTY || st === TOMB) {
        if (st === TOMB) this.#tombstones--;
        this.#keys[slot] = curKey;
        this.#values[slot] = curValue;
        this.#state[slot] = OCCUPIED;
        this.#dist[slot] = dist;
        this.#size++;
        return;
      }
      if (this.#mode === ProbeMode.ROBIN_HOOD && this.#dist[slot] < dist) {
        // 抢占：把「更富」的槽位让给探测距离更长的键，被换出的键继续向后找
        const tk = this.#keys[slot] as string;
        const tv = this.#values[slot] as V;
        const td = this.#dist[slot];
        this.#keys[slot] = curKey;
        this.#values[slot] = curValue;
        this.#dist[slot] = dist;
        curKey = tk;
        curValue = tv;
        dist = td;
      }
      slot = (slot + 1) & this.#mask;
      dist++;
    }
  }

  set(key: string, value: V): void {
    const found = this.#find(key);
    if (found >= 0) {
      this.#values[found] = value; // 已存在：原地覆盖
      return;
    }
    if ((this.#size + this.#tombstones + 1) / (this.#mask + 1) > this.#maxLoad) {
      this.#rehash((this.#mask + 1) * 2);
    }
    this.#insert(key, value);
  }

  get(key: string): V | undefined {
    const slot = this.#find(key);
    return slot >= 0 ? this.#values[slot] : undefined;
  }

  has(key: string): boolean {
    return this.#find(key) >= 0;
  }

  /** 墓碑删除：标记为 TOMB，查找时继续向后扫，不打断探测链。 */
  delete(key: string): boolean {
    const slot = this.#find(key);
    if (slot < 0) return false;
    this.#state[slot] = TOMB;
    this.#values[slot] = undefined;
    this.#size--;
    this.#tombstones++;
    return true;
  }

  /** 平均每次访问的探测步数（get/set/delete 的累计除以条目数）。 */
  avgProbes(): number {
    return this.probes / Math.max(1, this.#size);
  }

  *entries(): Generator<[string, V]> {
    for (let i = 0; i < this.#state.length; i++) {
      if (this.#state[i] === OCCUPIED) yield [this.#keys[i] as string, this.#values[i] as V];
    }
  }
}