Estruturas de Dados - Conceitos de Tabela Hash

os caras alunos sejam bem-vindos para aula de hoje na aula de hoje nós vamos falar sobre conceito de tabela hash o roteiro que eu vou seguir na hora de hoje será falaremos um pouco de motivação de tabela Jessie depois estruturar emos o tipo abstrato de dados depois falaremos sobre o detalhes de implementação e depois falaremos sobre funções de Regis Bom primeiramente uma motivação O que é que nós sabemos nós sabemos primeiramente com uma busca sequencial ela executem o tempo pode por quê Porque no pior casa para achar um determinado elemento dado uma chave nós teremos

que olhar toda a estrutura de dados não importa se ela é uma lista encadeada ou se é um vetor a busca binária por outro lado ela executa em tempo o dialog DN Entretanto a busca binária ela exige algumas restrições por exemplo ela existe que a gente esteja em um vetor e ela exige que esse vetor esteja ordenado a dúvida que surge é tenha possível executar uma busca em tempo melhor do que pode log dele sendo possível quais seriam as inscrições que devem existir sobre os dados e vamos estudar tabelas de hash pensando nessa motivação as

tabelas de hash se elas permitem busca sem tempo constantes satisfeitas algumas descrições em relação principalmente a função de espalhamento essa estrutura ela pode ter vários nomes dependendo do local ou da linguagem de programação onde ela foi implementada por exemplo em Python você deve ter se acostumado com uma estrutura de dados chamada de dicionário se você programa em outras linguagens com o da arte da plataforma plantar você provavelmente chama a mesma estrutura de dados só que dessa vez você chama ela de mapas e outros lugares essa estrutura de dados ela é chamada de arreios associativos e

assim por diante a princípio a chave de busca utilizada dentro de uma tabela hash se ela pode ser de qualquer tipo desde que ela possa ser mapeada em um tipo inteiro como nós vamos estudar hoje e vamos tentar entender o tipo abstrato de dados aqui quando nós fomos implementar uma tabela Race temos que entender que ela é um contêiner do jeito que a gente fez com pilhas e filas ela é uma estrutura em que a gente coloca elementos para depois buscar os elementos na hora de buscar os elementos só para saber isso nós utilizaremos uma

chave que nós chamaremos de cá então cá é a chave que mais vai me ajudar a buscar o registro específico o recuo enviar então é esse método mencionado aqui ele retorna uma entrada com chave igual a cá se ela existir caso contrário retorna num I will search Airton recebendo uma chave k e um valor ver ele insere essa entrada ver na chave cá se a chave não existir Então vamos assumir que a chave não existe para ver a inserção caso contrário nós vamos fazer uma atualização ou seja substitui se o registro está lá para que

ele tenha um novo valor então Street A então Cave ele funciona como inserção ou atualização de lipton é um método que remove mais chave k e o valor associado a ela nessa nossa disciplina nós implementar amo seu jeito enviar então em sortear Tom e os dele Thiagão entretanto com dicionários com tabelas de hash se outros métodos também são comuns por exemplo método size tem de retorna O número de entradas que existe naquela tabela de resto ou seja quanta Sensações por ocorrer E aí e também existe um método chamado oq7 ele retorna uma digita encadeada de

todas as chaves armazenadas na tabela para que serve essa lista encadeada para depois a gente poder por exemplo interar sobre todos os elementos dentro da tabela em pai então você deve ter se acostumado com isso seria um método ponto que da linguagem Python e você aprendeu indisciplinado anteriores a utilizar dicionário possam implementar íamos ela aqui Entretanto é um metro que seria interessante numa tabela de ré que você for utilizar velas ele retorna uma coleção contendo todos os valores Associados com as chaves armazenadas na tabela RS Ou seja é uma maneira de você conseguir obter todos

os valores sem a necessidade de passar as chaves e eu entrei 7 o último método aqui é o que retornaria uma coleção contendo todas as entradas do tipo chave valor da tabela então esses métodos desse slides aqui são as que nós não implementar e vamos nessa disciplina O nosso escopo vai ser apenas os métodos do slide anterior ou seja busca inserção e remoção de elementos e e vamos falar um pouco sobre detalhes de implementação nós queremos que a busca tem sessão e que a remoção ocorreu em tempo constantes nesse caso como eu faço para conseguir

