e eu quero aluna seja bem-vindo a mais uma aula essa aula de agora que nós vamos fazer nós vamos tentar entender como funciona a tabela rest mais uma maneira um pouco mais prática sem tentar se importar tanto com os detalhes de implementação para isso eu vou utilizar essa ferramenta aqui essa ferramenta que você pode encontrar em CS. O STF se aponta o dedo para tio Gales/visualization/algoritmos. HTML com essa ferramenta nós podemos visualizar várias estruturas de dados aqui nós vamos visualizar agora essa closet hash tables Open addressing onde endereçamento aberto significa aquilo que nós vimos em
aula significa tentar tratar as colisões utilizando a própria estrutura do vetor eu vou clicar bem aqui Oi e o quê que nós temos aqui o que nós temos aqui um vetor interno aqui está o nosso vetor esse vetor ele tem 29 elementos e a gente tem a possibilidade de inserir remover ou encontrar os elementos estão e o que é que nós vamos utilizar aqui nós vamos utilizar esse linear podem onde linear krogs significa o nosso teste de Near então Lembrando que a gente viu utilizando o nome teste de Near significa basicamente linear problema do inglês
para o português então vamos logo inicialmente inserir aqui alguns elementos tão por exemplo eu vou inserir o elemento 38 eu vou colocar aqui 38 vou clicar em Surf para onde o elemento 38 foi o elemento 38 foi para a posição 9 porque o a a 38 foi para a posição 9 porque a gente fez uma divisão por exemplo 38 / 9/38 de opa 29 desculpa 38 / 29 que é o tamanho do Array então 38 / 29 é um tá e o 30 / 29 é o resto da divisão vai ser quanto vai ser 38
- 29 e 38 - 29 é nove Então esse quer dizer que o elemento 38 ele vai ser colocado na posição 9 vamos inserir aqui um um outro elemento ou inserir um elemento 55 vou dar um infarte aqui no elemento 55 e ele foi para posição 26 porque ele foi para a posição 20 cesto porque porque 55 / 29 é um tá e 55 - 29 Vai dar quanto vai ser 15 - 9 que vai dar 6 bom e depois 4 - 2 que vai 4 - 2 que vai dar dois então o resto da
divisão aqui é 26 então é por isso que eu lamento 55 foi colocado aqui na posição 26 vamos inserir um novo elemento aqui eu vou inserir um elemento 101 não inserts um elemento um pouquinho mais alto então 101 / 29 Vai dar quanto vai dar três tá tão três vezes 9:27 vai dois duas vezes três seis sete oito aqui então 87 então resto da divisão vai ser 101 - 87 então 11 - 7 Vai dar 4 e 9 que essa aqui vai virar 9:30 até já vira nove menos oito vai dar um então o resto
da divisão é catorze então o elemento 101 e foi colocado na posição 14 vamos inserir aqui mais algum elemento vencer elementos mais baixos por exemplo vai ser o elemento 12 o elemento 12 ele vai ficar Em qual posição Angra fica na posição 12 mesmo porque porque 12 a menor do que 29 se eu fizesse a mesma coisa colocaria 12 / 29 e vai dar zero tá porque porque o resto da divisão das Velhas então É como se eu colocasse 10 aqui já quiseram vezes 29 a 0 e 12 - 0 vai ser 12 E aí
eu vou colocar aqui uns números um pouquinho mais baixo só para não ter que ficar fazendo computando o resto da divisão vai ficar um pouco mais fácil a minha vida por exemplo eu posso colocar lamento 15 ó e vai ser colocado aqui na posição 15 eu vou colocar o elemento 43 vamos ver onde a posição do 43 vai ficar tá tão 43 vou ter que dividir 43 por 29 vai dar um e aqui eu vou colocar um 29 só para computar o resto então 13 - 9 vai dar quatro que vai ficar 33 - 2
vai dar um ou seja ele vai ser colocado na posição 14 e daí a gente veio a gente vai ver ela já tem um elemento já tem um elemento na posição 14 que é o 101 e aqui vai ter então a colisão então o que que a gente vai fazer olha no teste né a gente vai verificar eu não posso colocar esse elemento aqui então eu vou tentar colocar esse elemento ônibus na posição seguinte que seria o 15 mas o 15 já está ocupado Então hoje eu vou colocar no 16 bom então é isso que
a gente vai ver agora quando inserir o elemento 43 Então vou colocar o 43 aqui já tentou colocar no 14 e não conseguiu tentou 15 não conseguiu e agora de veio para essa posição aqui vamos fazer o seguinte agora vamos tentar remover o elemento 101 eu vou colocar aqui o 101 e vou remover esse elemento ficando aqui no de Elite e ele encontrou o elemento e o que que ele colocou aquele colocou essa Flag tá é para que serve essa Flag aqui essa Flag serve para gente continuar achando o elemento 43 lembrando o 43 ele
deveria ter sido colocado na posição 14 então quando eu for buscar o 43 eu vou procurar esse 43 na posição 14 e nesta posição 14 ele não vai estar lá então o que que vai acontecer se eu não tivesse colocado nada aqui se eu tivesse se eu tivesse simplesmente removido então nunca mais acharia um elemento 43 por quê Porque o elemento 43 ele foi colocado em outro canto foi colocado na posição 16 já que ele não conseguiu ficar na posição cantor então se eu não deixar uma Flag aqui eu vou acabar não encontrando mais o
elemento 43 essa Flag aqui serve para isso ela serve para dizer algo como disponível Ah tá então na aula teórica eu chamei isso daqui de disponível por quê Porque na hora de inserir a vou dizer eu posso inserir alguém aqui mas na hora de buscar eu vou ter que buscar aqui no 14 eu vou ter que buscar um 15 eu vou ter que buscar no 16 para ser capaz de encontrar o 43 Então vou colocar aqui 43 e vou clicar no funk eu procuro aqui procurou aqui Opa e ele achou o elemento 43 dizendo olha
43 ele foi encontrado na hora de inserir um novo elemento por exemplo alguns seria novamente o elemento 101 eu vou colocar aqui 101 ou dar uma em circos e percebo onde ele vai ser inserido ele vai ser inserido nessa posição aqui por quê Porque essa posição ela está disponível Então vou colocar em Santos a e agora ele veio aqui para essa posição Ah tá então espero que tenha ficado claro essa ideia aqui se eu quero colocar algum elemento e a posição dele está ocupada então eu tente nas posições seguimos tipo eu vou colocar aqui um
elemento 44 a TAP estão tendo que dividir por 2944 / 2019 vai dar um vou ter que descobrir qual é o resto da divisão do 44 por 29 então 14 - 9 vai dar 53 - 2 vai dar um aí ficou na posição 15 então ele viria para esta posição bem aqui eu vou colocar agora então esse esse elemento isso vai ter foco na posição 15 ele veio parar aqui na posição 17 porque ele não consigo ficar na posição 15 não conseguiu ficar na posição 16 então ele foi obrigado aqui a ficar na posição 17
e se eu remover por exemplo elemento 15 E aí o seu remover o elemento 15 eu tenho que deixar uma Flag aqui dizendo disponível deles porque porque se eu não deixar essa Flag então eu não vou mais conseguir achar o elemento 44 por quê Porque eu procurarei o 44 na posição 15 se estivesse vazio diria olhando se tá vazio na posição 15 a sinal de que existe ninguém que queira ficar nessa posição mas o 44 Tá ainda em algum lugar e ele tem que ser achar Então essa é a ideia tá pessoal do que a
gente viu na parte teórica Eu recomendo que você fique brincando aqui um pouquinho mais com essa ferramenta até você ficar acostumado aí com a teoria e acostumado a ver o vetor interno sendo preenchido o vetor interno sendo remover remover elementos e também dá um faz colocar um faz aqui no 44 ele procura na posição 15 depois na posição 16 e depois ele encontram 44 na posição em 17 se eu procurar agora o elemento por exemplo o elemento 16 ele vai procurar nessa posição aqui não vai encontrar ele vai procurar nessa posição aqui não vai encontrar
e daí ele vai verificar que essa posição aqui está vazia e vai parar a busca dizendo não encontrei o vou colocar que eu 16 procurou aqui aqui não encontrei por quê Porque eu 18 Aquele é nulo entende sabe que não precisa mais procurar então basicamente isso daqui significa vazio é isso daqui significa disponível na hora de inserir tanto faz se está vazio o disponível o algoritmo vai inserir tanto fazer vai ser ou no vazio ou no disponível mas na hora de fazer a busca o vazio disponível tem conceitos diferentes o vazio significa pare a busca
enquanto que disponível significa hora continue a buscar porque talvez quem você está procurando ainda esteja por aí E se você continuar e buscando talvez até você encontre E é isso que eu tinha pra dizer nessa aula Espero que tenha ficado claro essa parte de tabela hash um forte abraço e nos vemos nas próximas aulas
