CODEWITHSUNDEEP
hash
rohitt
rohitt

Reputation: 1225

Hash function from string using MAD

The MAD (multiply-add-divide) method computes hash as follows for some value x,
h(x) = ((ax + b) mod p) mod N
where p is a prime number larger than N, a and b are some random integers in the range [1, p-1] and N is the size of the hash table.

How do I compute the hash of a string value? I'm not sure if I should compute the hash of the string (such as based on place value) and then use the MAD method or is there another way?

What I've tried? I want to implement a function int hash(str) which will return the hash value. I have written int hash(int x, int N), but here I'm sending a pre-calculated x based on ASCII value of characters in string.

Upvotes: 0

Views: 307

Answers (1)

Artjom B.
Artjom B.

Reputation: 61952

I can think of two sensible ways to do this.

  1. Treat each character as its own number (many programming languages have the ord function) and chain the evaluations of h is such a way that for example you use the value for a or b as the result of the previous result of h.

  2. Treat the whole string as a single number. You can convert a string to a bytes array which can be converted through some kind of big integer library into a single number. This can be used as input for h which must then be implemented with the same big integer library as well.

There is no telling which of those two methods are faster. I would guess it is the first one, but both of them don't guarantee any properties similar to a cryptographic hash function. There are many more ways to do this.

Upvotes: 1

Related Questions