algoskipper's blog

Unordered Map Mystery
By algoskipper, history, 6 weeks ago, In English

Question link

Using unordered map with custom hash mentioned below for storing frquency/kind of prefix sum but gives TLE and using map gets accepted.

For the first time I have seen unordered map with this custom hash is getting TLE because of it.

(Custom hash from blog )

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
           x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void solve()
{
  
  long long n;cin>>n;
  long long a[n];f(n)cin>>a[i];
  unordered_map<long long,long long,custom_hash>lp;
  lp[0]++;
  long long s=0;long long ans=0;
  f(n){
    s+=a[i];
    if(lp[s]>0){ans++;s=0;lp.clear();lp[0]++;}
    else lp[s]++;
  }cout<<ans<<endl;
}

Can anyone please explain it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's literally explained so well in the blog you linked. Why do you want the explanation again?

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

    In blog, Its saying that using custom hash with unordered map is fine and can be restricted by getting tle and it worked for me untill above mentioned code gave Tle to unordered map with cutsom hash while gp_hash_table with custom hash and map is getting accepted.

    That's the confusion in my mind that why i want some clarifications

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      f(n){
    ....
    ....
    lp.clear()
    ....
}

      lp.clear() is a O(N) operation. You code essentially runs into O(N^2) in worst case.

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

This has to do with GCC's bug for the unordered classes' clear() method. Instead of lp.clear(), try creating a new object lp = unordered_map<long long,long long,custom_hash>() (a bit ugly D:).

For more info check out this blog Blowing up unordered_map 2024 edition.

→ Reply