Reducing the range of a hash function maintaining even distribution
<p>I'm writing a cron-like job-dispatcher that runs jobs every minute (and other jobs every 5 minutes, etc.). However, instead of immediately dispatching all the jobs that run on a particular period at the top-of-the-minute, I want to spawn them evenly over their periods.</p>

<p>For example, if I have N jobs that run every P minutes, rather than spawn them all at P:00, I want to spawn the jobs evenly over the P*60 seconds, i.e., <code>ceil(N/P*60)</code> jobs per second.  Hence, the spawn time for each job would be "skewed" somewhat later.</p>

<p>However, for each job J, I want J to be spawned at the <em>same</em> skew every time it's dispatched so that the time between spawns for J is constant (and matches its period).</p>

<p>Each job has various information associated with it, including several strings that vary for each job. My original thought was to calculate a hash-code, H, for one or more of the strings and mod it by P*60 to calculate a constant skew, S, for each job. As long as the strings associated with the job remain the same, the calculated skew would remain constant.</p>

<p>However, I would assume that <code>S=H%(P*60)</code> suffers from  to <a href="http://www.azillionmonkeys.com/qed/random.html" rel="nofollow">problems similar to using <code>rand()</code></a> (uneven distribution that's biased towards lower numbers). However, I don't think the solutions presented there (to call <code>rand()</code> multiple times) would apply to my case where I'm using a hash-code because the hash function for a given job would always return the same hash.</p>

<p>So how can I get what I want?  (I'm writing in C.)</p>

<hr>

<h1>Examples:</h1>

<ol>
<li><p>Suppose I have N every-minute jobs (a cron schedule of <code>* * * * *</code>). For N &lt; 60 (let's say 2), then job-1 might be skewed to start at :23 (23 seconds past the minute) and job-2 might be skewed to start at :37. With so few jobs, it may not seem evenly distributed. However, as N approached 60, the "gaps" would fill in (assuming a perfect skew function) so that one job would be spawned every second. If N passed 60, some jobs spawned at some seconds would "double up." Similarly, as N approached 120, the "gaps" would again fill in so that two jobs would be spawned every second. And so on.</p></li>
<li><p>Supppose I have N every-five-minute jobs (a cron schedule of <code>*/5 * * * *</code>). In "normal" cron, that means "every five minutes on the zeroth second on the fives." I <em>instead</em> want that to mean "every five minutes, but not necessarily (and most likely not) on the zeroth second of <em>some</em> minute, but the only guarantee is that the interval between spawns will be five minutes." So for example, a particular job might be spawned at 00:07:24, 00:12:24, 00:17:24, etc. As N approached 300, one job would be spawned per second.</p></li>
</ol>