7 ms·

"Hashes are always O(1) reads, inserts and writes." Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost requ

• deleted 11y ago
  [deleted]
• seubert 11y ago
  It's even tagged "bad-theory." I think it's pretty clearly a joke! A really good one!
  • dhimes 11y ago
    "And we can’t forget our favorite JavaScript interview question of all time: If you only had twenty-four hours to implement arrays in JavaScript, how would you do it?"
    • pkaye 11y ago
      I'm not really versed on JavaScript. I presume this is a joke about the lack of a proper array structure in JavaScript? How would one answer this question anyway?
      • aggronn 11y ago
        This is probably intended to be a joke about how Javascript was originally developed over about 10 days, which has been the root of many of JS's problems. http://www.computer.org/csdl/mags/co/2012/02/mco2012020007.pdf http://www.computer.org/csdl/mags/co/2012/02/mco2012020007.p...
        • roghummal 11y ago
          But this heritage produced, years later, a great presentation about the evolution of JavaScript... that was best viewed without JavaScript.
      • nawitus 11y ago
        While it's probably joke, JavaScript's Array is fine (although it's more like a 'vector'). JavaScript VMs implement it as a real array (in fact, plain objects are often optimized into arrays too).
    • mdaniel 11y ago
      Aren't they just objects that have integer properties; that's why you can for (k in ['a', 'b']) { console.log(k); } and get back 0, 1? However: var a = {0:'a', 1:'b'}; for (k in a) { console.log(k); } also outputs 0, 1. Edit: turns out, you can even have doubles, too: var weird = {3.14:'hello', 6.28:'world'}; // for loop above emits: 3.14, 6.28 console.log(weird[3.14]); // emits 'hello'
      • tomjakubowski 11y ago
        JavaScript objects can only have string keys (this may have changed in ES2015 with Symbols). If you pass a non-string value in an object literal or inside a []-accessor, that value is converted to a string.
      • chriswarbo 11y ago
        > Edit: turns out, you can even have doubles, too: That's because Javascript doesn't actually have integers, it just has "Number": > The Number type has exactly 18437736874454810627 (that is, 264−253+3) values, representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic http://www.ecma-international.org/ecma-262/5.1/#sec-8.5 http://www.ecma-international.org/ecma-262/5.1/#sec-8.5
  • mutagen 11y ago
    I think I came around to that realization when he starts comparing Postgres to HTML tables.
    • justaaron 11y ago
      sounds reasonable. normalization vs denormalization ok, the last paragraphs kind of give it away... but there are good points in terms of keeping the data flat
• pmelendez 11y ago
  > Linked lists don't suffer from this problem, but at the cost of 1-2 pointers per item. Another cost is the cache misses. If you are doing operations in a sequential fashion using an array would have a significant advantage if the number of elements is high. That's another tradeoff to take in consideration.
  • adrusi 11y ago
    It can be avoided by choosing a good allocation strategy for the linked list, allocating nodes in an arena can eliminate cache misses.
    • yoklov 11y ago
      You'll still have more than if you had used an array, due to the low information density (2 extra pointers / node).
• masklinn 11y ago
  > Linked lists don't suffer from this problem, but at the cost of 1-2 pointers per item. And decreased memory locality (more cache misses) and increased number of allocations.
• pmalynin 11y ago
  O(n) in the size of the string not the hash map. Also, if the key space is known before hand, it is possible to build a perfect minimal hash table with 1.3n total keys (n is the size of the keyspace)
• SilasX 11y ago
  >Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation. Yeah, I know, it always came off to me as BS to repeat that hashes are O(1) lookup, like we're making a special exception. Anywhere else, you can look up the algorithm and derive its big-O without having to memorize, but not this one. Pretty clearly, as the hash table grows linearly, the keyspace has to grow linearly and the key size logarithmically. Since you get the keys from the output of a (nice, well-mixed) hash function, then the computation for where to insert has to increase logarithmically -- a longer hash output requires more steps. You only get O(1) by selectively ignoring one kind of asymptotic behavior (that of the computations needed for the hash). Reddit discussion: http://www.reddit.com/r/compsci/comments/2z74z8/why_is_hashtable_lookup_o1_rather_than_olog_n_or/ http://www.reddit.com/r/compsci/comments/2z74z8/why_is_hasht...
  • Cushman 11y ago
    This is mostly an issue with terms. Most (all?) of the operations we call constant-time, say, comparison, are technically logarithmic in the number of bits on real computers. Since that's usually not relevant to big-O analysis, we can sidestep the issue by specifying what we're counting: rather than say that mergesort is in O((log n) log (log n)) time, we say it takes O(n log n) comparisons. Whether you think of that as a theoretical computer with a constant-time comparison instruction or as a real computer with a commonsense (2^64) upper bound, the upshot is that we don't care. As long as what we're studying is sorting, not comparison, it will fall out of every algorithm, so the difference isn't important even in theory. It's still an important thing to notice, though-- there are plenty of cases where you definitely do care about counting bits. In more detail: http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time http://cs.stackexchange.com/questions/1643/how-can-we-assume...
    • deleted 11y ago
      [deleted]
    • brudgers 11y ago
• bane 11y ago
  I don't know why the complexity estimates I find for Hashes are always so bad. They never account for growth (or depending on the implementation shrinking on delete), never account for the hash function, etc. By the time you hash a key, you could have likely already inserted it into a trie. Lookups on hashes are also not O(1) for similar reasons. You have to hash the search string, then compare the value at whatever location it hashed to (usually a string-comparison operation which aren't O(1)) and depending on the collision strategy, do more things if it doesn't match, but isn't an empty value.
  • chrisseaton 11y ago
    When you say O(something), the something has a unit. Hash table lookups and insertions take time O(1), when talking about number of items already in the hash table - and that 'when talking about' is implicit and doesn't have to be said as anyone talking about the complexity of a hash table knows that, or would state otherwise as it would be an exception. Talking about the length of strings used as keys in the hash table is therefore nonsense when we have already agreed that we're talking about the number of elements in the hash table, as length of the strings isn't a parameter in that function. And they never account for growth - yeah, it's amortised isn't it? That's what we wanted to do when we do an O(). I mean what you are proposing would be an interesting study - the complexity of hash tables parameterised for all sorts of different properties such as the size increase function or the load factor or whatever, but it's not what anyone means when they talk about complexity of a hash table unless they state otherwise. So nobody's getting it wrong or making a mistake. They're using some assumptions that everyone's already agreed on and know about. If you want to talk about the complexity of something else you need to clarify.
    • rnovak 11y ago
      I have two kind of nits with this logic, but I could totally be wrong, and you should feel absolutely free to correct me. I'm fairly positive that a unit of measure should _never_ be variable, otherwise it's fairly pointless. And if you don't think hashing a 1TB string takes significantly longer than a 100byte string ... Futher more, big O notation is supposed to be a wide upper bound, but I don't think that works well if it's not actually an upper bound. If you were to tell your bosses something took constant time, and it took an hour for string A (1TB) and 100ms for string B (10B), I'm pretty sure your opinion wouldn't mean much after that. The hashmap should absolutely be considered in terms of the hash function, because it's the longest running part of the algorighthm. To do otherwise is disingenous. Using that logic, I could call any iterative algorithm O(1) since the top level function only gets called once.
