What is Anti hash test case?

1

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.

2

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).

3

You can Refer this for detailed Explaination - Click Here

1 Like
4

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

5

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.

6

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

2 Likes
7

This one too :

1 Like
8

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