3

Eu precisava de alguma forma gerar um "hash" a partir de uma string mas que o mesmo hash seja obtido independente da ordem das duas strings

1234+4321  = asdfghjkl
4321+1234  = asdfghjkl

isso é possível com PHP?

9
  • 2
    A entrada seria duas strings e a saída um hash? Você poderia sempre usar a menor depois a maior (comparando-as lexicograficamente) ou alternativamente fazer o hash de cada uma delas e depois combiná-los com um xor ou +.
    – mgibsonbr
    Commented 1/07/2015 às 23:17
  • 1
    @mgibsonbr Sim.. duas strings que na teoria seriam apenas números mas poderiam ser simplesmente palavras também.. poderia explanar sua idéia numa resposta? Commented 1/07/2015 às 23:22
  • O hash não é para esse propósito e sim devolver o mesmo valor para uma entrada conhecida, por isso é utilizado para verificação de integridade de arquivos e etc... Commented 1/07/2015 às 23:31
  • 1
    Posso sim. Só me esclarece uma coisa: você está pensando num hash tipo tabela hash ou num hash criptográfico?
    – mgibsonbr
    Commented 1/07/2015 às 23:32
  • 1
    @user3163662 Ok, vou escrever uma resposta então. É que a princípio pensei que você queria algo como isto ou isto.
    – mgibsonbr
    Commented 1/07/2015 às 23:44

2 Respostas 2

3

Vejo duas opções: 1) você compara ambas as strings, e concatena-as de modo que a "menor" (em ordem lexicográfica) esteja sempre primeiro, e então faz o hash das strings concatenadas; 2) você faz o hash de cada string independentemente, e depois combina os resultados usando alguma operação comutativa (como um xor). Exemplos:

function hashPar1($a, $b) {
    if ( strcmp($a, $b) > 0 ) {
        $temp = $a;
        $a = $b;
        $b = $temp;
    }
    return hash("sha256", $a . $b);
}

function hashPar2($a, $b) {
    $ha = hash("sha256", $a);
    $hb = hash("sha256", $b);
    $ret = "";
    for( $i=0; $i<strlen($ha); $i++) {
        ret .= chr(ord($ha{$i}) ^ ord($hb{$i}))
    }
    return ret;
}

Nota: eu sugiro a segunda opção, pois o primeiro método tem a desvantagem de um número maior de colisões. Por exemplo, o par foo+bar produziria o mesmo hash do par fo+obar ou f+oobar ou fooba+r (mas não foob+ar). Esse problema não ocorre no segundo método, já que strings distintas teriam hashes totalmente distintos [com alta probabilidade].

Atualização: li há pouco um comentário dizendo que no PHP você pode fazer o xor de duas strings diretamente, não precisa quebrá-la em caracteres e converter para e de números. Se isso estiver correto (não testei) então o código da opção 2 pode ser simplificado para:

$resultado = hash("sha256", $string1) ^ hash("sha256", $string2);
0

Ordene a String e utilize a função de hash. Veja o código abaixo

>>> a = '1234+4321'
>>> b = '4321+1234'
>>> a
'1234+4321'
>>> b
'4321+1234'
>>> sorted_a = ''.join(sorted(a))
>>> sorted_a
'+11223344'
>>> sorted_b = ''.join(sorted(b))
>>> sorted_b
'+11223344'
>>> hash(sorted_a)
6594644838925616234
>>> hash(sorted_b)
6594644838925616234

Note que o código acima funciona para letras e números. O procedimento utuilizado foi o seguinte:

  1. Criou-se variáveis 'a' e 'b'.
  2. Variáveis 'a' e 'b' foram ordenada, para que as mesmas fiquem iguais, caso possuam as mesmas letras.
  3. Calculou-se o hash da mesmas. Caso possuam as mesmas letras, terão valored de hash iguais.

Nota: a pergunta original não especifica a lingaugem, então fiz em python.

2
  • Pelo que eu entendi o que o AP quer é que duas strings específicas mapeiem pro mesmo valor, independentemente da ordem, e não que quaisquer strings com os mesmos caracteres o façam. Seu código produziria o mesmo hash para as strings 1234, 1243, 1324, 1342, 1423, 1432, 2134, ...
    – mgibsonbr
    Commented 1/07/2015 às 23:56
  • 1
    Eu entendi o contrário. Para quaisquer Strings com as mesmas letras, elas devem produzir um mesmo valor de hash. Commented 2/07/2015 às 0:02

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .