Introdução à função hash em Java
Como sabemos que Java é uma linguagem orientada a objetos, portanto, deve haver um mecanismo para descrever o estado de um objeto, independentemente do tamanho de um objeto. A função de hash em Java surgiu para atender a esse requisito.
O que é uma função hash?
Uma Função Hash pode ser definida como uma função que retorna um valor inteiro correspondente a um Objeto. A função Hash sempre retorna o mesmo valor inteiro para o mesmo objeto. O valor inteiro retornado pela função hash é chamado Valor de Hash. A seguir estão os pontos importantes sobre a função Hash:
- Sempre retorna um número inteiro (4 bytes) para um Objeto.
- Não podemos calcular o estado do objeto a partir do valor do hash que é a função de hash que é irreversível por natureza.
- Dois objetos iguais terão o mesmo valor de hash.
- Dois objetos desiguais nem sempre têm valores diferentes de Hash.
Aplicações da Função Hash
Aqui estão os aplicativos comuns das funções de hash:
1. Estruturas de dados
Quase toda linguagem de programação contém estruturas de dados baseadas em hash. Por exemplo, java contém estruturas de dados de tabela Hash, mapa de hash, conjunto de hash e conjunto de árvores baseadas na função hash. A base dessas estruturas de dados é o design do valor-chave, onde cada chave é única, enquanto o mesmo valor pode existir para várias chaves.
2. Resumo da Mensagem
Esse algoritmo é usado em uma verificação de integridade de dados. Esse algoritmo recebe uma mensagem de qualquer tamanho como entrada e produz dados de comprimento fixo (128 bits) como saída. Exemplos dos algoritmos de compilação de mensagens incluem MD2, MD4, MD5 e MD6.
3. Algoritmo de hash seguro
Esse algoritmo é usado para segurança de dados e é usado em aplicativos e protocolos como Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 e SHA-3 são categorias comuns do algoritmo Secure Hash.
4. Verificação de senha e armazenamento
Vamos considerar um cenário de logon no qual, quando uma senha é digitada para autenticar um usuário, um valor de hash da senha digitada é calculado e enviado pela rede ao servidor onde o hash do original está armazenado. Isso é feito para garantir que nenhum sniffing seja feito quando uma senha é enviada do cliente para o servidor.
5. Operação do Compilador
Como palavras-chave diferentes são usadas em uma linguagem de programação, para diferenciar essas palavras-chave e identificadores, o compilador usa um conjunto de hash que é implementado usando uma tabela de hash para armazenar todas essas palavras-chave e identificadores.
6. Algoritmo de Rabin-Karp
É um algoritmo de busca que utiliza o hash para procurar um ou mais padrões em uma determinada string. É um dos algoritmos mais usados.
7. Interfaces comparáveis e comparadoras
Essas interfaces contêm funções que são usadas para comparar dois objetos por vez. O valor de retorno dessas funções pode ser negativo, zero ou positivo, com base no fato de um determinado objeto ser menor que, igual ou maior que o objeto com o qual estamos comparando. Comparador interno e interfaces comparáveis usam uma função hash para comparar objetos um do outro.
8. Fila prioritária
A fila de prioridade é diferente da fila normal que segue a ordem FIFO (primeiro a entrar, primeiro a sair). Na fila de prioridade, os elementos são organizados em ordem personalizada com base em sua prioridade, que é implementada internamente usando comparáveis e comparadores, que os internos se baseiam nas Funções Hash.
Projetando Funções de Hash
Aqui estão alguns princípios gerais de design para criar funções de hash:
- Uma função de hash deve ser avaliada com eficiência.
- Os valores de hash calculados a partir das funções de hash devem ser distribuídos uniformemente, o que ajuda a evitar colisões.
- A linguagem de programação Java fornece uma função geral de hash com o método hashCode () na superclasse Object.
public int hashCode ()(
//Logic goes here
)
Colisão de hash em Java
Uma colisão de hash ocorre quando dois ou mais objetos retornam o mesmo valor de hash. Vamos dar um exemplo de um mapa de hash Java que armazena dados em pares chave-valor. Quando colocamos um objeto em um mapa de hash, o valor de hash da chave é calculado e com base nessa localização do depósito de valor de hash para armazenar o objeto de valor. Objetos com diferentes valores de hash devem entrar em diferentes buckets. Quando dois ou mais objetos têm o mesmo valor de hash, eles são armazenados no mesmo local do depósito usando uma estrutura de dados adicional chamada lista vinculada. Todos os objetos com o mesmo valor de hash são encadeados usando uma lista vinculada. Esse mecanismo é chamado encadeamento. A seguir, as maneiras de lidar com colisões é uma função hash:
- Encadeamento: como já abordado, a idéia por trás do encadeamento é criar uma lista vinculada de objetos com o mesmo valor de hash. O encadeamento é uma técnica simples, mas requer sobrecarga adicional de memória.
- Endereçamento aberto: nesta técnica, todos os elementos são armazenados em uma tabela de hash na qual cada entrada contém um registro ou NULL. Quando um elemento é pesquisado, cada entrada na tabela de hash é pesquisada pelo registro desejado até que o registro necessário seja encontrado ou se conclua que o registro não existe na tabela.
Vantagens do hash
A seguir, estão as vantagens do hash:
- Compare o conteúdo de dois arquivos com facilidade e eficiência, sem abri-los.
- As funções de hash são usadas para verificar a integridade de um arquivo.
- Com a ajuda do hash, a operação de pesquisa nas estruturas de dados ficou mais rápida.
- As funções de hash desempenham um papel vital na segurança dos dados, pois a maioria dos algoritmos e protocolos de segurança utiliza o hash.
- Hashing converte dados em um valor ou chave de tamanho fixo mais curto, que representa a string original que pode ser enviada pela rede.
Desvantagens do hash
Além das vantagens, também existem algumas limitações do hash:
- O hash não pode ser implementado para classificar dados.
- A colisão de hash não pode ser praticamente evitada, o que, por sua vez, leva à ineficiência.
Artigos recomendados
Este é um guia para a Função Hashing em Java. Aqui discutimos aplicativos da função hash, além de vantagens e desvantagens. Você também pode consultar os seguintes artigos para saber mais -
- Declaração e Inicialização do VB.Net
- Programa Java mostrando HashMap e TreeMap
- Tipos de hash no DBMS
- Técnicas de esteganografia
- Matrizes na programação Java
- Hashmap em Java