4 ms·

There's one valid objection to hashing (not the one the author expressed): you may have an array of items that you can compare, but you cannot hash. For exampl

by _cs2017_ 7y ago

There's one valid objection to hashing (not the one the author expressed): you may have an array of items that you can compare, but you cannot hash. For example, maybe you rely on a third-party service that lets you compare two items but does not provide you with a hash value. Or maybe you simply don't know the distribution of the items, so it's hard for you to write a good hash function. For instance, the items may be large strings of text. You can of course compare them. But to create a good hash function for them, you'd need to know a bit more about how they are distributed in the space of all possible strings. Maybe hashing the first few characters is good enough -- but that won't work if most of your strings start with the same prefix. Maybe splitting into words and hashing word frequencies is good -- but not if many strings are just reorderings of the same words. And so on.

ygra 7y ago
You could still use a TreeSet which only requires ordering and equality, but not hashing. As a side note, though, your earlier example would not be comparable via Equals, as it violates transitivity. Which is also what makes it impossible to generate a hash code consistent with its Equals implementation.
- _cs2017_ 7y ago
  Oh yeah absolutely you can use better structures even without hashing, I was just saying that a hash table isn't always an option. Lack of transitivity: you can still dedupe based on a transitive closure of whatever relationship I provide. It's easy if I want to dedupe numbers closer than 0.01 (using sorting) but much harder to do it efficiently for vectors.
- Thiez 7y ago
  > Which is also what makes it impossible to generate a hash code consistent with its Equals implementation. How so? `return 0;` is always a legal hash function, albeit a pretty lousy one.
jblow 7y ago
Hashing text is one of the easiest, most common uses of hashing. As for your first example “you may be relying on a 3rd party service that compares things”, has this ever happened in the history of the universe?
- ezrast 7y ago
  Maybe not, but I bet "someone else overrode == and you've been told not to mess with it" has.
- _cs2017_ 7y ago
  Hashing text isn't hard but to do it efficiently you may need to know the distribution. Imagine you want to dedupe 1000 text documents each 1TB in size. Hashing naively would require reading 1000 TB and would be horribly inefficient. Hashing the short prefix would be better but you need to know how long of a prefix is sufficient to avoid too many collisions. Sorting might be safer from efficiency perspective in this case unless you know a bit more about your data set. About 3rd party service: let's say you have images of faces and you want to dedupe them. A third party face comparison service could be a reasonable option. (And as another comment suggested, third party could be a different group in the same company, whose code base isn't trivial to modify.)
  - ww520 7y ago
    Isn't sorting 1000 of 1TB strings even more inefficient? You need to read and compare the 1TB strings 1000 * log(1000) or 3000 times, while hashing only needs 1000 times.
    - _cs2017_ 7y ago
      Typically, you can tell the order between two strings early, after you read just the starting few characters. So for comparison you would usually read maybe 10 bytes per file on average, or 3 x 1000 x 10 bytes = 30KB in total. Or maybe 30MB if the strings have long common prefixes. Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible. Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.

ygra 7y ago

You could still use a TreeSet which only requires ordering and equality, but not hashing. As a side note, though, your earlier example would not be comparable via Equals, as it violates transitivity. Which is also what makes it impossible to generate a hash code consistent with its Equals implementation.

_cs2017_ 7y ago
Oh yeah absolutely you can use better structures even without hashing, I was just saying that a hash table isn't always an option. Lack of transitivity: you can still dedupe based on a transitive closure of whatever relationship I provide. It's easy if I want to dedupe numbers closer than 0.01 (using sorting) but much harder to do it efficiently for vectors.
Thiez 7y ago
> Which is also what makes it impossible to generate a hash code consistent with its Equals implementation. How so? `return 0;` is always a legal hash function, albeit a pretty lousy one.

jblow 7y ago

Hashing text is one of the easiest, most common uses of hashing. As for your first example “you may be relying on a 3rd party service that compares things”, has this ever happened in the history of the universe?

ezrast 7y ago
Maybe not, but I bet "someone else overrode == and you've been told not to mess with it" has.
_cs2017_ 7y ago
Hashing text isn't hard but to do it efficiently you may need to know the distribution. Imagine you want to dedupe 1000 text documents each 1TB in size. Hashing naively would require reading 1000 TB and would be horribly inefficient. Hashing the short prefix would be better but you need to know how long of a prefix is sufficient to avoid too many collisions. Sorting might be safer from efficiency perspective in this case unless you know a bit more about your data set. About 3rd party service: let's say you have images of faces and you want to dedupe them. A third party face comparison service could be a reasonable option. (And as another comment suggested, third party could be a different group in the same company, whose code base isn't trivial to modify.)
- ww520 7y ago
  Isn't sorting 1000 of 1TB strings even more inefficient? You need to read and compare the 1TB strings 1000 * log(1000) or 3000 times, while hashing only needs 1000 times.
  - _cs2017_ 7y ago
    Typically, you can tell the order between two strings early, after you read just the starting few characters. So for comparison you would usually read maybe 10 bytes per file on average, or 3 x 1000 x 10 bytes = 30KB in total. Or maybe 30MB if the strings have long common prefixes. Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible. Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.