Artigo realizado a partir da Aula 22 da disciplina PCD
08/11/2023
Publico
Insertion | Search | Deletion | |
---|---|---|---|
Vetor | O(1) | O(N) | O(1) |
Vetor Ordenado | O(N) | O(lg(N)) | O(N) |
Lista ligada | O(1) | O(N) | O(1) |
AVL | O(lg(N)) | O(lg(N)) | O(lg(N)) |
Hash | ? | ? | ? |
A função Hash recebe um valor e retorna um outro valor dentro de um Range
.
O problema é que segundo o principio da casa de pombos caso haja mais elementos do que espaços sempre haverá uma colisão
O ideal é que as funções hashes façam uma boa distribuição dos dados, o que reduz o número de colisões.
Sondagem linear: Caso haja uma colisão a função deverá olhar o elemento vizinho. hi(x) = (ui-1(x) + 1) % M
No pior caso a inserção e busca são lineares.
Faz uso de uma estrutura de dados em cada posição.
Exemplo:
0: 42
1:
2: 02
3: 51 -> 33
4:
5:
Após inserir as chaves 80, 6, 68, 53, 10 e 19
resulta em:
0: 42 -> 6
1: 19
2: 02 -> 80 -> 68
3: 51 -> 33
4: 10
5: 53
O tamanho de cada lista depende do número de colisões.
Assumindo que computar h(x)
é O(1)
, tem-se:
O(1)
(sem colisão)O(N)
(todas as chaves colidem na mesma posição)O(N/M)
. Note a redução
para O(log(N/M))
se usarmos AVL ao invés de lista!Considerando A ≤ si ≤ Z, pode-se fazer h(s) = (P(si − A))%M (note que si − A mapeia A para 0, B para 1, etc.).
Exemplo: Seja M = 7 e resolução de colisões por endereçamento fechado.
Como h(BOLA) = 5, h(V ENT O) = 1, etc., a inserção das chaves BOLA, VENTO, DADOS, CAIXA, XICARA, DOCE e MESA resulta em:
0:
1: VENTO -> XICARA
2: DOCE
3: DADOS
4:
5: BOLA -> CAIXA
6: MESA
A string também pode ser considerada um número inteiro positivo de base b = |Σ|
. Neste caso, tem-se h(s) = (X((si − A) × b
i))%M
.
Considerando b = 26
, tem-se que h(BOLA) = (1 × 260 + 14 × 261 + 11 × 262 + 0 × 263)%7 = (1 + 14 × 26 + 11 × 676 + 0 × 17576)%7 = 7801%7 = 3
.
Ao todo, tem-se:
0: XICARA -> DOCE
1:
2: DADOS
3: BOLA
4: VENTO -> CAIXA
5:
6: MESA
O custo
O(|s|)
para computar a função hash!
Não cai na prova
Hash de endereçamento fechado resolvida por outra hash. Forma uma árvore de tabelas hash: