indroneal's blog

By indroneal, history, 8 years ago, In English

what is hashing ? can anyone explain me ? I searched google but cannt understand :(

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

| Write comment?
»
8 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Hashing is a way to replace a string with a number a good way to do this is to use the following algorithm: Let's say our string is s of length n we need to choose two numbers p and mod such that p is a prime number larger than the number of characters that are used in the alphabet of our string for example (if our string contains only small English characters then we can use p=43 since it is prime and it is larger than 26) and mod should be a big prime number. Then we can calculate the hash of the string like this: Hash=((s[1]*(p^1))%mod+(s[2]*(p^2))%mod+..+(s[i]*(p^i))%mod+...+(s[n]*(p^n))%mod)%mod.

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

Hashing an object is like extracting a signature of it. Usually the objects (may be strings, sets, etc..) are very long and the signature is very small and typically computing the signature (hash) of an object is very fast.

In what I have seen in programming, it is typically used for searching.

Consider the following problem: You are given n numbers. For each number you are given, you have to report if you have seen the number previously.

One way would be to store all the numbers we have seen at step i in a data structure and then search if the ith number is present in the stored data structure. But, we can use the signature idea here. Instead of searching for the ith number (n_i) in all previous elements, search only in those numbers that have the same signature as that of n_i. Since, signature of each number is unique, this is theoretically correct.

Typically this is implemented as follows: The signature of an object is interpreted as an address in memory. In this address, store the numbers seen that have this signature. Now, when we see a new number n_i, we compute its signature and check for the presence of this number at the memory address signified by the signature.

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

Refer this tutorial on hashing.