Блог пользователя neal

Blowing up unordered_map, and how to stop getting hacked on it
Автор neal, 6 лет назад, По-английски

C++ has always had the convenient data structures std::set and std::map, which are tree data structures whose operations take time. With C++11, we finally received a hash set and hash map in std::unordered_set and std::unordered_map. Unfortunately, I've seen a lot of people on Codeforces get hacked or fail system tests when using these. In this post I'll explain how it's possible to break these data structures and what you can do in order to continue using your favorite hash maps without worrying about being hacked .

So how are they hackable? We always assume hash maps are O(1) per operation (insert, erase, access, etc.). But this depends on a key assumption, which is that each item only runs into O(1) collisions on average. If our input data is completely random, this is a reasonable assumption. But this is no longer a safe bet when the input isn't random, especially so if someone is adversarially designing inputs to our code (a.k.a. hacking phase). In particular, if they know our hash function, they can easily generate a large number of different inputs that all collide, thus causing an O(n2) blow-up.

We'll prove that now by blowing up unordered_map. In order to do that, we first have to determine exactly how it's implemented. For this we can dig into gcc's implementation on GitHub: https://github.com/gcc-mirror/gcc.

After some searching around we run into unordered_map.h. Inside the file we can quickly see that unordered_map makes use of __detail::_Mod_range_hashing and __detail::_Prime_rehash_policy. From this we can guess that the map first hashes the input value and then mods by a prime number, and the result is used as the appropriate position in the hash table.

Some further searching for _Prime_rehash_policy leads us to hashtable_c++0x.cc. Here we can see that there is an array called __prime_list, and the hash table has a policy to resize itself when it gets too large. So we just need to find this list of primes.

The one include on this file leads us to hashtable-aux.cc. Aha, here is the list we're looking for.

One more thing: we need to know the hash function unordered_map uses before modding by these primes. It turns out to be quite simple: the map uses std::hash, which for integers is simply the identity function. Armed with this knowledge, we can insert lots of multiples of one of these primes to the map in order to get n2 blow-up. Not all of the primes work though, due to the resizing policy of the map; in order for a prime to work, we need the map to actually resize to this prime at some point in its set of operations. It turns out the right prime depends on the compiler version: for gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work. Run the code below in Custom Invocation and see what output you get.

#include <ctime>
#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 2e5;

void insert_numbers(long long x) {
    clock_t begin = clock();
    unordered_map<long long, int> numbers;

    for (int i = 1; i <= N; i++)
        numbers[i * x] = i;

    long long sum = 0;

    for (auto &entry : numbers)
        sum += (entry.first / x) * entry.second;

    printf("x = %lld: %.3lf seconds, sum = %lld\n", x, (double) (clock() - begin) / CLOCKS_PER_SEC, sum);
}

int main() {
    insert_numbers(107897);
    insert_numbers(126271);
}

Depending on which compiler version you are using, one of these two numbers will take much longer than the other. There are several other primes that also work; try some more for yourself!

Note that for other hash tables like cc_hash_table or gp_hash_table (see Chilli's helpful post), it's even easier to hack them. These hash tables use a modulo power of two policy, so in order to make a lot of collisions occur we can simply insert a lot of numbers that are equivalent, say, modulo 216.

Don't want to be hacked?

Let's look at how to safeguard these hash maps from collision attacks. To do this we can write our own custom hash function which we give to the unordered_map (or gp_hash_table, etc.). The standard hash function looks something like this:

struct custom_hash {
    size_t operator()(uint64_t x) const {
        return x;
    }
};

However as we mentioned, any predictable / deterministic hash function can be reverse-engineered to produce a large number of collisions, so the first thing we should do is add some non-determinism (via high-precision clock) to make it more difficult to hack:

struct custom_hash {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return x + FIXED_RANDOM;
    }
};

