Hash Table

Hash Table (Tabela de Dispersão) é uma estrutura de dados que associa objetos a posições no array através da chave dos objetos, de maneira rápida.

 Uma HT tem:
• Um array T de tamanho M para guardar valores;
• Uma função H que associa chaves a posições (H se chama hash, função de dispersão ou função de espalhamento).

 Cada objeto tem um valor v e uma chave k, na qual aplicamos a função H(k) para obter o índice no array onde v vai ser inserido.

 Quando vamos usar HTs, devemos levar em conta que o número de objetos a serem adicionados vai ser maior do que o tamanho do array, então obviamente alguns valores vão tentar ocupar os mesmos índices que outros.

 Sejam $k_1$ e $k_2$ chaves.
Vamos adicioná-las na tabela.

 $H(k_1) = i$
Logo $T[i] = k_1$.

 Se
$H(k_2) = i$
e
$T[i]$ já está ocupado
Dizemos que ocorreu uma colisão.

 Os melhores hashes são aqueles que conseguem mapear as chaves às posições com o menor número possível de colisões.

 Por exemplo:
Se as chaves são valores entre 100 e 199
Se H(k) = primeiro algarismo de k

 Então H é uma função péssima, pois entre 100 e 199, todos valores começam pelo mesmo algarismo, então para todo k, H(k) seria igual, logo a HT tentaria colocar todos os elementos na mesma posição. 

 A parte mais interessante das HTs é encontrar uma função H eficiente.

 Existem inúmeras heurísticas para tratar colisões, tais como:

SEPARATE CHAINING
É quando cada casa do array é uma lista encadeada de elementos, ou seja, T[i] é a i-ésima lista.
Quando um elemento vai ser adicionado, calculamos H(k) e inserimos o elemento no final da H(k)-ésima lista.
Essa abordagem nos dá uma inserção em O(1), mas ela só seria ótima se, para um número N de elementos e um array com M posições, o tamanho de cada uma das M listas fosse N/M (ou seja, se os elementos estivessem uniformemente distribuídos entre todas as listas).
Para que isso ocorresse, dependeríamos da eficácia de H.
Se H fosse péssimo, por exemplo, todos os elementos iriam para a mesma lista, e uma busca, no pior caso, seria percorrer a lista inteira, levando a complexidade a O(n).
LINEAR PROBING

Após calcular H(k) e perceber que há colisão, faz-se uma sondagem sistemática para saber onde o valor vai ser inserido.
Nos casos mais simples, caso ocorra colisão, seguimos procurando linearmente no array até achar uma posição vazia para colocar o valor.
Por exemplo, se vamos adicionar um valor na casa 3, mas ela já está ocupada, tentamos na casa 4, se já estiver ocupada, na 5, e assim sucessivamente, até acharmos uma posição vazia.
Isso é ruim pelo fato de não ser eficiente e de causar um problema chamado cluster, que nada mais é do que acúmulo de valores em determinada região. Quando se tem, por exemplo, 10 valores adjacentes nas casas $[i .. i + 9]$ do array, a probabilidade de que o próximo valor vai ser adicionado ser na casa $i + 10$ aumenta, pois em qualquer casa entre $i$ e $i + 9$ que ele cair, ele irá para $i+10$, e assim aumentando o acúmulo e diminuindo a probabilidade de uma distribuição uniforme dos valores.
Possíveis alternativas para essa abordagem são:

