5 ms·
hash functions map infinite-cardinality input sets to finite-cardinality output sets definitionally, this means each output value maps to multiple input values
by preseinger 3y ago
hash functions map infinite-cardinality input sets to finite-cardinality output sets
definitionally, this means each output value maps to multiple input values -- which means uniqueness is, factually, not guaranteed
it doesn't matter if the likelihood of collisions is 1-in-10, or 1-in-100000, or 1-in-1000000000000, or etc. -- if a collision is possible at all, then uniqueness is not guaranteed, and cannot be assumed as true
- deleted 3y ago[deleted]
- Dylan16807 3y agoYou can and should assume sufficiently likely things. It's a waste of time to worry about probabilities with enough zeroes. Especially because in the real world even a mathematically perfect system has a baseline failure rate. If the chance of hash collision is orders of magnitude lower than the baseline failure rate, then there is no downside to using that hash.
- preseinger 3y ago> It's a waste of time to worry about probabilities with enough zeroes. what? no. absolutely not. the "baseline failure rate" of a program with some input values X is zero. > in the real world even a mathematically perfect system has a baseline failure rate. what? no. absolutely not. x = 1 print(x) this is not a probabilistic program, there is no baseline failure rate above zero, the output must be "1", any other output means the program is incorrect this line of reasoning is absolutely invalid -- hash(x) != x
- piperswe 3y agoIf a cosmic ray flips that 1 to a 3, that will bring your failure rate above zero. No program is correct then.
- preseinger 3y agoi can't control solar rays i can control what my application uses as IDs
- Dylan16807 3y ago> what? no. absolutely not. Please explain how the benefit outweighs the cost to spend even 30 seconds to prevent a potential problem with 10^-40 probability. (And by that I mean 10^-40 total probability, not per-item.) > this is not a probabilistic program, there is no baseline failure rate above zero, the output must be "1", any other output means the program is incorrect You could have a power outage, or the OS could crash, or the CPU could have a bug on those opcodes when certain counters roll over at the exact wrong time, or a bit could flip in your memory. The baseline failure rate for a program on a computer in the universe is never zero. This isn't abstract math. And the collision rate of many hashing systems is much smaller than that baseline failure rate. There are even situations where assuming a hash never collides can increase reliability, because the code will be done sooner and that improves the baseline.
- preseinger 3y agoobviously computers are not totally infallible, solar rays can flip memory bits from 1 to 0 or vice versa -- but those failure modes are not expressed by the source code of the running program, they're triggered at a layer of abstraction well below the compiled and running software say the probability of a solar ray bit flip is (say) 0.01%, then consider the following function fn x -> int { if (randf32() < 0.0001) { panic("boom") } return 123 } x will panic with the same probability that a solar ray will flip a memory bit is this acceptable? can i assume that calling x will never panic, in practice?
- xigoi 3y ago> can i assume that calling x will never panic, in practice? If you used the actual probability, which is several orders of magnitude lower, then yes.
- preseinger 3y agoi'm not sure what to say to this -- my question was rhetorical your position is incompatible with deterministic program execution -- it's unsound (shrug)