Tariqul's blog

Calculating Hash value of a string
By Tariqul, 12 years ago, In English

In some contest, there is some string related problem. Many authors use hashing algorithm to make the solution faster. When string length is so small that hash value does not overflow, then I have no question. But when string length is too big to hash value is over flow, then how solution gives guarantee that there is no hash value of two different string is unique.

Can anyone clarify it please?

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

There is no guarantee that hash values are unique, but the probability of a collision is very low.

→ Reply
»
12 years ago, # |
  Vote: I like it +32 Vote: I do not like it

You rather beat tourist than hashing gives a collision.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

There is no guarantee that the hash of 2 different strings are unique. When using hash value to compare strings, there are always some (small) probability that your code will give incorrect answer for an input. It is up to the programmer to decide whether it is safe enough or not to use hash.

Edit: sorry for same answers as above. When I started typing, there was no comment :(

→ Reply