Polynomial hash function ( is this video wrong )

[adam2016]

Hi guys

So I'm learning about hashes and following this video - https://www.youtube.com/watch?v=jtMwp0FqEcg

but I have my doubts the professor is correct, shouldn't the sum of 116*31^0 + 104*31^1 + 105*31^2 + 115*31^3 == the hash value by the end of the loop in the algorithm he has wrote?

for 116*31^0 + 104*31^1 + 105*31^2 + 115*31^3 I get the answer 3,425,965 and for the hash in the algorithm I get 3'559'070, the results are very close but do not match

the algorithm is written at 10:12

int hashCode(string str){

  hash = 0;
  int g = 31;

  for(int i = 0; i < str.size(); ++i)
        hash = g * hash + str.at(i);

  return hash;

}

thanks

[jonnin]

I get 3530210
() missing? 116+(31*104) + (31*31*105)+(31*31*31*115) right?

[ne555]

> and for the hash in the algorithm I get 3'559'070
you did it backwards

[adam2016]

sorry my bad I meant for 116+(31*104) + (31*31*105)+(31*31*31*115) I get - 3530210

and for the hash algorithm I get 3'559'070

BUT 3559070 != 3530210

so the algorithm must be wrong right or the point he is trying to convey must be wrong at the very least right?

[jonnin]

I do not do videos; I can read 3+ pages of text in the time some goober can recite 1/2 a page. I was just giving you the value I got for the numbers.

his point can be correct with bad code or bad algorithm; in fact, this is fairly common in many textbooks :)

the algorithm is either wrong or its an approximation of something, I do not know, I didn't watch it. But if you want that algorithm, why not code it yourself? for i = 0...n hash+= data*pow(31, i) (though I would hard code up a table of powers of 31 for speed if you are doing something for real).

by the way, a hash algorithm that can be expressed in a single line of code is almost always too simple and going to have flaws (it may still be good enough for a microscopic hash table etc in spite of this). Be wary of such things if doing a bigger project.

[doug4]

@OP,

I think you skipped right over @ne555's post.

(116 * 31^3) + (104 * 31^2) + (105 * 31) + 115 = 3,559,070

116 + (104 * 31) + (105 * 31^2) + (115 * 31^3) = 3,530,210

I have no idea where 3,425,965 came from.

[adam2016]

3,425,965 was a mistake it is the product of (115 * 31^3) which I mistakenly used instead of 3,530,210

and yes I think ne555 is correct the problem was that it should have been done the other way around so let's say we have the string this

t h i s
116 104 105 115

g = 31

the video implies

116 * g^0
104 * g^1
105 * g^2
115 * g^3

in matter of fact it is

116 * g^3
104 * g^2
105 * g^1
115 * g^0

so the professor did indeed make this video a lot more confusion with the glaring mistakes

[jonnin]

if material were presented directly instead of in a confusing way, college would only be 1.5 years.

[adam2016]

very very true I can attest to that