map entry goes missing after a large number of insertions
loopless opened this issue · 3 comments
I have a map that is <int, void *> and a previously inserted entry goes 'missing' after a large number of insertions of other key/value pairs. The key value is 1597736, and it goes missing from the map after inserting a key of value 9861762. The size of the map is 1251645 when the problem occurs.
This happens on Linux , and not Windows oddly. I have a reproducer.
I am using GCC 6.3.1 on Centos 7 and compiling with
c++ test.cpp -o test
there is a small bug in the code that reads keys.txt , it should check of.fail() before adding the element to the map. It does not affect the validity of the reproducer.
Than you very much for the report. That's a quite critical bug. The commit I made should fix the issue.
The problem came from the too high number of collisions causing the bucket_entry::m_dist_from_ideal_bucket variable to overflow (distance higher than 32767) . I fixed the issue but I really recommend to use a better hash function than std::hash<T> for integers with GCC and Clang as they use a simple identity function which can cause some problems with hash tables using open-addressing. MSVC uses a more robust hash for integer which explain why it was working on Windows.
Thanks for fixing it. As you say, it is fairly critical and it's going to be sort of random