What is Anti hash test case?

I saw editorial of first problem of JULY LONG DIV1 (missing a point) and there is a section which says :-

We could think that simply changing the data structure to a hash-based one with O(1)O(1) queries/updates (like unordered_map in C++ or HashMap in Java) should work, yes it may do trick and our complexity would be O(N)O(N), however I was evil and included some antihash tests.

Can someone tell me what antihash test is ?

PS: I also google about it but didn’t understand.

If you want to know about this then read about hash table. Then you will know the problems with unordered map and in which case it leads to O(n).

You can Refer this for detailed Explaination - Click Here

1 Like

The thing is, everyone is referring to the same blog XD

Worst case scenario when collisions occurs; basically tester had generated a test case in such a way that while insertion operation, there will be O(n) collisions. As everyone knows how unordered maps are implemented i.e. which function is used … so it is possible to generate such a case.

I read anti-hash in polynomial hash , what I understood is we use larger prime base and modulus so to generate test case which has collision is very hard and nearly impossible , so anti hash set are those for which collision occurs and if we take larger prime base and modulus then generation of anti - hash set is nearly impossible

1 Like

This one too :
https://codeforces.com/blog/entry/4898
https://codeforces.com/blog/entry/60445?f0a28=1

1 Like

yes,actually this is so detailed blog that half of the things was not clear to me!