TypeScript中基于hashCode与equals实现HashMap存储Vector3键的方案咨询

核心实现思路 #

你可以基于原生Map自行封装支持值相等匹配的HashMap，整体逻辑非常轻量，适配游戏场景的性能需求：

• 先定义Hashable接口，要求所有作为键的类必须实现hashCode(): number和equals(other: unknown): boolean两个方法
• 内部用两层结构存储：外层Map的键是hashCode数值，值是同哈希值下的键值对数组（用来解决哈希冲突）
• 插入时先计算键的哈希值，对应哈希桶内先遍历找equals匹配的现有键，找到就覆盖值，没找到就追加新的键值对
• 查询、删除逻辑同理，先按哈希值定位到桶，再用equals方法匹配目标键

最简实现代码 #

// 可哈希对象接口
interface Hashable {
  hashCode(): number;
  equals(other: unknown): boolean;
}

// 自定义HashMap实现
class HashMap<K extends Hashable, V> {
  private storage = new Map<number, Array<[K, V]>>();

  set(key: K, value: V): void {
    const hash = key.hashCode();
    if (!this.storage.has(hash)) {
      this.storage.set(hash, []);
    }
    const bucket = this.storage.get(hash)!;
    const existIdx = bucket.findIndex(([item]) => item.equals(key));
    existIdx > -1 ? (bucket[existIdx][1] = value) : bucket.push([key, value]);
  }

  get(key: K): V | undefined {
    const bucket = this.storage.get(key.hashCode());
    return bucket?.find(([item]) => item.equals(key))?.[1];
  }

  has(key: K): boolean {
    return this.get(key) !== undefined;
  }

  delete(key: K): boolean {
    const hash = key.hashCode();
    const bucket = this.storage.get(hash);
    if (!bucket) return false;
    const targetIdx = bucket.findIndex(([item]) => item.equals(key));
    if (targetIdx < 0) return false;
    bucket.splice(targetIdx, 1);
    bucket.length === 0 && this.storage.delete(hash);
    return true;
  }
}

// IntVector3适配示例
class IntVector3 implements Hashable {
  constructor(public x: number, public y: number, public z: number) {}

  // 整数坐标哈希算法，31是经典素数因子，冲突概率低
  hashCode(): number {
    let hash = 17;
    hash = hash * 31 + this.x;
    hash = hash * 31 + this.y;
    hash = hash * 31 + this.z;
    return hash;
  }

  equals(other: unknown): boolean {
    if (!(other instanceof IntVector3)) return false;
    return this.x === other.x && this.y === other.y && this.z === other.z;
  }
}

适用场景优化提示 #

如果你的游戏坐标范围极大（单轴数值超过10^5），可以把哈希值替换为BigInt类型，直接用BigInt(this.x) << 64n | BigInt(this.y) << 32n | BigInt(this.z)作为哈希值，几乎可以完全避免哈希冲突，性能损失也极小。如果追求极致性能，也可以用位运算代替乘法计算哈希，进一步降低运行开销。

现成NPM包推荐 #

不想自己实现的话可以直接用成熟的第三方库：

• hashmap：轻量级无依赖的HashMap实现，支持自定义哈希函数和相等判断函数
• typescript-collections：TS友好的通用集合库，内置的HashMap支持泛型和自定义比较逻辑
• immutable：不可变数据结构库，内置的Map原生支持自定义哈希和相等判断，项目已经在用不可变数据的话可以直接复用

内容的提问来源于stack exchange，提问作者kitta