多对一哈希函数需求：实现字符串集合成员验证功能

你需要的是一种集合存在性验证机制，可以通过以下几种方式实现，无需依赖外部库，且完全满足功能需求：

现成方案：布隆过滤器（Bloom Filter） #

布隆过滤器是专门用于高效判断元素是否属于某个集合的结构，空间占用小、查询速度快，虽然存在极低的假阳性概率（可通过调整参数降低），但完全符合你“不关注安全性、只实现功能”的需求。

JavaScript 实现代码 #

class BloomFilter {
  constructor(size = 1024, hashCount = 3) {
    this.size = size;
    this.hashCount = hashCount;
    this.bitArray = new Array(size).fill(false);
  }

  // 内部哈希函数（多种子降低碰撞）
  #hash(str, seed) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      hash = (hash * seed + str.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  add(str) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.#hash(str, i + 1);
      this.bitArray[index] = true;
    }
  }

  has(str) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.#hash(str, i + 1);
      if (!this.bitArray[index]) return false;
    }
    return true;
  }

  serialize() {
    return JSON.stringify({
      size: this.size,
      hashCount: this.hashCount,
      bitArray: this.bitArray.map(bit => bit ? 1 : 0).join('')
    });
  }

  static deserialize(str) {
    const data = JSON.parse(str);
    const filter = new BloomFilter(data.size, data.hashCount);
    filter.bitArray = data.bitArray.split('').map(char => char === '1');
    return filter;
  }
}

function generate_hash(inputs) {
  const filter = new BloomFilter();
  inputs.forEach(str => filter.add(str));
  return filter.serialize();
}

function check_str(hashStr, random_str) {
  const filter = BloomFilter.deserialize(hashStr);
  return filter.has(random_str);
}

手动实现方案（无依赖，按需选择） #

方法1：存储哈希集合（100%准确，体积较大） #

直接对每个输入字符串计算唯一哈希值，将哈希集合序列化后作为结果。查询时只需验证目标字符串的哈希是否在集合中，完全无碰撞（只要哈希函数足够区分字符串）。

// 简单字符串哈希函数（非安全，仅用于区分）
function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash << 5) - hash + str.charCodeAt(i);
    hash |= 0; // 转为32位整数
  }
  return hash.toString();
}

function generate_hash(inputs) {
  // 去重后生成哈希集合
  const uniqueHashes = [...new Set(inputs.map(simpleHash))];
  return JSON.stringify(uniqueHashes);
}

function check_str(hashStr, random_str) {
  const storedHashes = JSON.parse(hashStr);
  const targetHash = simpleHash(random_str);
  return storedHashes.includes(targetHash);
}

方法2：前缀树序列化（适合含公共前缀的字符串集合） #

将所有输入字符串构建成前缀树（Trie），序列化后作为哈希结果。查询时遍历前缀树即可判断字符串是否存在，空间效率优于哈希集合（尤其当字符串有大量公共前缀时）。

// 前缀树节点构造函数
function TrieNode() {
  this.children = {};
  this.isEnd = false; // 标记该节点是否为字符串结尾
}

function generate_hash(inputs) {
  const root = new TrieNode();
  inputs.forEach(str => {
    let currentNode = root;
    for (const char of str) {
      if (!currentNode.children[char]) {
        currentNode.children[char] = new TrieNode();
      }
      currentNode = currentNode.children[char];
    }
    currentNode.isEnd = true;
  });
  // 序列化前缀树
  return JSON.stringify(root);
}

function check_str(hashStr, random_str) {
  const root = JSON.parse(hashStr);
  let currentNode = root;
  for (const char of random_str) {
    if (!currentNode.children[char]) {
      return false;
    }
    currentNode = currentNode.children[char];
  }
  return currentNode.isEnd === true;
}

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