See my post on making randomized solutions unhackable for more details. Awesome, so our hash is perfectly safe now, right? Not so fast. All we've done is add the same fixed number to every input to the function. But if two numbers a and b satisfy a = b (mod m), then a + x = b + x (mod m) for every x as well. Similar problems occur for other very simple hash functions: multiplying by a random large odd number (and overflowing mod 264) is likely effectively modulo p, but will be problematic for gp_hash_table's power of two policy; the same situation occurs for xor-ing with a random number.

A slightly better hash function like the following may look enticing:

struct custom_hash {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

However, if you are using a gp_hash_table this actually still leaves you susceptible to hacks from a strong enough adversary. In particular, after inserting the numbers (1 << 16) + 1, (2 << 16) + 2, (3 << 16) + 3, ..., into this hash table, all of the outputs will be equivalent modulo 216. (Do you see why?)

So we want a better hash function, ideally one where changing any input bit results in a 50-50 chance to change any output bit. Note for example that in the hash function x + FIXED_RANDOM, this property is not satisfied at all; for example, changing a higher bit in x results in a 0% chance of changing a lower bit of the output.

Personally, I like to use splitmix64, which is extremely high-quality and fast; credit goes to Sebastiano Vigna for designing it. Adding all this together, we have our safe custom hash function:

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};

Now we can simply define our unordered_map or our gp_hash_table as follows:

unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;

Once we use these in our program above, it runs very quickly:

x = 107897: 0.035 seconds, sum = 2666686666700000
x = 126271: 0.031 seconds, sum = 2666686666700000

=====
Used: 109 ms, 9204 KB
  • Проголосовать: нравится
  • +752
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Added to my snippets ;). Amazing Work.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

c++ 17 when set with same key has size larger than 8 it will use RBT to store data.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится 
very useful blog ✋✋
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How convenient! Thanks a lot!

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

very cool. keep it up!

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cool! I'm curious how many people actually do anti-hashing hacks in contest. Could you put the standard unordered_map runtimes on the inputs to use as comparisons to the benchmarks you put at the end? Or does it simply take way too much time to even record?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    The thing about this specific hack is that if anyone successfully makes this hack on anyone else in the contest, their test will be added to system tests which will leave you in trouble. A few examples of recent problems where you can fail for using unprotected unordered_map include 1027F - Session in BSU and 1039C - Network Safety.

    As far as runtime, it gets a bit slower with the custom hash but not too much. Pure unordered_map gives anywhere between 0.00s and 0.04s on non-adversarial cases when running with Custom Invocation, vs. 0.03s with custom hash. If you're concerned with speed then gp_hash_table with the custom hash is the way to go, since it uses power of two modding and linear probing rather than prime modding and collision chaining.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, I wasn't that concerned about the speed of your custom hash. I was curious about the speed of std::unordered_map on the adversarial case that you've created. However, reading it more closely, you have N = 105, so if it really is causing an O(n2) blowup on std::unordered_map, then it's probably too slow to bother recording the time.

      → Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

I like (uintptr_t)main. :) This pointer should be random for every run because of OS security issue.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Nicely written, as always. Thanks!

Whenever someone talks about hacking hashmaps, I think of this problem: https://ipsc.ksp.sk/2014/real/problems/h.html

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

Thanks for this helpful blog. For completeness, it should be noted that the last definition

gp_hash_table<long long, int, custom_hash> safe_hash_table;

should be preceded by 

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

The following is a slight update to your test program.

