javascriptalgorithmstring-hashing

Javascript hashing algorithm

I'm trying to learn how to do some basic hashing in Javascript and I've come across the following algorithm:

var hash = 0;
for (i = 0; i < this.length; i++) {
    char = str.charCodeAt(i);
    hash = ((hash<<5)-hash)+char;
    hash = hash & hash;
}

I don't really understand how it works and I was hoping you could help me out. In particular I don't understand (hash<<5)-hash and hash = hash & hash. Thank you for your replies.

Note: For anyone looking for the source, it's an implementation of Java’s String.hashCode(): http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method

Solution

  • The step

      hash = ((hash << 5) - hash) + char;

    is effectively:

      hash = ((hash * 32) - hash) + char;

    Then,

      hash = hash & hash;

    will only change the value if the number has overflowed the integer range (32 bits, or maybe 31). (I wouldn't do it that way but it's a matter of style.)

    In that code, the variables "i" and "char" should be declared:

    var hash = 0, i, char;