Recomendamos fortemente que se refira a postagem abaixo como um pré-requisito para isso. 
Hashing | Conjunto 1 (introdução) 

O que é colisão?  
Uma vez que uma função hash nos dá um pequeno número para uma chave que é um grande inteiro ou string, existe a possibilidade de que duas chaves resultem no mesmo valor. A situação em que uma chave recém-inserida mapeia para um slot já ocupado na tabela hash é chamada de colisão e deve ser tratada usando alguma técnica de tratamento de colisão. 
 

Quais são as chances de colisões com uma mesa grande?  
As colisões são muito prováveis, mesmo se tivermos uma mesa grande para armazenar as chaves. Uma observação importante é o Paradoxo do Aniversário . Com apenas 23 pessoas, a probabilidade de que duas pessoas façam aniversário no mesmo dia é de 50%. 

Como lidar com colisões?  
Existem basicamente dois métodos para lidar com a colisão: 
1) Encadeamento separado 
2) Endereçamento aberto 
Neste artigo, apenas o encadeamento separado é discutido. Estaremos discutindo o endereçamento aberto no próximo post. 

Encadeamento separado: 
A ideia é fazer com que cada célula da tabela de hash aponte para uma lista vinculada de registros que têm o mesmo valor de função de hash. 

Vamos considerar uma função hash simples como " mod de tecla 7 " e sequência de teclas como 50, 700, 76, 85, 92, 73, 101. 
 

Programa C++ para hash com encadeamento 

Vantagens: 
1) Simples de implementar. 
2) A tabela de hash nunca fica cheia, podemos sempre adicionar mais elementos à cadeia. 
3) Menos sensível à função hash ou fatores de carga. 
4) É mais usado quando não se sabe quantas e com que frequência as chaves podem ser inseridas ou excluídas. 

Desvantagens: 
1) O desempenho do cache de encadeamento não é bom porque as chaves são armazenadas usando uma lista vinculada. O endereçamento aberto fornece melhor desempenho do cache, pois tudo é armazenado na mesma tabela. 
2) Perda de espaço (algumas partes da tabela de hash nunca são usadas) 
3) Se a cadeia ficar longa, o tempo de pesquisa pode se tornar O (n) no pior caso. 
4) Usa espaço extra para links. 

Desempenho do encadeamento: O 
desempenho do hashing pode ser avaliado sob a suposição de que cada chave tem a mesma probabilidade de ser hash para qualquer slot da tabela (hashing uniforme simples).  

 m = Number of slots in hash table
 n = Number of keys to be inserted in hash table
 
 Load factor α = n/m 
  
 Expected time to search = O(1 + α)
 
 Expected time to delete = O(1 + α)

Time to insert = O(1)

 Time complexity of search insert and delete is 
 O(1) if  α is O(1)

Estruturas de dados para armazenamento de cadeias: 

• Listas vinculadas
  • Pesquisa: O (l) onde l = comprimento da lista encadeada
  • Excluir: O (l)
  • Inserção: O (l)
  • Não compatível com cache
• Arrayes de tamanho dinâmico (vetores em C++, ArrayList em Java, lista em Python)
  • Pesquisa: O (l) onde l = comprimento da array
  • Excluir: O (l)
  • Inserção: O (l)
  • Compatível com cache
• BST de auto-equilíbrio (árvores AVL, árvores vermelhas e pretas)
  • Pesquisa: O (log (l))
  • Excluir: O (log (l))
  • Inserção: O (l)
  • Não compatível com cache
  • Java 8 em diante usam isso para HashMap

<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="374" src="https://www.youtube.com/embed/_xA8UvfOGgU?feature=oembed" width="665"></iframe>

Próxima postagem:  
Endereçamento aberto para tratamento de colisão 

Referências:  
http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf 
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.