Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #370

Re: hash (step) function?

Show all headers | View raw

On Thu, 26 May 2011 11:30:57 -0700 (PDT), Matthew Martin
<honestmath@gmail.com> wrote:

>Hello All,
>
>I have users with assigned ID's which need to be placed into 2 pools
>(buckets).  X% needs to be placed into pool 1 and (100-X)% in pool 2.
>However, this needs to be repeatable and deterministic.
>
>Can anyone enlighten me as to a hash function where I am able to
>choose X and have numbers distributed as such?  I know that I can use
>the modulo function to break ID's into 100 pools and choose the
>dividing line closest to X, but I was wondering if there were a more
>efficient way.
>
>ID's placed in pool 2 are further divided among N buckets using the
>modulo function.
>
>Along the same lines, what might be a technique to "randomize" the
>ID's so that individual users are not always placed in the same
>bucket, but that will keep the buckets either even (in the case of
>modulo) or divided by X (in the first example)?
>
>Thanks!

The problem statement is incomplete.  Is the list of user ID's
predetermined and fixed, or is it variable?  In what respect is this
process repeatable and deterministic?

For example, if your list of of user ID's is fixed give each one a
sequence number, i.e., the first user in your list of users has
sequence number 1, the second one sequence number 2, and so on.  Then
dividing them up into buckets is trivial.

If the list of user ID's is variable there is a simple scheme for
reassigning sequence numbers with changes.  To wit, if a user is
added, it gets the next available sequence number; if one is deleted,
the user with the last sequence number is reassigned the sequence
number of the deleted user.

If you can't attach a sequence number to the user ID or the user
record then you need a different method.  Are there constraints on
what goes in which bucket?  Does the number of entries in a bucket
have to be exact?

Since you don't seem to care which ID's are in which buckets (this is
implied by hashing) why not just put ID's in the best bucket as you
scan the list of ID's; i.e., for each one pick the bucket that will
best fit the desired bucket ratio?  If this is not acceptable, why
not?

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

hash (step) function? Matthew Martin <honestmath@gmail.com> - 2011-05-26 11:30 -0700
  Re: hash (step) function? rossum <rossum48@coldmail.com> - 2011-05-26 23:49 +0100
    Re: hash (step) function? Matthew Martin <honestmath@gmail.com> - 2011-05-27 13:00 -0700
      Re: hash (step) function? rossum <rossum48@coldmail.com> - 2011-05-27 23:59 +0100
  Re: hash (step) function? cri@tiac.net (Richard Harter) - 2011-05-28 04:58 +0000

csiph-web