4 ms·
Can anyone explain how the hash function maps to multiple values in the bit vector? I thought functions cant be one to many.
by ZhangSWEFAANG 5y ago
Can anyone explain how the hash function maps to multiple values in the bit vector? I thought functions cant be one to many.
- fiddlerwoaroof 5y agoA function can map multiple inputs to one output but not one input to multiple outputs.
- karsinkk 5y agoYou're right, A hash function doesn't map to multiple values. Bloom filters and other probabilistic set membership DS's like Cuckoo filters instead use multiple hash functions to map one input to multiple output values. [1] The number of hash functions to use depends on the expected false positive probability rate, number of bits in the filter and the number of elements which will be inserted [1] : https://en.wikipedia.org/wiki/Bloom_filter#Algorithm_description https://en.wikipedia.org/wiki/Bloom_filter#Algorithm_descrip...