Update

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How does it compare with alternating max_load_factor of the hash table? because it is runs slower as compared to this trick (Arpa's Blog):

unordered_set<int> numbers;
numbers.max_load_factor(0.25);
numbers.reserve(1<<18);

this gives output of:

x = 107897: 0.018 seconds, sum = 2666686666700000
x = 126271: 0.031 seconds, sum = 2666686666700000
=====
Used: 61 ms, 10600 KB
→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This doesn't make it unhackable, it just changes the prime number that breaks it. Try calling insert_numbers(1056323); instead:

    x = 107897: 0.043 seconds, sum = 2666686666700000
x = 126271: 0.015 seconds, sum = 2666686666700000
x = 1056323: 1.149 seconds, sum = 2666686666700000

=====
Used: 1201 ms, 10456 KB
    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am not sure I understand how it "only" changes the prime number because according to the code, you are inserting numbers with same modulo wrt the prime. Running on equal modulo numbers with:

      unordered_set<int> numbers;
numbers.max_load_factor(0.25);
numbers.reserve(1<<20); // NOTICE THE CHANGE

      which gives output of:

      x = 107897: 0.010 seconds, sum = 2666686666700000
x = 126271: 0.015 seconds, sum = 2666686666700000
x = 1056323: 0.016 seconds, sum = 2666686666700000

=====
Used: 78 ms, 14864 KB

      Also reserve must change according to the elements to be inserted (upper bound to be a power of two). Maybe it's because of rehash scheme when max_load_factor is achieved in the bucket under consideration.

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      What if i need unordered_map<pair<int,int> , int> mp; here first is pair . What if more complex such as use (1,2,3,4) as first , i meant for struct data type first .

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

like splitmix64 is there a good hash function for pairs too?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you have a pair of integers you'd like to hash, you can use the custom hash function above on each of them to get two values a and b. Then combine them in any way you like, e.g., a + b.

    The one issue with a + b is that swapping the two elements of the pair will lead to the same hash value. This isn't a problem from a theory point of view since "O(1) collisions on average" is still valid, but to avoid this situation you can switch to a non-symmetric function such as 3 * a + b or a ^ (b >> 1).

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Using the idea in neal's comment

    struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(pair<uint64_t,uint64_t> x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
	}
};
    → Ответить
»
5 лет назад, # |
← Rev. 7   Проголосовать: нравится -10 Проголосовать: не нравится

Thanks for this blog, neal. Can you recommend a fast hash function that is not difficult to remember (for gp_hash_table)?

Can xorshift64 be such function?

uint64_t xorshift64(uint64_t x)
{
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return x;
}
UPD. Okay, this is bad hash function.

UPD2. I got idea about calculation polinomial hash from s, where x = s[0]+(s[1]<<16)+(s[2]<<32)+(s[3]<<48). Tested it and it is fast.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

very helpful !!

you write very good and you need just another blog like this one to be in "Top contributors List".

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

neal Why use size_t as the return value of operator(), why not int64_t, does it affect the performance of functions

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится 
#include <ctime>
#include <iostream>
#include <unordered_map>
#include <random>
using namespace std;

const int N = 2e5;

void insert_numbers(long long x) {
    clock_t begin = clock();
    unordered_map<long long, int> numbers;
    mt19937 rng(0);
    for (int i = 0; i < N; i++)
        numbers[uniform_int_distribution<int>(0, 1e6)(rng) * x] = i;

    long long sum = 0;

    for (auto &entry : numbers)
        sum += (entry.first / x) * entry.second;

    printf("x = %lld: %.3lf seconds, sum = %lld\n", x, (double) (clock() - begin) / CLOCKS_PER_SEC, sum);
}

int main() {
    insert_numbers(107897);
}

Why does this code take more than 2 seconds in custom invocation with C++17, while the same code with the 1e6 replaced by 1e9 takes less than 100 ms?(also, replacing 1e6 by 1e5 makes the running time over 10 seconds)

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Good question. This is actually quite tricky. It's because the default hash function returns a size_t, and on Codeforces size_t is a 32-bit integer. This means that multiplying by an integer up to 1e9 actually overflows 32 bits when hashed and ends up with a number that is no longer a multiple of our prime.

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I didn't get it. So if I have an array like [1,1,1,1......,1], your hash function is not deterministic because hash(1) != hash(1) because it uses some FIXED_RANDOM. If the FIXED_RANDOM would be the same for all numbers, then I think we are the begining. Correct me if I am wrong. Thanks.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just wanted to ask this, that for largest value possible in long long int x, this x += 0x9e3779b97f4a7c15 expression will overflow bounds of uint64.

