Função hash
Nesta seção, discutiremos sobre a função hash que ajuda a executar o código hash da chave relacionada do item de dados na estrutura de dados, conforme mencionado a seguir:
HashItem interno ( interno chave ){
retornar chave % tamanho da mesa ;
}
O processo de execução do índice de um array é chamado de hashing. Às vezes, o mesmo tipo de código é executado para gerar o mesmo índice usando as mesmas chaves chamadas colisões que são tratadas por meio de diferentes encadeamentos (criação de lista vinculada) e implementação de estratégias de endereçamento aberto.
Trabalho de tabela hash em C++
Os ponteiros para os valores reais são mantidos na tabela hash. Ele usa uma chave para pesquisar o índice de um array no qual os valores das chaves precisam ser armazenados no local desejado em um array. Pegamos a tabela hash com tamanho 10 conforme mencionado a seguir:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Vamos pegar aleatoriamente quaisquer dados em chaves diferentes e armazená-las em uma tabela hash apenas calculando o índice. Assim, os dados são armazenados nas chaves do índice calculado com a ajuda de uma função hash. Suponha que tomemos dados = {14,25,42,55,63,84} e chaves =[ 15,9,5,25,66,75 ].
Calcule o índice desses dados usando a função hash. O valor do índice é mencionado a seguir:
| Chave | quinze | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Calcular Índice | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Dados | 14 | 25 | 42 | 55 | 63 | 84 |
Depois de criar o índice de um array, coloque os dados na chave no índice exato de um determinado array, conforme descrito anteriormente.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Depois disso, podemos ver que ocorre uma colisão se duas ou mais chaves tiverem o mesmo código hash que resulta no mesmo índice dos elementos do array. Temos uma solução para evitar as chances de colisão: selecionar um bom método de hash e implementar estratégias precisas.
Agora, vamos discutir as diferentes técnicas de implementação com a ajuda de exemplos adequados.
Exemplo: adicionar dados em uma tabela hash usando uma técnica de hash aberto
Neste exemplo, utilizamos uma técnica de implementação como Open Hashing para evitar colisão na tabela hash. No hashing aberto ou encadeamento, criamos uma lista vinculada para encadear os valores da tabela hash. O trecho de código deste exemplo está anexado a seguir e descreve a técnica de hash aberto:
#include#include
aula Tabela Hash {
privado :
estático const interno tamanho da mesa = 10 ;
padrão :: lista < interno > mesaTem [ tamanho da mesa ] ;
interno hashFunc ( interno chave ) {
retornar chave % tamanho da mesa ;
}
público :
vazio inserir ( interno chave ) {
interno índice = hashFunc ( chave ) ;
mesaTem [ índice ] . retrocesso ( chave ) ;
}
vazio visualizar tabela ( ) {
para ( interno eu = 0 ; eu < tamanho da mesa ; ++ eu ) {
padrão :: corte << '[' << eu << ']' ;
para ( auto isto = mesaTem [ eu ] . começar ( ) ; isto ! = mesaTem [ eu ] . fim ( ) ; ++ isto ) {
padrão :: corte << ' -> ' << * isto ;
}
padrão :: corte << padrão :: fim ;
}
}
} ;
interno principal ( ) {
HashTable hasTable ;
hasTable. inserir ( quinze ) ;
hasTable. inserir ( 33 ) ;
hasTable. inserir ( 23 ) ;
hasTable. inserir ( 65 ) ;
hasTable. inserir ( 3 ) ;
hasTable. visualizar tabela ( ) ;
retornar 0 ;
}
Este é um exemplo muito interessante: construímos uma lista encadeada e inserimos os dados na tabela hash. Em primeiro lugar, definimos as bibliotecas no início do programa. O < lista > biblioteca é usada para a implementação da lista vinculada. Depois disso, construímos uma classe chamada “HashTable” e criamos os atributos da classe que são privados como tamanho da tabela e array da tabela usando a palavra-chave “private:”. Lembre-se de que os atributos privados não podem ser usados fora da classe. Aqui, consideramos o tamanho da tabela como “10”. Inicializamos o método hash usando isso e calculamos o índice da tabela hash. Na função hash, passamos a chave e o tamanho da tabela hash.
Construímos algumas funções obrigatórias e tornamos essas funções públicas na classe. Lembre-se de que as funções públicas podem ser usadas fora da classe em qualquer lugar. Usamos a palavra-chave “public:” para iniciar a parte pública da classe . Como queremos adicionar novos elementos à tabela hash, criamos uma função chamada “InsertHash” com uma chave como argumento da função. Na função “insert”, inicializamos a variável de índice. Passamos a função hash para a variável de índice. Depois disso, passe a variável de índice para a lista vinculada tableHas[]usando o método “push” para inserir um elemento na tabela.
Depois disso, construímos uma função “viewHashTab” para exibir a tabela hash para ver os dados recém-inseridos. Nesta função, pegamos um loop “for” que busca os valores até o final da tabela hash. Certifique-se de que os valores sejam armazenados no mesmo índice desenvolvido usando uma função hash. No loop, passamos os valores em seus respectivos índices e finalizamos a classe aqui. Na função “principal”, pegamos o objeto de uma classe chamada “hasTable”. Com a ajuda deste objeto de classe, podemos acessar o método de inserção passando a chave no método. A chave que passamos na função “main” é computada na função “insert” que retorna a posição do índice na tabela hash. Exibimos a tabela hash chamando a função “view” com a ajuda de um objeto “Class”.
A saída deste código está anexada a seguir:
Como podemos ver, a tabela hash é criada com sucesso usando a lista vinculada em C++. O encadeamento aberto é usado para evitar a colisão do mesmo índice.
Conclusão
Por fim, concluímos que uma tabela hash é a técnica mais emergente para armazenar e obter chaves com pares de valores para lidar com grandes quantidades de dados de forma eficiente. As chances de colisão são muito altas na tabela hash, destruindo os dados e seu armazenamento. Podemos superar essa colisão usando diferentes técnicas de gerenciamento de tabelas hash. Ao desenvolver a tabela hash em C++, os desenvolvedores podem aumentar o desempenho usando a técnica mais adequada para armazenar os dados na tabela hash. Esperamos que este artigo seja útil para sua compreensão da tabela hash.