Estruturas de Dados - Tratamento de Colisões

E aí [Música] Olá caros alunos na aula de hoje nós vamos continuar o nosso estudo de tabela hash só que falamos sobre tratamento de colisões nas aulas anteriores nós tentamos evitar esse assunto para facilitar um pouco código deixar códigos um pouco mais simples entretanto uma tabela rest que não trata uma colisão não é uma tabela rest porque não tem como evitar que essas colisões ocorreram na aula de hoje nós vamos seguir este roteiro falaremos sobre uma introdução depois falaremos sobre uma técnica de tratamento de colisão que ao encadeamento e separado depois falaremos sobre o teste

de Near outra técnica de tratamento de colisão e depois falaremos sobre detalhes de implementação do teste linear é só um pouco de introdução a presença de colisões que foi o que a gente evitou o tratar Até agora ela ocorre quando duas Chaves k1 e K2 geram H dica um igual a dica 2 ou seja elas apontam para o mesmo endereço de memória isso impede que a gente faça a imediatamente a inserção de um novo item diretamente na posição agadecarp Então a gente tem esse item que a gente quer colocar esse cara de ver diretamente na

posição HD car só que como existem condições a gente não pode simplesmente chegar e atualizar que foi o que a gente fez na aula passado e para resolver as condições ou melhor para tratar a condições nas colisões nós podemos utilizar tanto um espaço de memória adicional quando um espaço no próprio retorno próprio arranjo e vamos estudar um exemplo de cada uma dessas abordagens vamos falar sobre o encadeamento separado que que seria aceitar adiamento é separado é uma ideia simples para tratar horizons é a gente faz o seguinte na posição do vetor onde tem onde foi

um de ouvir a pontuação onde o índice nos levou tá o ensino e levou para cá ou seja a função de resto nos trouxe para cá e aqui inicia Na verdade o encadeamento é de elementos que podem política uma boa função de hash se fará com que a maior parte dos endereços fique vazio ou com apenas um elemento então uma boa função de resto faria com Quimera tivesse só um elemento aqui o que nos Faria ter uma consulta em sessão remoção em tempo com estamos que é o que a gente gostaria de ter de novo

isso só ocorre com boas condições de resto Tem que haver todo um estudo Para realmente saber se a gente está tendo esse proveito de ter essas operações em tempo constante Ao colocar n elementos em endereços espera-se ter em dias por n entradas por endereço na verdade em média a gente tem n-por-n entradas por endereço esse número aqui ele é chamado de fator de carga esse número aqui deveria ser limitado por uma constantes e de em constante ela tem que ser menor do que um ou seja tem que sobrar valores e idealmente vai sobrar valores aqui

vai sobrar digamos endereço sces vão ter vários endereços que não vão ser utilizados e os que forem utilizados o que que a gente quer que tenha um pouco os elementos aqui dentro que a gente possa estudar e dizer olha todos eles estão limitados por um número carro O que que a gente vai ter que modificar nós vamos ter que modificar as operações em ser Titan de leite ae Tom e Travis Walton No final a gente eu vou mostrar como a implementação pode ser feita essa daqui é um exemplo da tabela rest com entrad amento separado

vamos supor que a gente tem uma função de hash hdk e essa função de hash hdk pela recebe inteiros como parâmetros então números inteiros são recebidos e o que que eu faço eu faço apenas ficar mod 13 por quê Porque só tem 13 elementos aqui no meu vetor e os índices vão de 0 a 12 quando chegar o elemento 55 eu faço 55 mod 13 e de Glória 55 ele vai ter que ficar na posição três então eu não coloco 55 no Array lembrando encadeamento é separado de dentro do Array apenas inicia o encadeamento como