Also the argument for hash requires unsigned int64 value, but if we have negative numbers to hash too, then what happens.

Thanks.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks a lot for this post! It was in detail and very useful..

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Absolutely beautiful!

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Hey Nice Blog, But I have a doubt.... I have submitted same code(both have your custom_hash).
Problem : Social Network
My Solutions : unordered_map , unordered_set

I have a doubt that, i am getting TLE while using custom_hash with unordered set, but got ac while using same custom hash in unordered map. is there any reason for this? does your custom hash works faster on map than set or anything else?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Can we use this custom hash in unordered set as well??

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Using map<vector,int> mp; gives me TLE.

I want to use Unordered_map to avoid TLE.

How can i make it? Any help is appreciated. Thanks.

Question : 1225D - Power Products

My Submission : 77023902

neal Please help

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The complexity of your program with map<vector,int> is $$$O(n^2)$$$, assuming that $$$a_i \leq n$$$. Using an unordered_map will just remove a log factor, try improving your complexity by more than that.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

size_t is 32 bit in 32 bit compilers. Is using 64 bit hash function splitmix64 good then? Or do you know any better hash function for 32 bit?

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm getting this weird compiler warning on macOS when I make a basic unordered_map<ll,int,custom_hash>:

ld: warning: direct access in function 'std::_Hashtable<long long, std::pair<long long const, int>, std::allocator<std::pair<long long const, int> >, std::__detail::_Select1st, std::equal_to<long long>, custom_hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_rehash_aux(unsigned long, std::integral_constant<bool, true>)' from file '/var/folders/_4/k4frvr6d1h75g4ggfm5kbs580000gn/T//ccK8c6lm.o' to global weak symbol 'custom_hash::operator()(unsigned long long) const::FIXED_RANDOM' from file '/var/folders/_4/k4frvr6d1h75g4ggfm5kbs580000gn/T//ccK8c6lm.o' means the weak symbol cannot be overridden at runtime. This was likely caused by different translation units being compiled with different visibility settings.

These are my compiler flags

g++-9 -std=c++17 -O2 -Wl,-stack_size -fsanitize=undefined  -Wl,    0x10000000 -Wall -Wshadow  -Wextra -o $1 $1.cpp
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Does this custom hash increases running time because i used this custom hash in a problem and it got Time Limit Exceeded as verdict and without custom hash function it got accepted Link to Accepted solution and Link to TLE solution .

neal or somebody please help...

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We always assume hash maps are O(1) per operation (insert, erase, access, etc.). But this depends on a key assumption, which is that each item only runs into O(1) collisions on average. If our input data is completely random, this is a reasonable assumption. But this is no longer a safe bet when the input isn't random, especially so if someone is adversarially designing inputs to our code

    So if the input is random, custom hash will be worse.

    → Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Tried submitting your exact AC solution but it gives TLE now. Also still TLE for custom hash. Probably codechef updated their testcase.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

i tried using the above hash function for this quesn — https://www.codechef.com/LRNDSA10/problems/MATTEG

but i still get TLE

my solution — https://www.codechef.com/submit/complete/37329776

what am i doing wrong?

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hi I have tried to change (unordered_)map to many thing like this ones but every time I get TLE on last testcase; I think this idea should be change but if anybody can help me, I ll be happy. link of submission

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your article is very helpful for me. I want to share this article to other Japanese, so I translated it to Japanese. 日本語訳(Japanese): https://qiita.com/recuraki/items/652f97f5330fde231ddb

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I ran into this problem while upsolving. Turns out that test case 31 problem F from round 701 was specifically designed to blow up unordered maps. Quite nasty to do that but at least I learnt something. I'm glad I found your post because I had no idea what was going on.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can unordered set collation cause wrong answer ? If anyone know plz reply.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Bump because of recent contest hacks on problem C for this reason.

