Hashing - Teoria e Implementação de Tabelas de Símbolos

ESTRUTURA DE DADOS II 60 HORAS PROF JULIANO RATUSZNEI EMAIL JULIANORATUSZNEIUNICIDEDUBR 2 A teoria consiste em organizar os dados em estruturas semelhantes a fichários Criar um índice por ordem alfabética eou numérica Definir estruturas específicas para armazenálos Separar os dados por tipos e assuntos HASHING 3 implementação de tabelas de símbolos por meio de tabelas de dispersão tabelas de hash Um tabela de símbolos é uma tabela com duas colunas uma coluna de chave keys uma de valor values Dizemos que cada linha da tabela é um item Cada item associa um valor a uma chave Vetores matrizes listas ligadas pilha fila entre outros HASHING TABELA DE SÍMBOLOS TS chave valor wwwebaycom 6613519287 wwwprincetonedu 12811212815 wwwcsprincetonedu 12811213635 wwwharvardedu 1281036024 wwwyaleedu 130132518 wwwcnncom 642361620 wwwgooglecom 2162394199 wwwnytimescom 199239136200 4 Hashing tem dois ingredientes fundamentais uma função de hashing estrutura de armazenamento com índices um mecanismo de resolução de colisões dados podem ser duplicados evitar duplicatas HASHING 5 Problemática Imagine um pequeno país que possui 10 mil cidadãos Considere que esta tabela leva o número do CPF e o nome do cidadão Como armazenar a tabela HASHING chave valor 0586 José Carlos 0603 Alberto Santos 0644 Ingrid Silva 3675 Julio de Campos 6 Como armazenar a tabela Vetor com 10 mil posições Utilizamos a própria chave como índice do vetor O vetor é conhecido como tabela de hash e terá muitas posições vagas desperdício de espaço mas a busca get e a inseção put serão extremamente rápidas HASHING chave valor 0586 José Carlos 0603 Alberto Santos 0644 Ingrid Silva 3675 Julio de Campos 7 HASHING Exemplo 2 Imagine uma lista ligada cujas chaves são nomes de pessoas Suponha que a lista está em ordem alfabética Para acelerar as buscas divida a lista em 26 pedaços como uma lista telefônica nomes começando com A nomes começando com B chave valor associado Antonio Carlos 8533151 Arthur Silva 4210328 Bruna Carvalho 7532199 Vitor Lima 5535944 Wellington Silva 5159760 Yan Fraga 9537822 8 HASHING Para acelerar as buscas divida a lista em 26 pedaços como uma lista telefônica nomes começando com A nomes começando com B Assim temos um vetor de 26 posições é a tabela de hash cada posição do vetor aponta para o começo de uma das listas chave valor associado Antonio Carlos 8533151 Arthur Silva 4210328 Bruna Carvalho 7532199 Vitor Lima 5535944 Wellington Silva 5159760 Yan Fraga 9537822 HASHING um vetor de 26 posições é a tabela de hash cada posição do vetor aponta para o começo de uma das listas Comparamos com a busca binaria Comparamos com a busca sequencial A B C V W Y 8533151 Antonio 4210328 Arthur Silva 7532199 Bruna Carvalho 5535944 Vitor Lima 5159760 Wellington Silva 9537822 Yan Fraga BUSCA Vetor Hash Lista de Nomes com A 9 FUNÇÕES DE HASHING Uma tabela de dispersão ou tabela de hash hash table é um vetor cada uma de cujas posições armazena zero uma ou mais chaves e valores associados 10 Parâmetros importantes M número de posições na tabela de hash N número de chaves da tabela de símbolos NM fator de carga load factor 11 FUNÇÃO DE ESPALHAMENTO Função de hashing hash function transforma cada chave em um índice da tabela de hash Espalha as chaves utilizando alguma lógica de espalhamento balanceamento Responde a pergunta Em qual posição da tabela de hash devo colocar esta chave A função de hashing espalha as chaves pela tabela de hash 12 FUNÇÃO DE ESPALHAMENTO A função de hashing espalha as chaves pela tabela de hash A função de hashing associa um valor hash hash value entre 0 e M 1 a cada chave No exemplo dos CPFs temos 1 e a função de hashing é a identidade Pois não são todos os índices ocupados No exemplo dos nomes de pessoas temos 1 e a função de hashing é nomecharAt0 Pois temos sobreposições de elementos Nesse caso a função de hashing produz uma colisão quando duas chaves diferentes têm o mesmo valor hash e portanto são levadas na mesma posição da tabela de hash FUNÇÃO DE ESPALHAMENTO Exemplo Chaves são números de identificação 7 dígitos de estudantes da universidade e M vale 100 Uma possível função de hashing 2 primeiros dígitos da chave Outra possibilidade 2 dígitos do meio Outra possibilidade 2 últimos dígitos Qual dessas espalha melhor as chaves pelo intervalo 0 99 13 8536152 7210629 8536339 8536002 8067490 8536106 8536169 8531845 14 FUNÇÃO DE ESPALHAMENTO Outro exemplo função de hashing que leva qualquer número de CPF brasileiro que tem nove dígitos Correspondente dígito verificador um número entre 0 e 99 Por exemplo leva 111444777 em 35 O dígito verificador de um CPF depende de todos os dígitos do CPF Ideal a função de hashing deveria usar todos os dígitos da chave assim chaves ligeiramente diferentes serão levadas em números muito diferentes podemos usar o valor hash como checksum para verificar a integridade de um dado FUNÇÃO DE ESPALHAMENTO 15 Escolha M e a função de hashing de modo a diminuir o número de colisões espalhar bem as chaves pelo intervalo 0 M 1 FUNÇÃO DE HASHING MODULAR Que funções de hashing são usadas na prática Se as chaves são inteiros positivos podemos usar a função modular resto da divisão por M Exemplos com M 100 M 43 e M18 Em hashing modular é bom que M seja primo Utilizado pela maioria das funções hash 16 Hash Chave M 100 M43 M18 6613 13 34 7 374 74 30 14 9608 8 19 14 5521 21 17 13 1830 30 24 12 8582 82 25 14 8833 33 18 13 3073 73 20 13 7138 38 0 10 5254 54 8 16 3756 56 15 12 101 1 15 11 3066 66 13 6 8816 16 1 14 7941 41 29 3 8838 38 23 0 6686 86 21 8 9767 67 6 11 460 60 30 10 588 88 29 12 6958 58 35 10 2723 23 14 5 FUNÇÃO DE HASHING MODULAR No caso de strings podemos iterar hashing modular sobre os caracteres da string No lugar do multiplicador 43 poderia usar qualquer outro inteiro primo mas suficientemente pequeno para que os cálculos não produzam sobrecarga do sistema 17 int h 0 for int i 0 i slength i h 43 h scharAti M 18 HASHING IDEAL Hipótese do Hashing Uniforme Vamos supor que nossas funções de hashing distribuem as chaves pelo intervalo de inteiros 0 M 1 de maneira uniforme todos os valores hash igualmente prováveis e independente 19 HASHING IDEAL Exemplo Supõese que os números sorteados pela Loteria Federal são todos igualmente prováveis Supõese também que são independentes só porque 13 nunca foi sorteado ele não tem maior probabilidade de sair no próximo sorteio Nenhuma função determinística satisfaz a Hipótese do Hashing Uniforme Essa impossibilidade é uma questão profunda e fundamental em Ciência da Computação Mas a hipótese é útil porque permite fazer cálculos para prever o desempenho aproximado de tabelas de hash 20 REFERENCIAS FEOFILOFF P Hashing Departamento de Ciência da Computação Instituto de Matemática e Estatística da USP httpswwwimeuspbrpfestruturasdedadosaulassthashhtm l Atualizado em 21052018