se fosse uma digita em cadeado aqui de alimentos então no vetor O que é que nós temos nós temos ponteiros no vetor e esses ponteiros vão iniciar uma lista encadeada e esta lista encadeada ter a todos os elementos com o mesmo índice Ou seja todos os elementos que permitiram o nome separado aqui indica que a gente vai utilizar espaço adicional espaço que não foi alocado a priori do momento em que a gente se alocou o tamanho do Array eo encadeamento significa que eles vão ficar aqui em cadeados Então se vocês forem olhar para essa figura

vão notar os 55 mod 13 = 3 o 29 mod 13 também = 3 e o 42 mod 13 também é boa três por quê Porque o resto da divisão por 13 em todos eles = 3 o ar e ele tem e vai para o índice zero assim como 39 por quê Porque o 39 é um múltiplo de 13 tão três vezes 393 vezes umas três vezes uma três ou seja o resto da divisão exemplo bom então esse é o encadeamento separado uma ideia muito simples você implementa uma tabela de hash criando o Array de

se alistem ponteiros e esses ponteiros vão iniciar uma lista encadeada contendo todos os elementos que sofreram colisões e daí Claro tem que ver Tem que haver um estudo para verificar se isso aqui realmente vai ser em tempo constantes tem que esses elementos aqueles não podem crescer muito essa listas encadeadas ela não podem crescer ruim se a função de resto no portão boa ela vai acabar mapeando todo mundo por exemplo para um elemento só e daí ficaria uma lista com todos os elementos aqui isso aí com certeza não seria um não teríamos acessos buscas inserções em

em tempo constante tá então tem que ir um tomar um certo cuidado na hora de dizer que realmente aqui a gente vai ter tempo constante Tem que haver o estudo para ela eu disse que isto realmente vai E qual é uma outra estratégia que nós poderemos utilizar uma outra estratégia serial test the near as colisões Elas serão tratadas sem alocação de memória adicional então não teremos memória adicional nós usaremos o próprio vetor o próprio arranjo e se tentamos inserir um item kv em um endereço aí ocupado com igual hdk tá então a gente pegou a

chave transformou a chave inteiro e a gente tentou colocar numa posição aí e percebeu a essa posição aqui está ocupada por um outro elemento então o que que nós vamos fazer nós vamos tentar no endereço aí mais um O que significa que seu índice me levou para cá e aqui tá ocupado Então eu tento colocar tu e as tentativas continuou até se encontrar o endereço que aceite o novo item aqui tem até uma figurinha que exemplifica tudo isso assumindo que queremos colocar um elemento com chave k = 16 tendo a mesma função anterior então 16

mod 13 me levaria para a posição 3 aqui a gente está sumindo que nós não estão nós não temos um uma rede ponteiros tá nós estamos colocando os elementos diretamente não arreia que não é um tratamento separar é uma outra estratégia então quando vem um elemento de índice 16 Eu Quis colocar ele na posição três e percebi Olha já tenho 55 lá o que que eu faço Olha eu não quero perder esse novo elemento Então vou colocar na posição seguintes só que a posição seguinte também estava ocupada eu não quero perder esse elemento eu vou

colocar na outra posição que a 43 E também estava ocupada e eu não quero perder de novo elemento eu gosto dele então vou tentar na posição seguinte que estava vazia Então esse 16 ele ficou um pouco longe da posição original dele porque porque eu fui tentando até conseguir encontrar uma posição você tá primeiro na três depois na quadra e na cinco até chegarmos na posição ser livre e bom então isso quer dizer o quê que a gente vai criar essa nova estratégia no em frente ai Tom só que ao criar essa nova estratégia no insert

Python a gente vai ter que alterar também as funções ventre Vietnã e de Elite ai Tom porque porque agora o Victor livyatan ele vai receber uma chave vai saber qual é o endereço onde ela a chave deveria estar mas agora vai dele ao não encontrar o registro naquela posição ela deve continuar procurando nas posições seguintes por quê Porque é uma estante ai tá ele pode ter colocado o elemento nas posições seguintes seu Street não pode ter colocado os elementos na posição seguintes então recriar também tem que procurar nas posições seguintes i c k não existir

