4 ms·

You aren't really binary searching anymore. If it all fit into the RAM, you might as well just put it into a hashset.

peter_d_sherman 6y ago
You are correct, hashes are tremendously useful for some types of data... But, hashes, while tremendously useful for some types of data, are not necessarily without problems for other data, most notably if the data has the possibility of collisions: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Collision_(computer_science) https://en.wikipedia.org/wiki/Collision_(computer_science) https://danlark.org/2020/06/14/128-bit-division/ https://danlark.org/2020/06/14/128-bit-division/ >"When it comes to hashing, sometimes 64 bit is not enough, for example, because of birthday paradox — the hacker can iterate through random 2^{32} entities and it can be proven that with some constant probability they will find a collision, i.e. two different objects will have the same hash. 2^{32} is around 4 billion objects and with the current power capacity in each computer it is certainly achievable. That’s why we need sometimes to advance the bitness of hashing to at least 128 bits. Unfortunately, it comes with a cost because platforms and CPUs do not support 128 bit operations natively." So, it depends on the data, and what's being done with it, if the possibility of collisions exist, and what the implications of those possibilities are (perhaps hashes are great for speed, and harmless, if not used with respect to passwords, that is, used in some other place in software infrastructure, they might be the right choice for that place...)
- rocqua 6y ago
  Are binary searches that much better than hashmaps if a malicious attacker gets to interact with the system?
  - smabie 6y ago
    Hashmaps are resistant against timing attacks, while binary searches are not.
    - rurban 6y ago
      With possible timing attacks you usually do a full linear search, without early return. This search has always constant time, twice as slow. When the attacker gets to know the seed somehow even hashmaps can be exploited.

You are correct, hashes are tremendously useful for some types of data... But, hashes, while tremendously useful for some types of data, are not necessarily without problems for other data, most notably if the data has the possibility of collisions: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Collision_(computer_science) https://en.wikipedia.org/wiki/Collision_(computer_science) https://danlark.org/2020/06/14/128-bit-division/ https://danlark.org/2020/06/14/128-bit-division/ >"When it comes to hashing, sometimes 64 bit is not enough, for example, because of birthday paradox — the hacker can iterate through random 2^{32} entities and it can be proven that with some constant probability they will find a collision, i.e. two different objects will have the same hash. 2^{32} is around 4 billion objects and with the current power capacity in each computer it is certainly achievable. That’s why we need sometimes to advance the bitness of hashing to at least 128 bits. Unfortunately, it comes with a cost because platforms and CPUs do not support 128 bit operations natively." So, it depends on the data, and what's being done with it, if the possibility of collisions exist, and what the implications of those possibilities are (perhaps hashes are great for speed, and harmless, if not used with respect to passwords, that is, used in some other place in software infrastructure, they might be the right choice for that place...)

rocqua 6y ago
Are binary searches that much better than hashmaps if a malicious attacker gets to interact with the system?
- smabie 6y ago
  Hashmaps are resistant against timing attacks, while binary searches are not.
  - rurban 6y ago
    With possible timing attacks you usually do a full linear search, without early return. This search has always constant time, twice as slow. When the attacker gets to know the seed somehow even hashmaps can be exploited.