achar um endereço de onde está o registro a partir de uma determinada a chave nesse caso que que eu tenho que fazer a chave ela tem que me indicar Onde está o registro Essa é a única saída que eu tenho a pessoa tem uma chave de busca e é o uso essa chave de busca para encontrar na memória o registro Então tem que haver um mapeamento da chave de busca para o endereço de memória a cada entrada da nossa estrutura de dados ela é composta por um chá limpar do tipo chave-valor 1k, ver e associação

entre essa chave e o endereço que estará o valor é um estar o valor é que definir o mapeamento a chave ela é um identificador único e deve ser vista como uma maneira de se obter o a região de memória onde o valor está então como eu posso chamar isso eu posso dizer então que a chave fornece ou proporci ona o endereço para o seu valor Então essa é a grande ideia da tabela de resto tabela hash Você tem uma chave e essa chave ele ajuda a dizer onde está o registro que você está procurando

a tabela ela pode ser organizado em memória com um vetor dado que este permite acesso em tempo constante o que nós estamos tentando obter aqui acesso em tempo e a um determinado o registro então dando que eu tenho interesse de um registro qual é a estrutura de dados que eu posso obter um registro em tempo constantes é um vetor Então é isso que nós utilizaremos para implementar internamente uma tabela de resto um vetor que que eu preciso fazer então usuário ele tem uma chave que não necessariamente é um link de um vetor a chave pode

ser uma estranha pode ser um tipo qualquer o que eu tenho que fazer material essa chave em um inteiro e depois de uma da chave um inteiro eu posso com esse inteiro Identificar qual é o índice do registro que eu estou buscando é justamente o que essa figura que está dizendo a chave que está desse lado de cá ela pode ser uma string que pode ser um objeto pode ser até mesmo inteiro pode ser pontos flutuantes desde que eu possa mapear essa chave em um inteiro porque porque eu estou utilizando uma implementação vetor esse inteiro

é que vai me ajudar a identificar a posição na memória do registro que eu estou procurando bom então seja h a função que faz realmente uma peamento também chamada a função de espalhamento e a chave o endereço de memória será dado por HK Então esta notação que utilizarei para dizer qual é o recuo o endereço de memória HD de cá os seus valores retornados por HD Car forem bem distribuídos e o intervalo entre 0 e n - 1 então precisaremos apenas um vetor de capacidade n para guardar todos os registros então na aula de hoje

vamos assumir primeiramente ausência de condições ou seja uma determina duas Chaves diferentes que mapeiam para o mesmo inteiro pela função de mapeamento vamos supor que não temos condições bom então assumindo ausência de colisão a estrutura básica que eu vou mostrar agora seria suficiente alguém daí é uma chave aqui a função de mapeamento H transformaria essa chave em um inteiro e eu procuraria um inteiro eu colocaria o inteiro né ou colocaria o valor não vetou na posição onde memória é indicada pelo inteiro bom então tem chave também tem um valor que eu quero armazenar a função

H transforma inteiro e eu coloco no vetor se tem uma chave dois eu faço mesmo transforma em um inteiro diferentes e coloca na posição definida por esse inteiro Você tem uma chave três Eu transformo essa chave em outro inteiro por exemplo esse daquele papel para n - 1 e eu coloco registro na posição em menos um então o que que existe aqui Chaves a função H que vai me dizer exatamente no vetor Onde eu posso colocar o registro e essa ideia que eu gostaria que vocês tivessem de agora em diante bom então função de hash

a Gama foi a cada a chave e o intervalo de 0 a em menos um vamos assumir isso Onde n é a capacidade do vetor que eu coloquei arranjo Quando eu falar arranjo Array Beetle em geral eu estou querendo falar a mesma coisa não é possível tratar condições quando duas Chaves elas apontam para o mesmo para o mesmo índice na verdade mas teremos que tratar as condições mas por hora vamos pensar em evitar essas colisões então a função de espalhamento ela tem que diminuir a quantidade de colisões Clara função de pagamento não vai garantir que

não haverão colisões e numa próxima aula futura a gente entende como o tratamento dessas condições pode ser feito uma função de hash se ela é dito boa se minimiza a ocorrência dessas condições uma função de hash boa provavelmente não vai eliminar completamente a as colisões ou poderia confeccionar as duas Chaves imaginando a função de resto dizer olha que tem uma colisão então não deu não vamos tentar eliminar as colisões com a função de resto vamos assumir por hora que não existem tudo bem mas no futuro a gente vai tratar essas corações tá no futuro você

