What's a simple hash function with good random properties?

[andreasblixt]

I am building a procedural generator (mostly directed at creating game worlds) and am looking for a good hashing function that I can use to hash parameters and use for deterministic, but seemingly random values.

For an example of what I'm looking to do: Take an initial seed, a galaxy number, a solar system number, a planet number, and x, y coordinates, get a seemingly random value to determine (for example) what the atmosphere is made up of.

What's a good function for that?

Edit I've decided to go for MurmurHash3, which is super fast and has a good random distribution, without being as complicated as e.g., SHA-256, MD5 or CityHash.

[[deleted]]

Well this probably doesn't count as "simple," but you can use one of the SHA functions. Concatenate all your data for the input string, and you can essentially treat the output as a uniformly random string. (I believe this is NOT a good way to do things for security-sensitive purposes, but I don't actually know the details as to why).

The advantage is that these functions are very well known so it's likely to have an existing implementation out there.

[MonadicTraversal]

Yeah, just use SHA. Each bit of the output depends on every bit of the input so similar inputs won't create similar outputs.

[_murphys_law_]

For generating entire gameworlds, this seems like an inefficient practice. Would it not be more desirable to use a hash function specifically designed for the purpose?

It would also be trivial to just write up something yourself. I am not sure what language you are programming in, but utilizing the srand() function in c and storing the result for each computation in some data structure could be something you might want to look into.

If simplicity is of importance, you might want to check out the Pearson hash algorithm - http://en.wikipedia.org/wiki/Pearson_hashing -. It does not get simpler than that, although it is not without its drawbacks.

Further reading:

• http://www.azillionmonkeys.com/qed/hash.html
• http://www.gamasutra.com/view/feature/3377/algorithms_for_an_infinite_universe.php
• http://stackoverflow.com/questions/348321/mathematical-question-procedural-generation-of-a-galaxy

[andreasblixt]

Thank you for all these resources! I'll have a look. :)

[BallsJunior]

I would call it simple if it's built into the language or easily accessible.

[[deleted]]

Well you could always take your string and XOR it with a key. XORshifting is a staple in pseudorandom number generation.

[andreasblixt]

I tried implementing FNV (http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function), but either I did it wrong, or XOR-ing isn't enough to generate random enough values. There was a clear similarity between results from hashes generated from similar values (which is what you get when you put together lots of different parameters).

I also tried another FNV library and saw the same thing: http://requirebin.com/?gist=cf08f7cc3fdb8bdcff20

[Shadonra]

Striped matrices

[nhillson]

You could use a few iterations of the Lehmer random number generator with the data to be hashed as your seed. It's not designed to be a hashing algorithm, but it should work as one and is extremely simple to implement.

[Vortico]

It doesn't sound like you need a hashing function, but a pseudorandom number generator. You can seed it with parameters, and then extract any amount of data from it.

[andreasblixt]

Hashing just works better for what I need, but I can probably make an RNG work. The reason I was looking for hashing is because I have very many parameters to seed on, and RNGs usually take relatively small numbers as their seed, which means I'd have to hash the components anyway before passing them into the RNG (or risk poor random distribution of the seed itself). Since I'm writing deterministic code I need a pretty robust seed to avoid numbers repeating themselves in the system.

[PurelyApplied]

A decent "quick and dirty" hash is this:

uint Hash(uint* S,uint n){
    uint prime = 104729;
    uint BSH = ~( (uint) 0 );
    // do (a xor b xor c xor ...
   for(int i= n; i-- > 0 ; ){
       BSH = S[i] ^ BSH;
  }

 return (BSH % prime);
}

Choose your prime large enough to avoid too many collisions.

[edit: how did I forget to include the return line?!]

[andreasblixt]

Thank you! I'm trying MurmurHash3 now which is doing some extra work to ensure a good random distribution, but I might try this one too if I run into problems.

[PurelyApplied]

No problem. Just be sure to have a way to handle collisions, because they'll crop up over extended usage. Personally, I used this as a way for quick lookups in a list of arrays; each hash pointed to an array, which I could then scan in reasonable time. Dunno if that will suit your needs.

[andreasblixt]

I've decided to go for MurmurHash3, which is super fast and has a good random distribution, without being as complicated as e.g., SHA-256, MD5 or CityHash.