Olá pessoal!

Vamos rever os conceitos estudados, seguindo a playlist do prof Marcos Kutova, disponível no youtube.

Função de espalhamento (Função Hash)

Observe:

fun espalha(self, chave):
   para cada letra da chave: 
      posicao += identifique a ordem da letra no alfabeto
   return posicao

Por exemplo:

posicao = espalha(“abc”) # a = 1 b = 2 c = 3 # 1 + 2 + 3 # return posicao = 6

posicao = espalha(“cba”) #  c = 3 b = 2 a = 1 # 3 + 2 + 1 # return posicao = 6

posicao = espalha(“bca”) #  b = 2 c = 3 a = 1 # 2 + 3 + 1 # return posicao = 6Note que são 3 chaves diferentes “abc”, “cba” e “bca” porém todas retornaram a mesma posição.
Claaaro que as funções não são assim tão simples, mas você terá colisões mesmo assim. Quanto menos melhor! Mas uma ou 8 milhões, não importa, precisa ser tratada!

Ps: Outro exemplo simples e legal é esse algoritmo aqui, criado pelo Gabriel Porto em um exercício relacionado. Execute-o, troque as tartarugas, tente diferentes chaves. 
https://colab.research.google.com/drive/1yuSaYvk06dYGK-7XH0gvbdaHcnOrI-Nc?usp=sharing 
Observe que existe um parâmetro chamado tableSize. Qual é a importância de manter esse parâmetro?

Como resolver? O problema das chaves que vão para mesma posição?

Colisões 

encadeamento interno

encadeamento externo

buckets

Ai quanto processamento para reposicionar todo mundo na colisão do bucket!!! E se… fosse dinâmico, como seria?

Já que estamos aqui, vamos dar uma espiada no que o prof Marcos Kutova fala sobre os índices invertidos?