exh3's blog

Interesting situation with hash() C++
By exh3, history, 8 years ago, In English

Hi everybody!

I'm trying to solve this problem 4C - Registration System. My last solution is 24184665. I've found, that if I run code on my PC, I'll take another answer than if I run same code on Codeforce's server. Compiler — MS VS C++ 2010. For example:

Test data: test data

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the standard doesn't specify the implementation of hash functions, the output is environment-dependent. Actually std::hash can even produce different hash values for the same input in different executions.(Since C++14)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    But during one execution it should return the same hash codes for the same values. It's the main principle of hash alghorithms. The question is in generation different hash-codes for the same objects during one execution.

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

      The issue isn't "different hash-codes for the same objects during one execution" which is a library bug. It's the same hash value for different objects, in other words, hash collision. The string "idcvexvhgtyyvplfr" and "idcvexvhgtyyvplfrl" generates the same hash value for the compiler you selected.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        MS VS C++ 2010 hash function only looks at a part of the string according to this StackOverflow post. A bit odd, but not a bug.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          Yes. Maybe my previous comment isn't clear. I meant generating different hash for an object in an execution is a bug. Hash collision, although only looks part of a string is weird, isn't a bug.

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

            Oh, I understood. Thank you, guys. The solution is very simple — write your own hash function.

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

              Writing your own hash function is not going to prevent you from getting collisions. Is there a reason why you're not using a hash table?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +10 Vote: I do not like it

                There isn't. Simply, hash function was the first solution, which I found as optimal. But practice has shown that it isn't the best one. Thank you for a helpfull tips.

                → Reply