9 ms·

String.hashCode() is plenty unique

52 points by jxub 8y ago

Waterluvian 8y ago
Just my $0.02: there is nothing to be gained by nagging about someone's punctuation and grammar. That doesn't win you an argument about programming.
- qop 8y ago
  Pointing out mistakes allows for the makers of those mistakes to correct them in the future. Spelling is important. Grammar less so, since we can decipher. But adults should be able to at least spell the words they're using.
- treya 8y ago
  Apart from that one comment, the remainder of this article - the vast majority of it - was a well presented argument about why the original post was flawed. That comment was obviously just an aside
- sigpwned 8y ago
  This is the author. I didn't submit the article here, but I did happen to run across this posting from my GA. Thank you for the feedback. You're right. It's one thing to point out errors constructively, but another thing entirely to make fun. After all, English isn't everyone's first language, and I'd have a tough time writing an article like this in Spanish, for example! I've updated the article to remove that comment, although I still (gently) point out the worst of the errors. I've also added a theoretical framework to tighten up the argument a bit. Thanks again for the feedback. There's no purpose in being nasty when the point can be made another way.
theclaw 8y ago
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.
iainmerrick 8y ago
The original criticism seems perfectly valid (although maybe people are reading too much into it). If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique. 10x extra collisions on short strings does seems pretty bad. And it’s unfortunate that this hash function can’t be changed without breaking the language spec.
- FartyMcFarter 8y ago
  > If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique. No it isn't. In fact, with 16 bits of input, the probability of a collision is not far from 50% according to the birthday problem: https://en.m.wikipedia.org/wiki/Birthday_attack https://en.m.wikipedia.org/wiki/Birthday_attack
  - TheCoelacanth 8y ago
    That's assuming random distribution of hashes. I can trivially write a hash function that produces a unique 32-bit hash for inputs of 32-bit. Just truncate the input to 32 bits. It's not a very good hash function for longer inputs, of course.
    - iainmerrick 8y ago
      You could do that and also use a real hash for longer inputs. Literally truncating the input wouldn’t be great in the likely case that your hash table is using only 10 bits (say) of the hash value, but I bet there are similar approaches that would work.
    - FartyMcFarter 8y ago
      True - but I still don't think it's reasonable to assume that a hash function behaves that way.
Someone 8y ago
”resulted in 1 collision. A “fair” hash function would generate an expected 1.44 collisions over this data. String.hashCode() outperforms a fair hash function significantly” I doubt that is significant, and you needn’t even lookup the confidence intervals. Think of it this way: if you ran one more experiment with similar data, if that perfectly good hash were to approximate that 1.44 collision on average between the two experiments, is has to have at least one experiment where it has zero or one collision. Also, string hashing has a few requirements that I think are more important than having an optimal probability of collisions: - it has to work well on typical 16-bit text strings, where most of the time, half the bytes are zero and most of the other bytes have only fivefold six bits that vary (that’s why there are so many collisions in two character strings: they are four bytes long, but, at best, differ in only about 10 bits) - it has to be fast.

52 points by jxub 8y ago

Just my $0.02: there is nothing to be gained by nagging about someone's punctuation and grammar. That doesn't win you an argument about programming.

qop 8y ago
Pointing out mistakes allows for the makers of those mistakes to correct them in the future. Spelling is important. Grammar less so, since we can decipher. But adults should be able to at least spell the words they're using.
treya 8y ago
Apart from that one comment, the remainder of this article - the vast majority of it - was a well presented argument about why the original post was flawed. That comment was obviously just an aside
sigpwned 8y ago
This is the author. I didn't submit the article here, but I did happen to run across this posting from my GA. Thank you for the feedback. You're right. It's one thing to point out errors constructively, but another thing entirely to make fun. After all, English isn't everyone's first language, and I'd have a tough time writing an article like this in Spanish, for example! I've updated the article to remove that comment, although I still (gently) point out the worst of the errors. I've also added a theoretical framework to tighten up the argument a bit. Thanks again for the feedback. There's no purpose in being nasty when the point can be made another way.

theclaw 8y ago

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.

iainmerrick 8y ago

The original criticism seems perfectly valid (although maybe people are reading too much into it). If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique. 10x extra collisions on short strings does seems pretty bad. And it’s unfortunate that this hash function can’t be changed without breaking the language spec.

FartyMcFarter 8y ago
> If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique. No it isn't. In fact, with 16 bits of input, the probability of a collision is not far from 50% according to the birthday problem: https://en.m.wikipedia.org/wiki/Birthday_attack https://en.m.wikipedia.org/wiki/Birthday_attack
- TheCoelacanth 8y ago
  That's assuming random distribution of hashes. I can trivially write a hash function that produces a unique 32-bit hash for inputs of 32-bit. Just truncate the input to 32 bits. It's not a very good hash function for longer inputs, of course.
  - iainmerrick 8y ago
    You could do that and also use a real hash for longer inputs. Literally truncating the input wouldn’t be great in the likely case that your hash table is using only 10 bits (say) of the hash value, but I bet there are similar approaches that would work.
  - FartyMcFarter 8y ago
    True - but I still don't think it's reasonable to assume that a hash function behaves that way.

Someone 8y ago

”resulted in 1 collision. A “fair” hash function would generate an expected 1.44 collisions over this data. String.hashCode() outperforms a fair hash function significantly” I doubt that is significant, and you needn’t even lookup the confidence intervals. Think of it this way: if you ran one more experiment with similar data, if that perfectly good hash were to approximate that 1.44 collision on average between the two experiments, is has to have at least one experiment where it has zero or one collision. Also, string hashing has a few requirements that I think are more important than having an optimal probability of collisions: - it has to work well on typical 16-bit text strings, where most of the time, half the bytes are zero and most of the other bytes have only fivefold six bits that vary (that’s why there are so many collisions in two character strings: they are four bytes long, but, at best, differ in only about 10 bits) - it has to be fast.