m.h's blog

!! How to solve Hashing problems
By m.h, 10 years ago, In English

Hi :)

In recent Codeforces contests , we see many problem with "Hashing" tag ! so I decide to learn Hashing algorithms and formula !

What must I do ?

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

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hashing = String in Base X Mod Y
X and Y are integers you have to choose i choose X = 29 or X = 43 and i choose Y as 1e9 + 7 or 1e15 + 7
or whatever what is bad about it is that two strings can have the same mod which is unlikely
you can easily get hash of strings in O(1) with preprocess of O(n) which isnt hard to think of
Good luck

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

    what is X and Y?

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

      some variables you choose?

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

      Y should be a prime (random or at least unrelated to the test data). Y should be greater than n^2, where n is the number of strings you are planning to hash.

      X should be a integer between your alphabet size and Y-1. Code is easier to write if X*Y conveniently fits into your integer data type.

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

Read this code. it can be helpful.

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

http://threads-iiith.quora.com/String-Hashing-for-competitive-programming Have a look at this.

→ Reply