I'm making a game, and every now and then a number of objects in the game need to know whether or not the player has moved. Because of the large numbers of objects involved, instead of alerting every object every frame, I've sorted them into bins with corresponding events. Bin 1 is alerted the first frame the player moves, then bin 2 the second frame, etc, up to some finite number.
However, I need some consistent way to assign each object a bin. Just using the object ids isn't working, as the way that the objects are generated gives patterns in their ids that may result in some bins being filled more or less than others, which decreases the gains in efficiency. If all the ids are even and so is the bin size, then only the even bins will be filled.
In short, the problem is this:
Given a sequence of non-random, unknown, unique integers S that may or may not have a pattern, how can I choose a hashing algorithm H and number of bins p so that H(S[i]) % p forms a roughly uniform distribution?
Simply choosing a prime number as the number of bins seems to be a good start, but I'm wondering if there's a hashing algorithm I can use to "scramble" the patterns of the input sequence and improve uniformity. Ideally, one already included in .Net.
Edit:
I've found some promising results in this answer. I'm still curious about this problem though, both from a mathematical perspective and whether there are tools to do this included in .NET.
Using one of those algorithms you linked to would likely be a fine solution. As pointed out the splitmix64
algorithm is a good choice for 64bit integers, or for 32bit int
s the hash-prospector link looks good.
You don't say what your "object ids" are, but if they're sequential integers (e.g. array indices) or Object.GetHashCode
values that would be appropriate input for those algorithms.
There are some very technical players (e.g. SciCraft group in Minecraft) that might be able to exploit such a system, but even if you used a cryptographic hash you'd likely need more entropy than just those object ids. For example, you could pull some state from the OSs CSPRNG when your game is starting, and hash that with the object id. A non-cryptographic hash like the MurmurHash would likely be fine when used like this.
Using the low order bits would likely be OK for indexing your bins, but I'd suggest using a power of 2 (e.g. 8 or 16) as a "bitwise and" is much cheaper than a modulus/division.