MrArM's blog

How to learn HashTable DataStructure !?
By MrArM, 11 years ago, In English

Hi , HappyNewYear ;)

I saw some problem that need hashing to solve , Such as 271D - Good Substrings and 127D - Password .

So I decided to learn this data structure !

I tried to find it by google but I can't find any intelligible tutorial .

Can anyone help me with any helpful tutorial ?!

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dataStructures maybe good :-?

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

    Thanks , But it's really short and especially about implementation there is nothing :-??

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

Do you know hashing on strings? It's not same as hashtable and essential to solve problems you mentioned.

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

I don't think you need a hash-table itself; it's already implemented in most common programming languages anyways. You just want to be able to use simple hashing.

The whole idea behind hashing strings is that you convert a string (slow comparison function) into an integer, and instead of comparing the whole strings for equality, you just compare their hashes. Classic polynomial hash is the most common:

where $p$ and M are suitably chosen numbers; for me, M = 109 + 9 and p = 999983 (largest prime below 106) work well.

All you need to be able to do is compute a hash (using classic modular arithmetic) and compare hashes instead of whole strings.

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

As a comment, both mentioned problems can be solved without hashing strings under given constraints. And you might prefer solutions not involving hashing in order to avoid arguing later whether it is a good practice to add anti-hash tests to test suite.

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

I found this paper useful to learn hashing http://www.mii.lt/olympiads_in_informatics/pdf/INFOL119.pdf

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

here you can find a good tutorial e-maxx site

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

    Google Translate? Seriously? I mean, I often find the GT'd text harder to understand than the original one... even in languages which I don't know :D

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

here is my code for this question which i submitted while ago 4917199 . u just need a base and a prime. In this problem single hashing worked well but in several cases double hashing may be required. Second question is totally different from this one. In the hashing I used for first problem, it pre-computes in O(n^2) and answer each substring in O(1) but in second One n = 1e6. There is a way to hash an string by O(n) and answer each substring by O(1) by using partial sum. For each position i in string, u have to find biggest value for x such as hash(substr(i,x)) == hash(substr(0,x)). you can binary search on x. This will work in O(nlgn)

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

    I think you don't need to use a module because when you calculate the hash value the integer multiplication is in module 2^64 if you are using long long. this is my solution 5617947

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

      I recall a note from one tutorial:

      whoever uses 2^32 will get beaten up by Chuck Norris

      In other words, some moduli can be risky. Supposedly, as I haven't really encountered my hashes failing.

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

        It happened to me once in a moduli in long long but when I used two different function it passed!!

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

        Well you are right look the same submission but only using 37 instead 31. 5617936 5617947 . Is a real example you said.

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

        Good article about it on codeforces (in russian)

        → Reply