5 ms·

I feel like you’d want something a bit safer than “we don’t store the keys and just rely on the hash to be really good” [1], putting “please do not use this for

by boulos 6y ago

I feel like you’d want something a bit safer than “we don’t store the keys and just rely on the hash to be really good” [1], putting “please do not use this for serious tasks” in a comment embedded in the header file isn’t a clear enough warning. It’s not clear to me that that probability of collision assumptions hold. It’s basically assuming that the hashing is perfect and distributes any inputs to the full 64-bit space with uniform probability. That’s the usual hash map / randomized algorithm hope, but does BigCrush or similar avalanche testing really prove that? (Presumably not, otherwise there wouldn’t be image attacks for things like md5). [1] https://github.com/wangyi-fudan/wyhash/blob/d2a305811972f391d472cd57c9d542411773ead1/wyhash.h#L204 https://github.com/wangyi-fudan/wyhash/blob/d2a305811972f391...

deleted 6y ago
[deleted]
graderjs 6y ago
I agree that not storing keys is riskier, and it's not a risk that's mitigated even if it is a perfect uniform distribution because you can still have collisions. Maybe I don't understand the reasons for that design but personally I don't think it's a good design for a hash table. But even so the hash underlying it is a very good hash. Big crush and smhasher give a good indication of uniform distribution, but nothing can guarantee no collisions because you're always going to have collisions it's always a possibility. Even if you have a perfect permutation of the 64 bit space, the minute you go beyond 64 bits of keys you're going to collide within 64 bits of hash. By all the tests they run md5 is a much poorer hash than many others. But it's a or it was a cryptographic hash. It's different.
- stingraycharles 6y ago
  To be fair 2^64 keys is a lot, to the point that it cannot possibly fit into memory with today’s hardware.
  - Bootvis 6y ago
    According to the Birthday paradox you can expect a collision after approx 2^32 keys. Whether this is small or big probably depends on your use case.
    - kaoD 6y ago
      But even after only one item is inserted the probability of collision is >0. Yes, it is very very very (very) small, but it's still there!
  - hansvm 6y ago
    We're getting close. There's way more RAM than that in the world, and a quick search turned up a single machine from a few years ago that was only off by 160x or so. Even without relying on the pigeonhole principle though you still have the birthday paradox. As a ballpark estimate, if you have N keys then you'd expect a 50/50 chance of at least one collision with sqrt(N) hashes -- 2^32 for this problem.
  - deleted 6y ago
    [deleted]
rurban 6y ago
I do a similar thing with constant keys. Check the result with a simple memcmp/strcmp of the key for false positives. But only usable for constant perfect hashes. 64 bit is not good enough for that claim. 128 would be good, 256 perfect for production use. Regardless of the hash function quality. wyhash is a very good hash, the best and fastest portable one.
CodesInChaos 6y ago
> “we don’t store the keys and just rely on the hash to be really good” I think that's fine if you actually use a really good hash (e.g. a 128-bit cryptographic PRF). But I wouldn't be comfortable with hashes shorter than that or which aren't crypto quality. People already make such assumptions when assuming uniqueness v4 UUIDs.
herbstein 6y ago
> It’s not clear to me that that probability of collision assumptions hold. It’s basically assuming that the hashing is perfect and distributes any inputs to the full 64-bit space with uniform probability. You can get this guarantee by using a random hash function if you don't support insertion and are fine with using a relatively larger amounts of memory.
- deleted 6y ago
  [deleted]

by boulos 6y ago

deleted 6y ago

[deleted]

graderjs 6y ago

I agree that not storing keys is riskier, and it's not a risk that's mitigated even if it is a perfect uniform distribution because you can still have collisions. Maybe I don't understand the reasons for that design but personally I don't think it's a good design for a hash table. But even so the hash underlying it is a very good hash. Big crush and smhasher give a good indication of uniform distribution, but nothing can guarantee no collisions because you're always going to have collisions it's always a possibility. Even if you have a perfect permutation of the 64 bit space, the minute you go beyond 64 bits of keys you're going to collide within 64 bits of hash. By all the tests they run md5 is a much poorer hash than many others. But it's a or it was a cryptographic hash. It's different.

stingraycharles 6y ago
To be fair 2^64 keys is a lot, to the point that it cannot possibly fit into memory with today’s hardware.
- Bootvis 6y ago
  According to the Birthday paradox you can expect a collision after approx 2^32 keys. Whether this is small or big probably depends on your use case.
  - kaoD 6y ago
    But even after only one item is inserted the probability of collision is >0. Yes, it is very very very (very) small, but it's still there!
- hansvm 6y ago
  We're getting close. There's way more RAM than that in the world, and a quick search turned up a single machine from a few years ago that was only off by 160x or so. Even without relying on the pigeonhole principle though you still have the birthday paradox. As a ballpark estimate, if you have N keys then you'd expect a 50/50 chance of at least one collision with sqrt(N) hashes -- 2^32 for this problem.
- deleted 6y ago
  [deleted]

rurban 6y ago

I do a similar thing with constant keys. Check the result with a simple memcmp/strcmp of the key for false positives. But only usable for constant perfect hashes. 64 bit is not good enough for that claim. 128 would be good, 256 perfect for production use. Regardless of the hash function quality. wyhash is a very good hash, the best and fastest portable one.

CodesInChaos 6y ago

> “we don’t store the keys and just rely on the hash to be really good” I think that's fine if you actually use a really good hash (e.g. a 128-bit cryptographic PRF). But I wouldn't be comfortable with hashes shorter than that or which aren't crypto quality. People already make such assumptions when assuming uniqueness v4 UUIDs.

herbstein 6y ago

> It’s not clear to me that that probability of collision assumptions hold. It’s basically assuming that the hashing is perfect and distributes any inputs to the full 64-bit space with uniform probability. You can get this guarantee by using a random hash function if you don't support insertion and are fine with using a relatively larger amounts of memory.

deleted 6y ago
[deleted]