Então não é trivial então finalizar a em uma posição vazia ou seja se essa chave cara realmente não está no vaso no vetor então o que que acontece com o Victor evita ele vai continuar procurando até percebeu Paquetá numa posição vazia o insert aiton Teria colocado nessa posição vazia se o elemento existisse como eu cheguei numa posição vazia então é provavelmente o escritório tá nunca colocou esse carro aqui é o nome teste de lear ocorre porque acessar o HD car na verdade faz ter implica em testar a chave para verificar se encontramos a entrada desejada

se não encontramos nós procuramos na Exposições consecutivos mas operações que vão invocado dele Titan vamos supor poder retirar Então vai ser chamado várias vezes então as operações em dele então não poderão agora remover os hippies pois isto faria com Que Alguma chave não puder pudesse não ser mais encontrada pelo metrô e viagem por exemplo no no cenário anterior nós colocamos o 16 na posição 6 porque porque nós tentamos nos aqui na posição Onde está o 55 depois tentamos na posição digital 30 depois tentamos na posição está o 43 até cair aqui no 16 só que

vamos supor que alguém disse olha eu tenho que remover os 55 oi e daí se o dele Titãs chega aqui de séria vou remover os 55 e vou colocar o menos um que significava estar vazio se ele fizer isso então eu entro enviar então não vai mais conseguir encontrar o 16 porque porque quando eu fosse amar o Vitor enviar então ele vai procurar nessa posição aqui e vai verificar onde essa posição tá vazia se essa posição tá vazia o 16 não existe ele vai interpretar dessa forma e vai estar errada porque porque eu 16 está

em algum lugar aqui mas ao invés de mudar o vento enviar então a gente vai mudar o dele Titan para não deixar que isso Socorro O que é que nós vamos fazer nós vamos fazer com que o delitia então ele não remova o o elemento mas substitua por um marcador chamado disponível que que significa ser marcador é uma outra Flag que a gente pode utilizar ao invés de colocar menos um no vetor a gente pode colocar um outro a fazer pelo menos dois elementos os dois significa olha aqui tá disponível só não vou chamar de

vazio porque o vidro e aí também quando olhar pelo menos dois vai saber tem que continuar buscando por quê porque alguém removeu esse número daqui entra tanto em estante Airon quando ele olhar ou menos dois ele vai dizer Ah legal aqui tá disponível não tá vazio eu posso colocar tanto no Brasil quanto no disponível então se eu preciso inserir aqui eu vou inserir vem aqui bom então dele já e também vai ter agora essa noção de disponível e nesse caso as buscas pelas Chaves cá elas podem pular pelos endereços disponíveis e continuar até encontrar a

chave ou uma célula vazia Então eu vi triviais como ele procurou numa determinada posição ele viu que lá tá disponível tá que pensou aqui tá disponível por que existia algo aqui que foi apagado então aqui foi marcado como disponível ele não foi marcado mais com o vazio então eu posso procurar na posição seguinte por quê Porque quem eu estou procurando que é o elemento 16 ele pode estar na posição seguintes I will start a o que que ele vai dizer ele vai dizer olha alguém marcou aqui como disponível isso quer dizer que eu posso ir

lá e colocar o que eu quiser E aí a alguns problemas o teste de near-end agrupa os elementos em posições contíguas então as pesquisas elas podem se tornar lentas outras estratégias de agrupamento de diziam por exemplo teste quadrático que ao invés de testar aquela posição a posição e mais um ela atesta a posição e mais FJ onde FJ vai ser igual a j o quadrado ou seja na primeira tentativa ela vai procurar o imaser ó quadrado na segunda tentativa vai ser o II mais um ao quadrado na terceira tentativa vai ser ui mais 2 ao