vai entender o que que significa então o e vamos entender por hora que uma função é boa quando uma função de hash é boa quando diminui o melhor minimiza a ocorrência de posições é a primeira tarefa da função será transformar Chaves e tipos arbitrários e inteiros Então vamos assumir que queremos armazenar informações de funcionários de uma empresa e indexar essas informações pelo login único da pessoa então vamos assumir que todos os funcionários tem um login EA esse login que vai ser utilizado como chave de busca o login ele pode ser o primeiro nome da pessoa

mas se esse depois foi lido por alguém então outro login deve ser selecionado por exemplo por aquele funcionado bom então por exemplo se eu meu nome é o disse se existe outro licis na empresa eu poderia colocar o disse 02 algo nesse sentido bom então como Eu transformo a chave que seria por exemplo o nome pôde se esqueceria a chave de busca em um inteiro porque eu preciso de um inteiro para procurar no vetor eu posso simplesmente o melhor eu posso inicialmente se mapear caracteres caracteres de par inteiros a tabela é esse que pode ajudar

nesse caso a tabela é que seria é uma tabela que mapei a cada caractere para um índice inteiro por exemplo a maiúsculo loteria aumente 65 o b maiúsculo teria um ser associado ao inteiro 66 o a minúscula seriam 97 o b minúsculo seriam 98 o número 0 serial 48 o número um seria o 49 e assim por diante então se eu quero uma piada o nome o disse sem inteiro o que é que eu faço eu pego o valor do Hulk somo com o valor do ele some com o valor do i1 valor do é

e som e do oeste x 3 vezes por quê Porque o Unisystem três essas tá isso será transformado em um inteiro então se eu quero obter as informações do esses eu procuraria dentro de um vetor no índice 776 eu conseguiria esse tempo constantes por quê Porque eu consigo mapear o nome unisys em inteiro no tempo constantes e a verdade seria um tempo que depende do tamanho da stringhi Mas vamos estar vamos assumir que o tamanho da stringhi ele é delimitado por um carro tá vamos assumir ele não pode ter um login maior do que cá

o que é conta só para poder dizer que a tempo constante então nós podemos mapear qualquer login inteiro por exemplo disso e serial 776 Danielle e seria 830 Amanda terá 600 e teste Cleópatra seria 1218 e o valor inteiro encontrado seria o índice da entrada em um vetor o índice do registro dentro de um vetor e essa ideia que ilustra tudo que nós temos a dizer sobre uma tabela ref e entretanto essa ideia ela gera algumas condições por exemplo Orlando e o Reginaldo que são quadrinhos que são a leitura inversa um do outro eles seriam

mapeados para mesma para o mesmo índice o mesmo de Adriana e Ariadna porque é porque eles têm a mesma vocais as mesmas vagas então pessoas contendo as mesmas vogais e consoantes as mesmas letras me desculpa então pessoas que tenham nomes com as mesmas letras elas teriam uma piadas para o mesmo índice E isso quer dizer que essa função ela não espalha assim também uma função de resto que seria melhor ou quis para o espalharia os números de uma maneira melhor seria aquela que levasse em conta a posição dos caracteres o por exemplo levasse em conta

que aqui Washington na primeira posição e deve ter um valor diferente do último Como eu posso fazer isso eu posso assumir a primeiramente aqui meu nome é uma cadeia ao invés de um saco de caracteres e daí eu posso colocar uma fórmula que leve em conta o índice de cada um dos dos caracteres por exemplo vamos chamar esse primeiro caractere AC DC zero esse segundo caractere aquele ser um esse terceiro cara segundo primeiro segundo terceiro caracteres e 2 e assim por diante então para gerar o inteiro poderia usar uma fórmula como essa daqui onde eu

teria que atribuir um valor para por exemplo colocaria o valor do Ó e inteiro O Novo com Amor o HD o vezes um apresenta o que seria três elevado a k menos um quê que é o Caio o tamanho da string um dois três quatro cinco seis sete seria três elevado a 6 mas o h2r às vezes 3 elevado a 5 mas e assim por diante Segue uma nova função que agora leva em conta a posição dos caracteres isso para algum mar diferente de zero onde um e o quê que isso faria por exemplo para

