5 ms·

Ironically, the universal terms for ‘hashes’ are ‘map,’ ‘associative array’ or, at the worst, ‘table.’ Even ‘dictionary’ makes sense and is definitely used outs

by aasasd 8y ago

Ironically, the universal terms for ‘hashes’ are ‘map,’ ‘associative array’ or, at the worst, ‘table.’ Even ‘dictionary’ makes sense and is definitely used outside of MS. Hashes are completely different things, the use of them is an implementation detail and not necessary.

CydeWeys 8y ago
OK, I'll bite. How do you get O(1) lookup without using a hashtable?
- outadoc 8y ago
  That's not the issue. If you have a Dictionary interface that says it provides you with O(1) lookup, you don't care if it uses a hashtable or magic dust to do it.
  - CydeWeys 8y ago
    My point is that, since a hashtable is the only way to provide the desired performance characteristics, it's not unreasonable at all to say "I want a hashtable", instead of "I want a Dictionary implementation with O(1) lookup". The former is more succinct.
    - outadoc 8y ago
      I get ya, but I think you just described abstraction. Sure, if we're speaking low-level, we might as well use "hashtable".
      - CydeWeys 8y ago
        When someone says "hashtable" in the context of writing software, they're most often specifying desired performance characteristics, not the specific implementation details. This is how Perl does it, for example. Also, there are Map implementations that don't have these performance characteristics, e.g. a TreeMap in Java which internally uses a red/black tree and thus provides logarithmic lookup and insertion. If I'm writing something that needs to do a lot of efficient lookups but only write "Map" in the spec, there's danger that the wrong thing will be used, and performance will suffer. It really does need a hashtable, not just a generic lookup interface.
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
- rurban 8y ago
  For a small amount of short keys hash tables perform worse than a simple linear scan. 127 is a good number but it depends on the design. O(1) is completely missing the point of hidden constant factors. For many applications, like the one used in javascript, ruby or perl - map as objects with 3-7 short keys - hash tables are totally overblown. For compile-time known keys you better create a perfect hash table, where the fastest could be a switch of pre-compiled word-aligned memcmp statements. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-and-faster-than-memcmp.html http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an... Haven't done that yet with SIMD instructions, which should be much faster. For mostly read maps (like e.g. for mysql applications) it's mostly faster to run-time compile a shared lib with a perfect hash table. Compilers are very fast with data-only. For many other use cases a judy tree, compressed patricia tree, ctrie, HAMT, CHAMP or even a btree may be faster than a typical hash table. Esp. considering cache oblivious architectures. The modern swiss table doesn't look like an old-style hash table anymore, more like a patricia tree. E.g. almost everything is faster than the default C++ hash table.
- Arkanosis 8y ago
  Lookup in a trie is O(L) where L is the length of the key; not that different if you take into account that to lookup into a hashtable, you also have to compute the hash of the key.
- bloak 8y ago
  In theory, I don't think hash tables are O(1): even if you ignore the atrocious worst-case performance and just look at average performance you still have to make the size of the hash depend on the number of entries, which brings in a factor of log(n), which is exactly what tree-based algorithms have. In practice, the performance of a hash table definitely does depend on the number of entries because of the cache hierarchy and stuff like that. I could easily be wrong about the theory: there are, of course, lots of different kinds of hash table and different ways you might formalise the meaning of "O(1)".
  - palant 8y ago
    You are definitely right for most hash tables. Determining the right bucket is O(1) but there will be collisions. Open hashing solves it by creating a linked list within buckets which you will need to traverse. Closed hashing solves it by probing, you might test several buckets before finding the right entry. In both cases, you get O(log(n)) as the average lookup performance. You actually get O(1) with perfect hash functions, but doing so requires choosing a hash function by the data set. This is normally only feasible for precalculated hash tables, not those that are being filled dynamically.
    - CydeWeys 8y ago
      The average lookup performance on a hashtable is definitely not O(logN) -- it's amortized O(1). Just Google for "hash table performance" and observe that all the results are saying O(1), not O(logN). I'd like to request some reputable sources from you showing O(logN). The modal number of buckets you have to look into (or the modal size of the linked list) is 1. If it's more than 1, then your hash table is too full, and you need to enlarge it. This is admittedly an expensive operation, but it still amortizes out to O(1). And if you know in advance how many elements will be in a hashtable (this is common), then you never even need to resize.
      - palant 8y ago
        It should be obvoius that hash table lookups are above O(1) as long as collisions exist. Tweaking the load factor can reduce the probability of collisions, but that's merely a constant factor to the lookup complexity. As to whether O(log(n)) is a good approximation for the average, we can certainly discuss that. It depends a lot on the algorithm, but https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... shows (first graph) that the reality is typically even above logarithmic for some reason.
- palant 8y ago
  There are some options. For example, if the indexes are known to be within a certain range, a plain array will do better. For tables below a certain size, an array of key/value tuples might also perform better. An implementation could even switch between the underlying approaches depending on the data at hand, choosing between hash tables and something else depending on what should perform better. Yes, the "hash" part is an implementation detail. The performance is also an implementation detail by the way. Often, tables will optimize for a different criterion such as memory efficiency. Lookup will be less efficient then. And, as another person noted, you cannot really expect O(1) from a hash table anyway.