quadrado isso faz com que é a primeira tentativa vai ser na posição a segunda vai ser do lado a outra vai ser um pouquinho mais distantes Então esse próximo as tentativas vão ter um fator quadrático aqui só para garantir que não vai ficar um monte de elemento contigo isso vai evitar o agrupamento sequencial Mas provavelmente vai criar outros padrões agrupamento se ele não for prima então teste quadrático pode até falhar porque é porque ele pode ficar pulando e vai acabar voltando para a posição inicial sem ainda tendo posições vazias no Beto então de pula pula

pula de repente ele pula volta continuar pulando e daí ele vai acabar dizendo olha não não tem posição para colocar esse elemento aqui mas tem posição de inverno vetor Então esse é um toque cuidado a ser tomado Na verdade são cuidado que deveria ser tomado até com n primo porque com ele é primo isso também pode ocorrer Entretanto é um pouquinho mais rápido mas o problema também pode ocorrer e o resto em duplo consiste em encontrar uma função a guinha para tratamento de colisões Ou seja a gente vai fazer o imas SJ de novo não

é vai ser mais e mais um e mais dois e mais três não vai ser um e mais FJ ou onde esse FJ ele vai utilizar uma função a galinha basicamente a dizer Olha eu tentei a primeira forma de indexação cheguei naquela posição como eu cheguei naquela posição e aquela posição tá ocupada então eu uso uma outra função de backup que já foi previamente construída e essa segunda função de backup que já foi previamente construída vai ser utilizada nesse caso tá então tem duas funções uma que vai ser a primeira tentativa e outra função que

vai me ajudar nas tentativas seguintes é a função de hash secundária ela não vai poder resultar em 0 e uma escolha comum seria essa função aqui para algum número primo que menor que me Então seria configurar esses parâmetros aí e utilizar essa segunda função mas não falaremos sobre ela eu já estou muito satisfeito se vocês entenderem o primeiro hash e saberem que esse primeiro o teste de né ar e saber em que esse teste de Near tem alguns problemas que essas outras funções aí podem resolver principal desses problemas é que os elementos vão acabar criando

clusters consecutivos ocupados e isso pode não ser bom porque pode fazer com que a busca fique longa pode fazer com que a gente perca aí essa ideia de obtenção em tempo constante é mas é ele que nós vamos implementar nós vamos implementar o teste de né ar e que basicamente significa onde ficaram retrô ibiatan modificar o restante Tom e modificar o dele Tipo nós vamos dizer que o disponível do vetor vai ser alguém com r a = - 2 Então na hora de telecar nós não vamos colocar o menos um mas o de Topo que

isso significa vazio nós vamos colocar o menos dois por que significa disponível tá então a gente vai diferenciar O que é vazio do que é disponível utilizando a chave menos dois para disponível a chave a - 1 para o Street Fighter irá tratar o -1 -2 para uma coisa só ele que é isso aí tanto pode ser menos um homem nos dois eu posso inserir Mas o Vitor livyatan vai tratar o menos um como eu tenho que parar minha busca por que tá vazio e o menos dois combatendo que continuar a minha busca bom então

vamos ver isso aqui no código esse daqui é o trivial Tom assim táxi aqui de a semântica dos parâmetros e a mesmo então a pessoa passa um aluno e eu procuro na minha estrutura de dados interna e coloco no na própria variável que foi passada aqui como referência e daí aviso se foi encontrado ou não e agora função de hash se ela vai me levar uma localização só que eu vou tratar essa localização apenas com a localização Inicial Talvez seja necessário buscar um pouquinho mas se for necessário buscar mais eu aviso nessa variável mortos e

bom e o que que eu vou fazer eu vou iniciar nessa startlog que vai ser a minha posição inicial e vou internar Começando por ela então quem vai ter ar vai ser a variável location vai ter aqui um por um Iniciando em startlog que era aquela posição base aquela posição que esperaria encontrar aquela chave ó e aqui eu vou iniciar um to while eu só vou parar aquecer do frio enquanto Na verdade eu vou esperar enquanto o location for diferente destaques Lock ou seja não fiz um laço e acabei voltando para ele e mortos sorte

