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

Groups > comp.programming > #363 > unrolled thread

hash (step) function?

Back to article view | Back to comp.programming

Contents

  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

#363 — hash (step) function?

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!

Matt

[toc] | [next] | [standalone]

#364

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.
Unlikely.  Have you tried a test run with real amounts of data to see
if there is a speed problem?  If not then stick with the obvious
solution unless there is a real problem.

>
>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)?
Generate a random integer less than N (the number of buckets).  Add
this number to the ID before modding.  The distribution will be
shifted into different buckets, though users in adjacent buckets
before will usually be in adjacent buckets after.

For a more thorough mixing you need to generate a permutation, but
that will be more time consuming than add + mod.  Knuth algorithms
3.4.2R and 3.4.2P may be useful if you want to do something more
complex.

rossum

>
>Thanks!
>
>Matt

[toc] | [prev] | [next] | [standalone]

#368

Cheers for the advice.  I was hoping for a level of sophistication
that I was not currently aware of, but it seems that will not occur.
I will have to look up the Knuth algorithms.

Thank you again.

Matt

On May 26, 3:49 pm, rossum <rossu...@coldmail.com> wrote:

> Unlikely.  Have you tried a test run with real amounts of data to see
> if there is a speed problem?  If not then stick with the obvious
> solution unless there is a real problem.
>
>
>
> >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)?
>
> Generate a random integer less than N (the number of buckets).  Add
> this number to the ID before modding.  The distribution will be
> shifted into different buckets, though users in adjacent buckets
> before will usually be in adjacent buckets after.
>
> For a more thorough mixing you need to generate a permutation, but
> that will be more time consuming than add + mod.  Knuth algorithms
> 3.4.2R and 3.4.2P may be useful if you want to do something more
> complex.
>
> rossum
>
>
>
>
>
>
>
>
>
> >Thanks!
>
> >Matt

[toc] | [prev] | [next] | [standalone]

#369

On Fri, 27 May 2011 13:00:42 -0700 (PDT), Matthew Martin
<honestmath@gmail.com> wrote:

>I was hoping for a level of sophistication
>that I was not currently aware of, but it seems that will not occur.
>I will have to look up the Knuth algorithms.
How sophisticated do you want to go?  How much time do you have to
spend processing each ID?  How many sledgehammers do you want to use
to crack a nut?

Salted SHA-256 will give you a hash, at a cost in time.

AES-256-CTR will give you a permutation, at a cost in time.

Given your problem description, either would be overkill.  Better to
keep it simple.

rossum

[toc] | [prev] | [next] | [standalone]

#370

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?

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web