Sondagem Quadrática:

           Definimos nosso H de forma diferente:

           $H(k, i) = (h'(k) + c_1i + c_2i^2)$ $mod$ $M$, onde:

           • $h'$ é uma função de hashing auxiliar;
           • $c_1$ e $c_2$ são constantes maiores que 0
           • $i$ é a posição da sondagem.
           • inicialmente, chamamos H(k, 0)
           • uma função simples para h' é h'(k) = k mod M

           $H(k, i)$ {
                       $i = h'(k) + c_1i + c_2i^2$
                       $i = i$ $mod$ $M$
                       se $T[i]$ está vazio, retorna $i$
                       retorna $H(k, i)$
            }
De maneira análoga, podemos lidar com o $i$ de outras formas para gerar as posições, mas não temos como garantir que $H(k, i)$ vai encontrar uma casa vazia.
Essa alternativa evita o cluster linear, mas gera cluster quadrático, que forma agrupamentos menores e separados, ao invés de agrupamentos maiores únicos.

 Há também a Sondagem Pseudo-Aleatória, mas não vou estar tratando ela.
Existem outras heurísticas, como o Método da Dobra, Método da Divisão, Método da Multiplicação, Cuckoo Hashing, etc.
DOUBLE HASHING

Uma boa solução é usar uma segunda função de hash para tratar as colisões.
A ideia é que, ao haver colisão, seja aplicada uma segunda função de hash que vai funcionar dependendo do valor da chave.
• Vamos mudar o tamanho de T para o primo mais próximo de M (exe: se M é 14, mudamos para 13)
• Ambos os hashes devem ser capazes de retornar todos os valores entre 0 e M-1
• Funções comuns para o primeiro hashing:
$h_1(k) = k$ $mod$ $M$
• Funções comuns para o segundo hashing:
$h_2(k) = C - (k$ $mod$ $C)$, onde C é o primeiro número primo menor que M)
$h_2(k) = 1 + ( (k/M)$ $mod$ $(M-1) )$

 O valor de M deve ser primo pelo fato de que, ao aplicarmos os hashes, o valor será menor que M e nunca irá dividi-lo, fazendo com que índices diferentes sejam checados.

 A função é assim:
$H(k)$ {
          $i = h_1(k)$
          pulo = $h_2(k)$
          enquanto $T[i]$ não for vazia:
                  $i = (i + pulo)$ $mod$ $M$
          retorna $i$
}

 Eventualmente, devemos checar se ainda há posições vazias no array, senão o loop pode ser infinito.

 

struct HashTable{
    #define M 13
    #define C 11
    int T[M];

    HashTable(){memset(T, 0, sizeof(T));}

    int h1(int k){return k % M;}
    int h2(int k){return C - (k % C);}

    int H(int k){
        int posicao = h1(k), pulo = h2(k);
        int inicio = posicao;
        while(T[posicao] != 0){
            posicao = (posicao + pulo) % M;
            if(posicao == inicio) return -1;
        }
        return posicao;
    }

    void add(int k){
        int posicao = H(k);
        if(posicao == -1) printf("Hash cheio\n");
        else{
            T[posicao] = k;
            print();
        }
    }

    void print(){
        for(int i = 0; i < 13; i++) printf("%.3d ", T[i]);
        printf("\n");
    }

};

int main(){
    HashTable H;
    H.add(4);
    H.add(28);
    H.add(15);
    H.add(133);
    H.add(800);
    H.add(74);
    H.add(99);
    H.add(51);
    H.add(3);
    H.add(88);
    H.add(57);
    H.add(66);
    H.add(7);
    H.add(16);
}



 Complexidade da Inserção: O(1)  
 Complexidade no Pior Caso: O(n)

As buscas e remoções têm a mesma complexidade, no entanto nem todos os hashes são iguais, por exemplo: o cuckoo hashing tem busca O(1) garantida.

 As HTs tem inúmeras aplicações, como na criptografia e nos bitcoins, a exemplo dos hashes criptográficos SHA (Secure Hash Algorithm), como o SHA-2, SHA-512, etc.

 Esses hashes criptográficos são considerados "livres de colisão" e "secretos", isto é, H(x) = H(y) se e somente se x = y, e dado H(x), é impossível calcular x. Essas considerações se dão pelo fato de que levaria uma eternidade para encontrar uma colisão ou desencriptar o H(x) desses hashes.

 Outra aplicação está no algoritmo Rabin-Karp, que utiliza hashing para achar um padrão (substring) numa string.

Em C++ a partir do 11, as Hash Tables tem implementação pronta, unordered_map.



Nenhum comentário:

Postar um comentário

Assinar: Postagens (Atom)