-is-this-fft-'s blog

List of problems I've solved using unordered_map
By -is-this-fft-, history, 3 weeks ago, In English

I'm just in a funny mood. Don't take this post too seriously.

These are all of the problems I've solved using unordered_map. This should be a complete list. For context, I've solved maybe around 4000 problems in total?

I think neither solution is intended. The moral of the story: this class (and unordered_set) are very rarely if ever necessary in competitive programming. Yes, in theory they can do in $$$O(1)$$$ what map does in $$$O(\log n)$$$. In practice, they have a pretty large constant and are maybe only marginally faster than map. And that's not to mention all the times you can get hacked on it.

  • Vote: I like it
  • +163
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

most people gravitate towards them essentially because they have been "sold" this idea of having constant lookup time which is neither guarantee-able nor safe from poor performance. funnily enough, the logarithmic retrieval complexity that they despise so much isn't even a bottleneck in most cases, is much safer compared to getting unnecessary time limit exceeded verdicts because you didn't write a custom hash lol. but hey, to each their own.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    the logarithmic retrieval complexity that they despise so much isn't even a bottleneck in most cases

    Moreover, in cases where it is a bottleneck, unordered_map usually doesn't help. This list would be 10 or so problems longer if I included problems where I tried that.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it +25 Vote: I do not like it

      I remember atleast 2 problems where i tried umap and then replaced by a vector with binary search (granted this cant be done for all problems)

      The vector and binary search variant was 2 — 3x faster atleast (maybe more, i have forgotten)

      → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      also, there's one more issue (a gcc implementation issue to be precise) with unordered_map which i personally didn't know about until recently. it can be found here

      → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This one here is one of the problems where using map leads to a time limit exceeded in tc 6 But unordered_map with a custom hash works

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        287988574

        I don't see why either of them is necessary. Of course this list would be much longer if I replaced all arrays in my submissions with unordered_maps.

        → Reply
»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

But the conventional wisdom is: when in doubt, just use a hashmap.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I've only ever heard this in the context of interview prep, not cp lol

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is gp hash table safe every time we want O(1)?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    the general rule is that whenever you see "every time", the answer is probably no. moreover, you might want to refer to this to dig more about pbds (the "a better hash function" section might be helpful).

    → Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I think you meant: Yes, in theory they can do in O(n) what map does in O(logn).

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome :)

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

When I read the title (and your handle), I was expecting to see nothing but empty list in this post

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am surprised. I completely agree that it is not common to see unordered map being helpful but I am sure I had much more than 2 such occasions. "Create one large unordered map and reserve it with a big number at the beginning of the solution" is a relatively common idea that I'd say I use around once a year.

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

It is absolutely possible to write a completely safe O(1) hash table, see https://en.wikipedia.org/wiki/Universal_hashing and with also rehashes that detect if too many collisions are present. It is mathematically sound assuming source of randomness is proper, and even not it is almost impossible to make a hack case that simultaneously break two hashes. The issue is it will degrade into the time advantage against map/set even more. Therefore, for all practical purposes unordered_map should be regarded as O(log n) practically.

Worth mentioning that there are many cases radix sort (which sorts equal value together) may be sufficient.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

funny

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

+this

(unordered_set, though)

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I needed to use in this problem 1439B - Graph Subset Problem and it still the only one for me. Upd: unordered_set

→ Reply