4 ms·
you can compress it by just truncating the hashes as short as you want
by bloomthrowaway 8y ago
you can compress it by just truncating the hashes as short as you want
- Franciscouzo 8y agoI think the method you're describing is equivalent to a bloom filter that only uses one hash function per key.
- bloomthrowaway 8y agoits the same structure as a Bloom filter but more efficient because it has no empty slots
- jhafdks7r3wr3 8y agoNo, it's not the same structure as a Bloom filter without empty slots. It's the same structure as a Bloom filter with only one hash function. Bloom filters use multiple.
- bloomthrowaway 8y agomultiple hash functions only exist because they don't use secure hashes (for speed reasons) so there's collisions. Normally for passwords you would use a secure hash, negating this
- Franciscouzo 8y agoNo, the math on bloom filters already assumes a random oracle.
- honoredb 8y agoTo store 500 million hashes in 860MB, wouldn't you need to truncate them to 13 bits each? That'd give a false positive rate of 1000 in 1000, slightly worse than the Bloom filter's false positive rate of 1 in 1000.
- dwaite 8y agoDepends on the data structure and encoding. For instance, another simple/fast/non-optimal encoding would be a 32 bit table of bit flags, which would weigh in at 0.5 GiB. That would give you a ~11.5% false positive rate.