by aasasd 8y ago

CydeWeys 8y ago

OK, I'll bite. How do you get O(1) lookup without using a hashtable?

outadoc 8y ago
That's not the issue. If you have a Dictionary interface that says it provides you with O(1) lookup, you don't care if it uses a hashtable or magic dust to do it.
- CydeWeys 8y ago
  My point is that, since a hashtable is the only way to provide the desired performance characteristics, it's not unreasonable at all to say "I want a hashtable", instead of "I want a Dictionary implementation with O(1) lookup". The former is more succinct.
  - outadoc 8y ago
    I get ya, but I think you just described abstraction. Sure, if we're speaking low-level, we might as well use "hashtable".
    - CydeWeys 8y ago
      When someone says "hashtable" in the context of writing software, they're most often specifying desired performance characteristics, not the specific implementation details. This is how Perl does it, for example. Also, there are Map implementations that don't have these performance characteristics, e.g. a TreeMap in Java which internally uses a red/black tree and thus provides logarithmic lookup and insertion. If I'm writing something that needs to do a lot of efficient lookups but only write "Map" in the spec, there's danger that the wrong thing will be used, and performance will suffer. It really does need a hashtable, not just a generic lookup interface.
deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
rurban 8y ago
For a small amount of short keys hash tables perform worse than a simple linear scan. 127 is a good number but it depends on the design. O(1) is completely missing the point of hidden constant factors. For many applications, like the one used in javascript, ruby or perl - map as objects with 3-7 short keys - hash tables are totally overblown. For compile-time known keys you better create a perfect hash table, where the fastest could be a switch of pre-compiled word-aligned memcmp statements. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-and-faster-than-memcmp.html http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an... Haven't done that yet with SIMD instructions, which should be much faster. For mostly read maps (like e.g. for mysql applications) it's mostly faster to run-time compile a shared lib with a perfect hash table. Compilers are very fast with data-only. For many other use cases a judy tree, compressed patricia tree, ctrie, HAMT, CHAMP or even a btree may be faster than a typical hash table. Esp. considering cache oblivious architectures. The modern swiss table doesn't look like an old-style hash table anymore, more like a patricia tree. E.g. almost everything is faster than the default C++ hash table.
Arkanosis 8y ago
Lookup in a trie is O(L) where L is the length of the key; not that different if you take into account that to lookup into a hashtable, you also have to compute the hash of the key.
bloak 8y ago
In theory, I don't think hash tables are O(1): even if you ignore the atrocious worst-case performance and just look at average performance you still have to make the size of the hash depend on the number of entries, which brings in a factor of log(n), which is exactly what tree-based algorithms have. In practice, the performance of a hash table definitely does depend on the number of entries because of the cache hierarchy and stuff like that. I could easily be wrong about the theory: there are, of course, lots of different kinds of hash table and different ways you might formalise the meaning of "O(1)".
- palant 8y ago
  You are definitely right for most hash tables. Determining the right bucket is O(1) but there will be collisions. Open hashing solves it by creating a linked list within buckets which you will need to traverse. Closed hashing solves it by probing, you might test several buckets before finding the right entry. In both cases, you get O(log(n)) as the average lookup performance. You actually get O(1) with perfect hash functions, but doing so requires choosing a hash function by the data set. This is normally only feasible for precalculated hash tables, not those that are being filled dynamically.
  - CydeWeys 8y ago
    The average lookup performance on a hashtable is definitely not O(logN) -- it's amortized O(1). Just Google for "hash table performance" and observe that all the results are saying O(1), not O(logN). I'd like to request some reputable sources from you showing O(logN). The modal number of buckets you have to look into (or the modal size of the linked list) is 1. If it's more than 1, then your hash table is too full, and you need to enlarge it. This is admittedly an expensive operation, but it still amortizes out to O(1). And if you know in advance how many elements will be in a hashtable (this is common), then you never even need to resize.
    - palant 8y ago
      It should be obvoius that hash table lookups are above O(1) as long as collisions exist. Tweaking the load factor can reduce the probability of collisions, but that's merely a constant factor to the lookup complexity. As to whether O(log(n)) is a good approximation for the average, we can certainly discuss that. It depends a lot on the algorithm, but https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... shows (first graph) that the reality is typically even above logarithmic for some reason.
palant 8y ago
There are some options. For example, if the indexes are known to be within a certain range, a plain array will do better. For tables below a certain size, an array of key/value tuples might also perform better. An implementation could even switch between the underlying approaches depending on the data at hand, choosing between hash tables and something else depending on what should perform better. Yes, the "hash" part is an implementation detail. The performance is also an implementation detail by the way. Often, tables will optimize for a different criterion such as memory efficiency. Lookup will be less efficient then. And, as another person noted, you cannot really expect O(1) from a hash table anyway.