→ Ответить
»
2 года назад, # |
← Rev. 5   Проголосовать: нравится -21 Проголосовать: не нравится

deleted

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Absolutely perfect! I wanted to increase my knowledge upon this matter and understand what is going underneath the hood explaining the so much hacks we've seen in recent contests for UNORDERED hash map. I think it is not safe at all to use that unordered version.. This blog is bumpped by hacks every now and then lol

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My submission for 1561D1 - Up the Strip (simplified version) is getting TLEed using your custom hash!

Submission : 164724313

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Without using custom_hash :

x = 107897: 0.119 seconds, sum = 2666686666700000
x = 126271: 0.119 seconds, sum = 2666686666700000

using custom_hash. :

x = 107897: 0.154 seconds, sum = 2666686666700000
x = 126271: 0.164 seconds, sum = 2666686666700000

:using c++ 17.

why time is not decreasing ? neal

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    It depends on your specific compiler version. Try some other primes from the list above until you figure out which one is bad for yours in particular

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

TLE solution with your custom hash : 2206 ms

AC solution with normal map : 118 ms

Why?Can you please clarify why this had happened?

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I think .clear() is very slow for hash maps in general

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I also thought that but don't know why it is technically very slow ,can you please come up with details what are the technical reasons .clear() is slow if you have time someday?

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        It's due to a bug on GCC, clear() works in a time complexity of $$$O(\mathbf{capacity})$$$. However, due to the bug, clear() does not clear the capacity (i.e. "deallocate") after clearing, therefore the repeated use of the function takes a massive amount of time.

        → Ответить
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          this bug is in every version of gcc or just in gcc 9.2.1 of atcoder?

          → Ответить
          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            The bug still exists in the latest version (at least up to GCC 11, from what I know) on major Online Judges.

            → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why always using these cryptic hashfunctions with XORs and Shift operations?

Carter-Wegman should do the job perfectly fine, right? https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
ll ra = gen(), rb = gen();              // shall be two random numbers
ll p = (1 << 31) - 1;                   // prime > |U| - bigger than universe size
ll carter_wegmann(ll a){
    return (ra * a + rb) % p;           // the hashmap does a subsequent mod bucket_count
}
→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This looks like it'll probably work fine, but a few reasons that come to mind:

    • mod is much slower than xor, shift, and multiplication with a fixed constant
    • splitmix64 as mentioned above is a perfect bijective mapping from $$$[0, 2^{64})$$$ onto itself; what you wrote above compresses 64-bit numbers into 31-bit numbers which may not be ideal
    → Ответить
»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For some reason, $$$107897$$$ and $$$126271$$$ no longer seem to result in an $$$n^2$$$ blow-up on C++ 20.

I'm not sure exactly why this is the case, since they worked almost a year ago when I made the tests for https://mirror.codeforces.com/contest/1748/problem/C.

This solution used to get TLE, but now passes only on C++ 20.

I have tried several other primes from hashtable-aux.cc and none of them seem to work. neal

→ Ответить
  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    That's not too surprising on a new compiler version. Some of the primes should still work though. Keep trying more!

    → Ответить
  • »
    »
    2 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    For GNU G++20 13.2 (64-bit, winlibs), the best candidates are $$$85229$$$, $$$172933$$$ and $$$351061$$$.

    → Ответить
  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Use $$$85229$$$ for C++23. This should work for C++ 20 also

    → Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Hi Neal! Thank you a lot for the post! Why I don't see any improvements with your hash? I am using the g++ -std=c++20

Without your hash 

x = 107897: 0.055 seconds, sum = 2666686666700000
x = 126271: 0.039 seconds, sum = 2666686666700000

And with your hash 

x = 107897: 0.069 seconds, sum = 2666686666700000
x = 126271: 0.045 seconds, sum = 2666686666700000

On average, they look similar and I didn't see the performance difference as it was described in the post. Why?

→ Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    The hash decreases the probability of an O(n^2) blowup, it doesn't change the complexity or commit to some improvement in the other cases, so...

    → Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Based on my recent tests, using $$$172933$$$ and $$$85229$$$ with g++ -std=c++20 version yields better results. In fact, for different g++ versions, you need to find different numbers, as neal mentioned. You can test within the prime number table to find them.

    → Ответить
»
10 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is there any particular reason to use splitmix64(x + FIXED_RANDOM) instead of splitmix64(x ^ FIXED_RANDOM) which is a little bit faster?

→ Ответить
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think this issue should be patched by Codeforces just like I/O are patched because it's completely technical. I believe many people not using a template (including me) know this one but don't want to implement randomized hashing during the contest because it's just too complicated. (Also this post was posted 5 years ago but no one seemed to give this suggestion)

MikeMirzayanov

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    IO is not patched by CF??? If you do not use fast IO, you will tle on quite a few problems.

    Just use map, its fast enough in 99% cases (umap isnt much faster than map given its high constant)

    → Ответить
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    was it patched recently ?

    → Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Beautifully Explained!! I was doing a porblem on CSES by using sliding window where I got TLE while using unordered_map and then it passed using map, that is how i discovered collisions for the first time:

with unordered_map : CSES Playlist with unordered map

with map : CSES Playlist with map

→ Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Do i have to import something to use hash set error = "identifier "gp_hash_table" is undefined"?? Iam new to all this.. gp_hash_table<long long, int, custom_hash> safe_hash_table;

→ Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It shows compilation error in codeforces. Works fine on my machine.

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Not sure what was up with your machine, but you missed the header <chrono>, hence the CE log: program.cpp:35:51: error: 'std::chrono' has not been declared.

    Either uncomment your bits/stdc++.h declaration, or #include <chrono>.

    → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i got tle with unordereedmap with custom hash https://mirror.codeforces.com/contest/1778/submission/264624245

and AC

With vector

https://mirror.codeforces.com/contest/1778/submission/264626174

so it s not safe always

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you have to understand the fact that your first step is to see whether solution is possible without map then if you see it's not possible without map then it's a question of choosing ordered/unordered.So comparing safety between vector and unordered map is pointless

    → Ответить
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      is there is way to make sur unordered map with chash is o(1) ?

      → Ответить
      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        unordered map in on average $$$O(1)$$$ with custom hash and vector operations is obviously constant $$$O(1)$$$ , so it's little faster than unordered map obviously , your vector solution almost TLEed too(almost 1800 ms),unordered map here didn't act much slower , it's good enough , it's just your solution isn't too good

        → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it applicable to Python dictionaries? Meaning can we use the same hash function within the int wrapper class?
I stumbled upon this blog post: Anti-hash-table test in Python and thought if the solution proposed there is sufficient and secure against the stronger adversaries, like mentioned in this post.

→ Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Useful

→ Ответить
»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the helpful blog. This is really convenient. I recently got hacked for the same reason on using an unordered map. Will implement this next time onwards

→ Ответить
»
4 недели назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

If I had read this blog couple of days ago, my solution in the last contest won't get hacked. I used C++23.

When I ran the above snippet to test time. This is what I got. I am literally shocked.

x = 107897: 0.101 seconds, sum = 2666686666700000
x = 126271: 0.111 seconds, sum = 2666686666700000
x = 85229: 169.391 seconds, sum = 2666686666700000

The prime for C++23 is $$$85229$$$.

Just to see the difference, if you use the same code for map, this is what you'll get on average:

x = 107897: 0.170 seconds, sum = 2666686666700000
x = 126271: 0.166 seconds, sum = 2666686666700000
x = 85229: 0.163 seconds, sum = 2666686666700000

Thanks for this awesome helpful blog <3

→ Ответить
»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can I write the hashing function if I need this in a physical contest (e.g. IOI)? Because memorizing the function is nearly impossible. I am asking solution Only for unordered_map, cause I don't use gp_hash_table.

→ Ответить
»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Question link

Using unordered map with custom hash mentioned above 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.

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

→ Ответить