ou seja ainda ainda tem espaço mais para ser procurado Ele tá em conta não fiz um laço aqui no círculo eu continuo procurando e enquanto ainda tiver mais lugar para procurar eu procuro Vamos tentar entender isso aqui dentro desse desse laço tem um e se eu cheguei numa posição essa posição é exatamente aquilo que eu estava buscando então eu sei que eu não preciso mais procurar por quê Porque eu achei e se essa posição aqui que eu cheguei na minha busca foi = -1 eu sei também que eu não preciso mais procurar por quê Porque

tá vazio Caso contrário eu continuo procurando Lembrando que eu tô pensando aqui de forma circular eu tô colocando mod Max atrás mais um para quê Porque se eu cheguei no final do vetor eu vou ter que continuar procurando no início do vetor daqui eu tenho que verificar se eu encontrei onde eu encontrei quando eu saio do laço por quê porque se eu sair do laço porque o r a eram iguais com um elemento que eu achei então eu verifico Olha o elemento onde eu parei esse laço é o elemento que eu queria procurar se sim

eu encontrei esse eu encontrei eu coloco na variante se eu não encontrei eu não faço nada então essa é a ideia do entre então ele vai continuar procurando enquanto tiver posição diferente de menos 1 ou em conta não achei um elemento Oi e o de leite ae Tom utility TAM Ele parece um pouquinho mais complicado mas percebo Ele é igual ao have Higher than in Grande PA essa parte aqui Eu Só Tô verificando se eu preciso procurar o elemento tá então procura um elemento procura o elemento até encontrar aquele alimento que eu quero remover e

eu uso o mesmo critério do litro Eaton ou só vou parar a busca se eu encontrar o elemento ou se eu chegar no menos um indicando a do elemento não existisse Se eu sair desse laço porque eu encontrei o elemento Olha só bem aqui eu saí do laço porque eu encontrei no vetor alguém com aquele r a então eu coloco instrutor location é igual aluno só que percebam aqui eu coloco - 2 - 2 significa disponível significa Olha numa próxima busca eu tenho que continuar as buscas o mesmo ao encontrar o menos dois então na

hora de deletar não coloco mais menos um como eu fazia antes agora eu coloco menos estudos então é essa ideia do bilhete ai Tom muito parecido com uma entre viatone é certo essa parte final que a gente já trabalhou no início da aula Oi e o Stitch ai Tom Bem winstat Airton e de inicia naquela localização daquele location e ele vai fazer o que ele vai continuar procurando uma localização que seja = -1 ou igual a menos dois o que é porque ele quer achar alguém menos um homem menos dois para colocar o que veio

porque o arame até naquela posição então ele vai dizer de location = get it has e aqui esse laço aqui embaixo ele vai ficar em espera ocupada ele vai verificar olha dentro daquela posição que eu tô procurando o r a é maior do que zero porque porque se o r a foi o maior do quiser fique preocupado Se eu é real for menor do que zero que pode ser tanto menos um quanto menos dois significa que eu posso colocar aqui então se o RH para o maior do quiser ele continuar procurando Dener mês se conhecermos

e onde é que sair desse laço aqui ele que significa aqui você sai do celular significado eu achei uma posição Onde eu posso colocar o elemento então ele paulopes transmissor location é igual aluno e depois ele faz lembra mais Note que a gente não tratando o caso em que o vetor todo está completo eu vou isso aqui faria com que ficasse em Loop Infinito eu vou assumir que isso não é um caso e que a pessoa colocou espaço de sobra no vetor interno é isso que a gente tem para tratamento de colisões a gente tratou

condições pelo menos logicamente utilizando a lista encadeada a gente tudo aqui Tem cadeado e esse teste de Neve e viu a implementação utilizando o teste de mesmo Espero que tenha ficado Claro caso não tenha ficado Claro recomendo assistir os vídeos novamente um forte abraço e a gente se vê nas próximas aulas e E aí [Música]