咨询是否存在生成值列表哈希并校验值归属的算法

Great question! What you're looking for is totally achievable, and there are a couple of solid approaches depending on whether you need 100% accuracy or are okay with a tiny tradeoff for massive space savings.

Bloom Filters (Space-Efficient Probabilistic Check) #

This is the perfect fit if you want a compact "hash" string and can tolerate an extremely low false positive rate (you'll never get a false negative—if it says a value isn't present, it definitely isn't).

Bloom Filters work by using multiple hash functions to map each value to bits in a bitmap. The final "hash" is just this bitmap encoded into a compact string (like Base64). When checking membership, we run the value through the same hash functions and verify all the corresponding bits are set.

Here's how you'd implement this in JavaScript using a popular library:

// Install the library first: npm install bloomfilter
const BloomFilter = require('bloomfilter').BloomFilter;

const values = ['a', 'b', 'c', 'd'];
// Initialize filter: capacity = 10 items, 4 hash functions (adjust for your needs)
const filter = new BloomFilter(10, 4);

// Add all values to the filter
values.forEach(val => filter.add(val));

// Get your compact "hash" string
const hash = filter.buckets.toString('base64');
console.log(hash); // Example output: "xjaks14sdffdghj23h4kjhgd9f81nkjrsdfg9aiojd"

// Check membership
const includes = (hashStr, val) => {
  // Reconstruct the filter from the hash string
  const buckets = Buffer.from(hashStr, 'base64');
  const filter = new BloomFilter(10, 4);
  filter.buckets = buckets;
  return filter.test(val);
};

console.log(includes(hash, 'b')); // true
console.log(includes(hash, 'v')); // false

Exact Membership Check (No False Positives) #

If you need 100% accuracy (no chance of false positives), you can serialize a hash set into a string. This is less space-efficient than a Bloom Filter, but guarantees perfect results.

Here's a simple implementation:

const values = ['a', 'b', 'c', 'd'];

// Create a serialized "hash" from the value list
const createHash = (vals) => JSON.stringify(new Set(vals));

const hash = createHash(values);
console.log(hash); // Output: '["a","b","c","d"]'

// Check membership by parsing the hash back into a Set
const includes = (hashStr, val) => new Set(JSON.parse(hashStr)).has(val);

console.log(includes(hash, 'b')); // true
console.log(includes(hash, 'v')); // false

Which One Should You Choose? #

• Bloom Filter: Use this when your value list is large, and you need a tiny, portable "hash" string. The false positive rate can be minimized by tuning the filter's capacity and number of hash functions.
• Serialized Hash Set: Use this when you can't tolerate any false positives, and the size of the serialized string isn't a problem.

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