Hashing a string between two integers with a good distribution (Uniform Hash)

Question

I'm trying to hash some strings between 0 and a very low n in order to give one color per user.

Here is my (working) code:

 function nameToColor(name) {
            var colors = ['red', 'blue', 'green', 'purple', 'orange', 'darkred', 'darkblue', 'darkgreen', 'cadetblue', 'darkpurple'];
            var hash = hashStr(name);
            var index = hash % colors.length;
            return colors[index];
        }

        //djb2 hash
        function hashStr(str) {
            var hash = 5381;
            for (var i = 0; i < str.length; i++) {
                var charCode = str.charCodeAt(i);
                hash = ((hash << 5) + hash) + charCode; /* hash * 33 + c */
            }
            return hash;    
        }

Unfortunately the low numbers are massively over-represented.

Question:

How can I write a deterministic javascript function that takes any string as argument and returns with a good (as uniform as possible) distribution a number between 0 and n?

Hashing is well understood and way out of scope of this question. Maybe just use one of the gazillion hash functions that already exist. — Hogan, Jun 13 '13 at 09:14
Also Benford's law deals with leading digits (the leftmost) you aren't using the leading digit, you are using the modulus of the hash result. — Hogan, Jun 13 '13 at 09:19
@Hogan I'm already using a standard hashing function, it just doesn't fit what I need. That's why I'm asking this question. — L. Sanna, Jun 13 '13 at 09:21
There are 4 or 5 listed on that page. I'm guessing you are just seeing results that don't look random enough. The problem with random is it never looks random. Random just is. — Hogan, Jun 13 '13 at 09:23
@Hogan It isn't a duplicate. I already have a hash function, it's in the code I posted. — L. Sanna, Jun 13 '13 at 09:23
A "deterministic javascript function that takes any string as argument and returns with a good distribution a number between 0 and n" is a hashing function. This is the definition of a hashing function. You are asking how to write a good hashing function, that question is the same. — Hogan, Jun 13 '13 at 09:24
Here is another link for you http://erlycoder.com/49/javascript-hash-functions-to-convert-string-into-integer-hash- — Hogan, Jun 13 '13 at 09:35
and another http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/ — NimChimpsky, Jun 13 '13 at 09:35
@NimChimpsky I already tried the JAVA hash, I had the same problem. — L. Sanna, Jun 13 '13 at 09:41
This question was not a duplicate. He clearly asks for a *uniform* hash function. The other question does not specify this criterion. — MRocklin, Oct 17 '13 at 17:40

L. Sanna · Accepted Answer · 2019-11-13T19:05:45.430

Hogan gave in comment a link to several hash implementation in javascript. It turns out that the most simple is the most appropriate:

function nameToColor(name) {
                var colors = ['red', 'blue', 'green', 'purple', 'orange', 'darkred', 'darkblue', 'darkgreen', 'cadetblue', 'darkpurple'];
                var hash = hashStr(name);
                var index = hash % colors.length;
                return colors[index];
        }

        //very simple hash
        function hashStr(str) {
            var hash = 0;
            for (var i = 0; i < str.length; i++) {
                var charCode = str.charCodeAt(i);
                hash += charCode;
            }
            return hash;
        }

I think it works well because it only uses the addition (no shift or multiplications) which leave the modulo unchanged, so the initial quality of distribution is conserved.

I also found this on wikipedia, but did not have to use it:

In many applications, the range of hash values may be different for each run of the program, or may change along the same run (for instance, when a hash table needs to be expanded). In those situations, one needs a hash function which takes two parameters—the input data z, and the number n of allowed hash values.

A common solution is to compute a fixed hash function with a very large range (say, 0 to 232 − 1), divide the result by n, and use the division's remainder. If n is itself a power of 2, this can be done by bit masking and bit shifting. When this approach is used, the hash function must be chosen so that the result has fairly uniform distribution between 0 and n − 1, for any value of n that may occur in the application. Depending on the function, the remainder may be uniform only for certain values of n, e.g. odd or prime numbers.

We can allow the table size n to not be a power of 2 and still not have to perform any remainder or division operation, as these computations are sometimes costly. For example, let n be significantly less than 2b. Consider a pseudo random number generator (PRNG) function P(key) that is uniform on the interval [0, 2b − 1]. A hash function uniform on the interval [0, n-1] is n P(key)/2b. We can replace the division by a (possibly faster) right bit shift: nP(key)>> b.

all hash functions have collisions, but the above one has ones that are quite bad for natural text text: "ab" and "ba" will have exactly the same hashcode because the used formula is only a sum that does not care about order. Also: "aaaaaaaaab" and "aaaaaaaaac" will end up having a nearly identical color. — Ilmarinen123, May 02 '20 at 16:03

score 1 · Answer 2 · answered Jun 13 '13 at 12:52

1

The following hash function, by Brian White, is very generic, use any kind of input (including strings), comes with simple examples, and is written for Javascript node.js.

https://npmjs.org/package/xxhash

Hope this helps

answered Jun 13 '13 at 12:52

Cyan

13,248
8
43
78

score 0 · Answer 3 · answered Oct 04 '21 at 22:36

Here is a variation of the code above:

function hashValue(theString,size){
  var sum = 0;
  for(i=0;i<theString.length;i++){
    sum += theString[i].charCodeAt(0) * 3;
  }
  return sum % size;
}

Simply pass a string and the size you want it to have, for example, 36 if you want it to return numbers 0 through 36. The * 3 can add variation but can be whatever number you want. I repurposed this idea from here (Hash function that can return a integer range based on string) by M_callens

Adding a `* 3` here is mathematically unsound - for example, if `size` is any multiple of 3, everything is going to hash into just 1/3rd of the buckets! — Jimbly, Dec 02 '21 at 23:41

Hashing a string between two integers with a good distribution (Uniform Hash)

3 Answers3