Como projetar uniformemente um hash para um número fixo de buckets

Olá colegas estatísticos,

Eu tenho uma fonte gerando hashes (por exemplo, computando uma string com um carimbo de data e hora e outras informações e hash com md5) e quero projetá-la em um número fixo de buckets (digamos 100).

hash de amostra: 0fb916f0b174c66fd35ef078d861a367

O que eu pensei inicialmente era usar apenas o primeiro caractere do hash para escolher um balde, mas isso leva a uma projeção descontroladamente uniforme (ou seja, algumas letras aparecem muito raramente e outras com muita freqüência)

Então, tentei converter essa string hexa em um número inteiro usando a soma dos valores de char e, em seguida, pegue o módulo para escolher um bucket:

import sys

for line in sys.stdin:
    i = 0
    for c in line:
        i += ord(c)
    print i%100

Parece funcionar na prática, mas não sei se há algum senso comum ou resultados teóricos que possam explicar por que e até que ponto isso é verdade?

[Edit] Após algumas considerações, cheguei à seguinte conclusão: Em teoria, você pode converter o hash em um número inteiro (muito grande) interpretando-o como um número: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (cada letra representa um número hexadecimal). Então você pode modular esse grande número para projetá-lo no espaço do balde. [/Editar]

Obrigado !

NB: colocando em forma a resposta que surgiu da discussão nos comentários para facilitar a leitura para as pessoas interessadas

(versão atualizada)

Suponha que tenhamos uma fonte gerando eventos independentes que queremos distribuir uniformemente em $B$ baldes.

Os principais passos são:

1. hash cada evento $e$ para um inteiro $i$ de tamanho $2^N$
2. projeto para $\mathcal{R} \times [0, 1[$ Como $p = \frac{i}{2^N}$
3. encontrar balde correspondente $b_i$ de modo a $\frac{b_i}{B} \le p \lt \frac{b_{i+1}}{B}$

Para 1. uma solução popular é usar o MurmurHash para gerar um número inteiro de 64 ou 128 bits.

Para 3. uma solução simples é iterar em $j = 1..B$ e verifique se $p$ é em $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

No pseudo-código (python), o procedimento geral pode ser:

def hash_to_bucket(e, B):
    i = murmurhash3.to_long128(str(e))
    p = i / float(2**128)
    for j in range(0, B):
        if j/float(B) <= p and (j+1)/float(B) > p:
            return j+1
    return B

(versão anterior, realmente não ideal)

A primeira observação é que a n- ésima letra do hash deve ser distribuída uniformemente em relação ao alfabeto (que tem aqui 16 letras - obrigado a @leonbloy por apontar isso).

Então, para projetá-lo para um intervalo de [0,100 [, o truque é pegar 2 letras do hash (por exemplo, 1ª e 2ª posições) e gerar um número inteiro com isso:

int_value = int(hash[0])+16*int(hash[1])

Esse valor vive no intervalo [0,16+ (16-1) * 16 [, ​​portanto, apenas precisamos modulá- lo para 100 para gerar um intervalo no intervalo [0, 100 [: Como apontado nos comentários, fazer portanto, impacte a uniformidade da distribuição, pois a primeira letra é mais influente que a segunda.

bucket = int_value % 100

Em teoria, você pode converter o hash inteiro em um número inteiro (muito grande) interpretando-o como um número: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (cada letra representa um número hexadecimal). Então você pode modular esse grande número para projetá-lo no espaço do balde. Pode-se notar, então, que o módulo i pode ser decomposto em uma operação distributiva e aditiva:

Eu tive um problema semelhante e criei uma solução diferente, que pode ser mais rápida e facilmente implementada em qualquer idioma.

Meu primeiro pensamento foi despachar itens de maneira rápida e uniforme em um número fixo de baldes e, para ser escalável, eu deveria imitar a aleatoriedade.

Então, eu codifiquei essa pequena função retornando um número flutuante em [0, 1 [dada uma string (ou qualquer tipo de dado de fato).

Aqui em Python:

import math
def pseudo_random_checksum(s, precision=10000):
    x = sum([ord(c) * math.sin(i + 1) for i,c in enumerate(s)]) * precision
    return x - math.floor(x)

É claro que não é aleatório, na verdade nem sequer é pseudo-aleatório; os mesmos dados sempre retornam a mesma soma de verificação. Mas funciona como aleatório e é bem rápido.

Você pode despachar e recuperar itens facilmente em N buckets, atribuindo simplesmente cada item ao número do bucket math.floor (N * pseudo_random_checksum (item)).