10

Eu tenho uma pequena lista de strings (onde as strings nunca vão se repetir) e gostaria de usar hashcode como id, é uma boa prática?

2
  • 3
    Hashcode pode colidir. Qual seria a vantagem de não usar as strings? Se são únicas, você pode numerá-las na sequência, se o problema for espaço.
    – Largato
    11/02/2016 às 21:53
  • 1
    Boa prática em que sentido?
    – cantoni
    11/02/2016 às 21:54

2 Respostas 2

9

Depende.

Valor único

Não é boa prática se a ideia é criar um ID único.

Hashes são uma simplificação do conteúdo e toda simplificação perde informação porque não tem como você representar o todo com a parte.

Isso significa que é difícil, mas não impossível, que duas Strings ou objetos diferentes gerem o mesmo valor de hash. Quando isso ocorre, dizemos que houve uma colisão. Uma implementação séria deve tratar este tipo de situação, caso contrário estará comprometendo a integridade dos dados ou, como no caso do uso de hashes em segurança, até a privacidade dos seus usuários.

O máximo que você poderia fazer para diminuir o tamanho de uma String sem perder informação é comprimi-la, mas isso não seria muito prático.

Se você precisa criar chaves a partir Strings você tem basicamente duas opções:

  1. Use as próprias Strings. Exemplo:
mapa.put("string1", valor1);
mapa.put("string2", valor2);
  1. Atribua um número às Strings, como se fosse um id numa tabela:
mapeamento.put("String1", 1);
mapeamento.put("string2", 2);
...
mapa.put(1, valor1);
mapa.put(2, valor2);

Classificação

Por outro lado, hashes são bons para classificar conteúdos, o que significa que você pode encontrar rapidamente o que procura, mas não de forma única.

Vou usar o exemplo do HashMap para ilustrar isso.

Imagine que você tem um balde cheio de bolinhas coloridas e numeradas e alguém pede para você pegar uma bola azul de número 1. Você pode gastar um bom tempo procurando e no final pode ser que não a encontre. Isso é o equivalente a buscar itens numa lista, por exemplo.

Por outro lado, se você tiver vários baldes, cada um com bolinhas de uma só cor, basta ir até o balde com a etiqueta de bolinhas azuis e olhar lá dentro. Você ainda pode ter que procurar um pouco pelo número correto, mas vai ser muito mais eficiente.

É mais ou menos assim que funciona com o HashMap. Se você olhar a implementação do HashMap.put() vai ver que ele usa o hash para acessar o índice do vetor table. Neste caso, as posições dos vetores são como os baldes do exemplo acima. Cada item de table é o tipo Entry, cuja implementação funciona como uma lista encadeada (veja o atributo next). Quando você adiciona um item, se já houver outro item no mesmo balde (não necessariamente com o mesmo hash), ele é adicionado ao final da lista ligada.

Então, quando vocês faz um HashMap.get() ele primeiro usa o hash para ir no elemento certo do vetor table, depois ele percorre a lista ligada usando o equals para verificar se ele encontrou realmente a chave que você usou.

Conclusão

Hashing é um mecanismo excelente para classificar conteúdo de forma eficiente ou até mesmo para verificar a integridade de dados de forma relativamente segura (considerando que a probabilidade de colisão é pequena), mas não para identificar de forma única.

6

Note que não existe garantia de não colisão quando se usa funções de hash. Isso significa que strings diferentes podem produzir o mesmo número inteiro (isso é uma colisão). Um exemplo são as strings: "[email protected]" e "[email protected]". Ambas produzem o mesmo número inteiro na implementação de hashCode da classe String no Java.

Assim, tudo depende do contexto para o qual está sendo aplicado. Se é pra resolver um caso específico, eu tentaria primeiro a abordagem descrita aqui, pois é muito simples de implementar. Checar se houve colisão é também trivial de fazer. Caso ela não atenda, implementar outras é simples e, mais simples ainda, é usar algoritmos de hash prontos.

Veja a implementação em C++ de um algoritmo que se diz decente na geração de hashes para Strings: (facilmente adaptada para Java): https://stackoverflow.com/a/107657/2236741

Respostas relacionadas no SOen:

https://stackoverflow.com/questions/2624192/good-hash-function-for-strings

https://stackoverflow.com/questions/6120657/how-to-generate-a-unique-hash-code-for-string-input-in-android

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 .