5 ms·

There is no error in the original article other than how it’s phrased. I think it intends to warn people not to trust String.hashCode() to be unique, with a lot

There is no error in the original article other than how it’s phrased. I think it intends to warn people not to trust String.hashCode() to be unique, with a lot of examples. That is good! Why criticise it? Proper use of hashCode() is for quickly comparing if strings might be equal before doing a full string compare, it’s meant for building hashtables.

dahart 8y ago
Your interpretation is generous since the original article says explicitly: “some hashes are worse than others. You can expect String to be fairly poor.” The problem / error is the claim that the collision demonstration with short strings somehow proves that String is much worse than other hash functions, without testing other hash function, and without understanding that the theoretical ideal predicts a lot of collisions with short strings.
cm2187 8y ago
Actually is any hashing algorithm guaranteeing uniqueness? Of course it is theoretically impossible to guarantee that (pigeonhole principle) but even practically, can a collision occur on sha256 in real use? I understand the hash is designed so that it is theoretically difficult to manufacture a collision but surely a collision could occur in real life?
- dmurray 8y ago
  Suppose there are 100 billion computers in the world, including phones, smart watches, toasters, etc. Suppose each of those can perform at the level of a state of the art specialized mining ASIC, 10 million million hashes per second, and they've all been generating 256-bit hashes constantly for 30 years, or a billion seconds. Suppose further that sha256 is pretty good and the probability of a collision is close to that of random chance. Then there have been 1e33 sha256 hashes generated ever. Looking at the probability table on Wikipedia for the birthday problem [0] and the row for 256 bits, interpolating it gives a probability of 1e-10 that there has been a collision. So there would be a chance of one in ten billion that some two hashes have collided over the last 30 years. Your piece of toast, perhaps, and my bitcoin digest. I think for practical purposes we're pretty safe. [0]https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
  - cm2187 8y ago
    I think you are assuming it has a perfectly uniform distribution.
    - dmurray 8y ago
      Yes, that's what I meant by saying sha256 is at least "pretty good" as a hash function. Which is not at all proven, but one of the reasons sha256 is popular is that it looks like it should be close to uniform.
  - lostmsu 8y ago
    Impressively, my Facebook interviewer did not recognize validity of nearly identical explanation for using sha256 hashes instead of full strings as a key for purpose of counting stack traces.
- zokier 8y ago
  Perfect hash functions guarantee no collisions. Of course they have other limitations, so you have to pick some tradeoffs.
  - kevinwang 8y ago
    I'm pretty sure, as the parent mentioned, that theoretic collisionness is impossible with |input-domaim| > |output-domain| bc of the pigeonhole principle. Especially so when input has no maximum size.
  - speakeron 8y ago
    However perfect it is, it can only guarantee no collisions if the size of the strings you're hashing is equal or lower than the hash size. In this house, we obey the pigeonhole principle.
    - jcranmer 8y ago
      It can do better, if the input is not "every possible string." A perfect hash of the strings representing 32-bit unsigned integers can compress strings up to 10 bytes long into 4 bytes of data.
  - rurban 8y ago
    Sure, there is a pretty severe limitation for perfect hash functions: you have to know all the possible keys in advance. That's rarely the case.
rurban 8y ago
There's a huge math error in the article, coming to complete wrong solutions in the second case, long strings. The probability of the 2nd case is 1.4, so the outcome of 1 collision is no surprise at all, and thus you cannot praise the quality of the Java hash function this way. What he should have praised instead is the Java hash table, which is the only one of all major programming languages, which is fast and secure. All others are mostly slow, and insecure. Java chose a fast hash and a secure collision strategy, counting collisions and switching to a tree on attacks. Most others chose a random seed and a slow hash function, which are still DOS unsafe whilst being 10x slower. Pure security theatre.

dahart 8y ago

Your interpretation is generous since the original article says explicitly: “some hashes are worse than others. You can expect String to be fairly poor.” The problem / error is the claim that the collision demonstration with short strings somehow proves that String is much worse than other hash functions, without testing other hash function, and without understanding that the theoretical ideal predicts a lot of collisions with short strings.

cm2187 8y ago

Actually is any hashing algorithm guaranteeing uniqueness? Of course it is theoretically impossible to guarantee that (pigeonhole principle) but even practically, can a collision occur on sha256 in real use? I understand the hash is designed so that it is theoretically difficult to manufacture a collision but surely a collision could occur in real life?

dmurray 8y ago
Suppose there are 100 billion computers in the world, including phones, smart watches, toasters, etc. Suppose each of those can perform at the level of a state of the art specialized mining ASIC, 10 million million hashes per second, and they've all been generating 256-bit hashes constantly for 30 years, or a billion seconds. Suppose further that sha256 is pretty good and the probability of a collision is close to that of random chance. Then there have been 1e33 sha256 hashes generated ever. Looking at the probability table on Wikipedia for the birthday problem [0] and the row for 256 bits, interpolating it gives a probability of 1e-10 that there has been a collision. So there would be a chance of one in ten billion that some two hashes have collided over the last 30 years. Your piece of toast, perhaps, and my bitcoin digest. I think for practical purposes we're pretty safe. [0]https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- cm2187 8y ago
  I think you are assuming it has a perfectly uniform distribution.
  - dmurray 8y ago
    Yes, that's what I meant by saying sha256 is at least "pretty good" as a hash function. Which is not at all proven, but one of the reasons sha256 is popular is that it looks like it should be close to uniform.
- lostmsu 8y ago
  Impressively, my Facebook interviewer did not recognize validity of nearly identical explanation for using sha256 hashes instead of full strings as a key for purpose of counting stack traces.
zokier 8y ago
Perfect hash functions guarantee no collisions. Of course they have other limitations, so you have to pick some tradeoffs.
- kevinwang 8y ago
  I'm pretty sure, as the parent mentioned, that theoretic collisionness is impossible with |input-domaim| > |output-domain| bc of the pigeonhole principle. Especially so when input has no maximum size.
- speakeron 8y ago
  However perfect it is, it can only guarantee no collisions if the size of the strings you're hashing is equal or lower than the hash size. In this house, we obey the pigeonhole principle.
  - jcranmer 8y ago
    It can do better, if the input is not "every possible string." A perfect hash of the strings representing 32-bit unsigned integers can compress strings up to 10 bytes long into 4 bytes of data.
- rurban 8y ago
  Sure, there is a pretty severe limitation for perfect hash functions: you have to know all the possible keys in advance. That's rarely the case.

rurban 8y ago

There's a huge math error in the article, coming to complete wrong solutions in the second case, long strings. The probability of the 2nd case is 1.4, so the outcome of 1 collision is no surprise at all, and thus you cannot praise the quality of the Java hash function this way. What he should have praised instead is the Java hash table, which is the only one of all major programming languages, which is fast and secure. All others are mostly slow, and insecure. Java chose a fast hash and a secure collision strategy, counting collisions and switching to a tree on attacks. Most others chose a random seed and a slow hash function, which are still DOS unsafe whilst being 10x slower. Pure security theatre.