• nhaehnle 11y ago
  computing the hash of a string key is typically an O(n) This is a good point, though to be fair, this aspect of it is usually also ignored when analyzing the main alternative data structures, which are balanced binary trees. At least every successful lookup in such a tree with strings as keys also has to read the entire string. This means that hashes probably still have an advantage over balanced binary trees. Tries, on the other hand, could really beat hashes when the keys are strings. In practice, they might have a cache and branching disadvantage, though.
  • tikhonj 11y ago
    Actually, modern tries can have good cache behavior, especially at larger sizes. Hash maps inherently store data haphazardly inside themselves while tries keep it in order with similar keys near each other in memory. At the very least, this makes it easier for your algorithms to be more cache friendly, because tries' cache behavior is predictable in a way that hash maps' isn't. This is even more relevant for branch prediction: hash functions (by design) are harder to predict, giving the lookup algorithm of a trie an advantage. A cache aware design like "adaptive radix trees" delivers really good performance in practice, comparable or better than hash maps while also supporting fast iteration and certain queries (like iterating over all keys with a given prefix). Take a look at the adaptive radix tree paper[1]: the idea is very accessible, and the resulting performance very impressive. They also generalize the system to work with different types of keys through a systematic method for turning values into binary strings. [1]: http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf
• sorokod 11y ago
  > computing the hash of a string key is typically an O(n) operation. When strings are immutable, the hash values can be cached so the computation is amortized (this is how it works in Java)
• fiatmoney 11y ago
  Additionally, it's provable that in the context of a physical computer, no data structure actually has O(1) read / write / anything performance over an arbitrary amount of data. Consider that the universe enforces both a maximum information density per cubic meter, and a maximum speed at accessing a given physical location.
• LgWoodenBadger 11y ago
  Worst case performance of a Map is O(n).
• the8472 11y ago
  > computing the hash of a string key is typically an O(n) operation. The n in operation time on data structures usually refers to the number of members in the data structure. String length would be a different variable. For example worst case for finding a string member in a linked list would be O(n * k) where n is the elements in the linked list and k is the string length. I.e. the worst case here assumes lots of members with shared prefixes. So the O(1) in hash tables actually is O(1 * k). This distinction often is important because the length of strings and the number of members are independent variables. And for many use-cases (e.g. member names in classes or text-protocol keywords) k is essentially fixed, e.g. a maximum member name length of 255 characters or a similar limitation. And for big O notation that means O(1 * 1), since it's a constant.
• m0llusk 11y ago
  How big is this hash? If accessing it forces paging then the performance cost could be quite large. And then it might be unfortunate enough to have hash buckets for collisions.