Hashing algorithms/implementations for Monte Carlo simulation

Question

To summarise this question in advance, I'm looking for a good hash function that is suitable for generating pseudo-random numbers in Monte Carlo simulations. This means it should be reasonably fast (so something like md5 is ruled out) but have statistics that are good enough for numerical applications.

The reason is that sometimes, when writing simulation code, I've felt the need to generate a function that maps some set of objects to floats between 0 and 1, in a pseudo-random way. Such a function might always map the Numpy array [1.0, 2.0, 3.0] to 0.11214, but on a different run of the simulation a different function might be generated, which always maps [1.0, 2.0, 3.0] to 0.92546. The input set might not consist of arrays, but if it does then it's important that order is not ignored, i.e. [1.0, 2.0, 3.0] and [1.0, 3.0, 2.0] should return different results.

It seems there are a few different technical terms for generating such a random function: depending on details of the implementation it's either called universal hashing or psuedorandom function families. Of course one way to implement this is to use a good hashing function. Different pseudorandom functions can be generated using "salting", i.e. prepending a fixed string to every object before running the hashing algorithm. Changing this prefix gives a different pseudorandom function.

Secure hashing algorithms such as md5 will have excellent statistics, but are too slow to be practical in a Monte Carlo simulation. Of course there exist many "fast hashing" algorithms (i.e. non-secure hashing algorithms) that might be suitable to use instead. However, the issue is that I haven't been able to find a good analysis of any such algorithms in terms of their suitability for numerical computation.

This is important, because most fast hashing algorithms are designed for use in file systems. Typically, papers describing hash functions evaluate them in terms of how well they will perform in such an application. However, and the requirements for this are rather different from the requirements for a numerical simulation. I'm not an expert, but the essential difference is that for a file system we really care a lot about avoiding collisions, whereas for a numerical algorithm we care most about uniformity of the distribution of outputs and statistical independence of the functions' outputs, even if the function is given inputs that are closely related.

These goals are related to one another (and secure hashing algorithms will score very well on all three) but they are not the same. As a trivial example to illustrate this, using Python's built-in hashing algorithm modulo 1000, "aaa" is mapped to 340, "aab" to 343, "aac" to 342, "aad" to 337, "aae" to 336 and "aaf" to 339. There are no collisions in this data, but the results are clearly neither uniformly distributed nor independent.

So I'm looking for any advice on which hashing algorithm(s) to use in Monte Carlo simulations, to get a good trade-off between speed and statistics that are suitable for numerics. In an ideal world there would also be an existing C implementation with Python bindings; it would also be ideal if objects like Numpy arrays could be hashed directly, rather than first having to convert them to strings. Ideally I would like an off the shelf solution that I can trust, in the same way that I trust Numpy's random number generator. However, I don't mind implementing it myself if that's what necessary - the important thing is to find an algorithm that has been formally evaluated in terms of it suitability for numerical applications, rather than for use in file systems.

Answer 1

The first thing that comes to my mind is the following:

import random

def randomy(obj):
    """
    Map objects to uniformly distributed random numbers in [0, 1].
    The input must be hash-able. You will get the same output for
    the same input during all calls in the same program run, but
    outputs may vary between different program runs.
    """
    try:
        return randomy._store[obj]
    except KeyError:
        value = random.random()
        randomy._store[obj] = value
        return value

randomy._store = {} # Initialize memoization map

x = "Test string"
y = "Another string"

print randomy(x)
print randomy(x)
print randomy(y)

Answer 2

If the data object you are trying to map is large enough, then just taking bit patterns is probably enough. For example, you might simply xor all the bytes of your object, giving you a number between 0 and 255 which you can then map onto the reals between 0 and 1.