a = 3 Orlando utilizando essa função ele geraria um índice 1121 1389 enquanto que o dinauro levaria ao índice 118 1173 ou seja agora Orlando e o Dinaldo começa a minha segunda função de resto eles levam a índices diferentes um valor de aalto quando eu digo alto por volta de 33 37 39 41 notem que eu tô escolhendo o Primus aqui tende a diminuir o número de colisões para algumas poucas normalmente estudos mostram que se a gente pega o Lucas para língua inglesa 50 mil palavras por exemplo alguns livros isso é bem documentado em livros

de estruturas de dados um valor por volta de 41 gera no máximo aí umas sete condições utilizando essa função Então 7 previsões quer dizer olha no máximo você vai ter que encontrar o índice usando a função e tempo constante e daí você procure mais 7 elementos de um por um até conseguir encontrar aquilo que você quer o que já é muito bom e se quer dizer que existe um tempo aí constante é que eu posso obter esses elementos assumindo realmente que o máximo de colisões teria séries é porque isso seria possível porque nesse caso é

possível fazer com que cada endereço de memória tem espaço para mais de uma entrada ou seja na posição zero eu vou colocar seis entradas no máximo na posição um também então a tabela a função de resto uma peia para e simples e nesse índice aqui eu procuro de um por um e essa seria uma ideia boa a tampa entretanto o valor de ar muito alto ele pode até mesmo levar a uma ver flow do do intervalo dos inteiros ou seja ficou tão alto valor por causa de um ano muito alto que aí ultrapassa o limite

de dois inteiros na verdade isso pode até acabar gerando e tabelas de resto muito grandes que ocupam muita memória então o que que se faz depois disso normalmente uma compressão poster definir um n dizendo olha não eu não quero eu vou usar aquela função anterior entretanto eu quero uma rede tamanho só cinco mil no máximo e o que é que você faz você utiliza o resto da divisão você computa da maneira que tinha feito antes e depois computa o resto da divisão e o resto da divisão pelo tamanho do Rei do vetor é onde você

vai colocar aquele registro é uma coisa que a gente pode perceber o tamanho que você coloca a promotora interfere Claro na presença de colisões que você usar um tamanho de Vetor igual a 1000 Vai ter muito menos condições do que se usasse um tamanho do vetor igual a cem por quê Porque em mil você consegue espalhar massa então o Eniac ele interfere na ocorrência depois de exames e para ajudar no espalhamento é interessante utilizar um número primo para ele porque porque ele quebra e alguns padrões que podem se repetir isso diminui as chances de ocorrer

determinados padrões da distribuição de dados por exemplo supondo que as chaves de um determinado aplicação eram 200 205 210 até 600 se você escolher por exemplo n = 100 então cada chave irá colidir com várias outras Chaves por exemplo o 200 vai colidir com o 300 que vai colidir com 400 que vai colidir com 500 que vai colidir com 600 entretanto se você utilizar um n = 101 a Só lembrando eu estou dizendo que vai corrigir porque porque um resto da divisão por 100 de todos esses elementos vai ser o mesmo o mesmo ocorre por

exemplo 201 e com 301 o resto da divisão por sem vai ser igual ao ou seja eles irão colidir mas se você escolher esse um ele igual a 101 nesse conjunto inteiro nós não teríamos nenhuma condição então isso aqui é havia um padrão era 205 210 o fato de ter Escolhido um primo fez com que a gente tinha um padrão da chave mas fez com que não houvesse um padrão na distribuição de dados é isso que eu queria na hora de escolher um um R inteiro porque a gente já viu agora existem vários ingredientes que

a gente precisa para construir uma tabela de hash quais deles são importantes do tamanho do vetor é importantes ou que porque um vetor maior normalmente tende a dar uma possibilidade de espalhar melhor os dados e diminuir as colisões a utilização de um tamanho de Vetor inteiro ajuda a gente a quebrar alguns padrões que pô o tempo que as condições ocorressem a própria função de resta também ela pode ser boa o seguinte sentido ela minimiza as colisões ou não ser tão boa por exemplo gera muitas colisões pega assistentes e Jerry e joga as estrias todas para

o mesmo índice do vetor na próxima aula nós implementar íamos esses conceitos em ser mais mais e em seguida veremos técnicas de tratamento de condições mas por hora era isso que eu gostaria de falar para vocês um forte abraço agradeço por terem assistido à aula até aqui se teve alguma coisa que não ficou muito cara na hora de hoje eu recomendo que vocês assistam um vídeo novamente Então até uma próxima oportunidade e [Música] E aí [Música]