-is-this-fft-'s blog

List of problems I've solved using unordered_map
By -is-this-fft-, history, 2 months 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
  • +171
  • Vote: I do not like it

»
2 months 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
  • »
    »
    2 months 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
    • »
      »
      »
      2 months 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
    • »
      »
      »
      2 months 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
    • »
      »
      »
      2 months 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
      • »
        »
        »
        »
        2 months 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
»
2 months 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
  • »
    »
    2 months 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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months 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
»
2 months 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
  • »
    »
    8 days ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    to be more serious, I never really understood when people described hash table insert as O(1). Like big-O is worst case whereas hash table insert is average/expected to be constant

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

      Actually big-O is just a notation to describe the grow rate of functions, and that's it. There is no restriction say big-O should only describe function of complexity in worst case and it's nothing weird to use it to describe function of complexity in average case, and you can plug any function you want into it.

      wiki

      → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome :)

→ Reply
»
2 months 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
»
2 months 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
»
2 months 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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

funny

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

+this

(unordered_set, though)

→ Reply
»
2 months 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
»
8 days ago, # |
  Vote: I like it -16 Vote: I do not like it

I can't say I found this too funny, but you are one of the chillest high-rated people here so I have given you an updoot.

→ Reply