Função Hash

A função hash é usada para mapear uma chave para um valor, gerando um código hash que, por sua vez, é usado para encontrar a localização de um item em uma estrutura de dados como uma tabela hash.

flowchart LR
 subgraph s1["🔑 Chaves"]
        A0["'maçã'"]
        B0["'uva'"]
        C0["'laranja'"]
        D0["'banana'"]
  end
 subgraph s2["⚙️ Função Hash"]
  end
 subgraph s3["📊 Tabela Hash"]
        A2["Índice 0: ❌      "]
        B2["Índice 1: 'laranja'"]
        C2["Índice 2: 'uva'"]
        D2["Índice 3: 'maçã'"]
        E2["Índice 4: 'banana'"]
  end
    A0 ==> s2
    B0 ==> s2
    C0 ==> s2
    D0 ==> s2
    s2 =="h('laranja')=1"==> B2
    s2 =="h('uva')=2"==> C2
    s2 =="h('maçã')=3"==> D2
    s2 =="h('banana')=4"==> E2

    classDef box fill:#fff,stroke:#000,color:#000,stroke-width:1px;
    
    class A0 box
    class B0 box
    class C0 box
    class D0 box
    class A2 box
    class B2 box
    class C2 box
    class D2 box
    class E2 box
    
    style s2 stroke:none,fill:#BBDEFB
    style s1 stroke:none,fill:#FFE0B2
    style s3 stroke:none,fill:#FFE0B2
    
    linkStyle 0 stroke:#D50000,fill:none
    linkStyle 1 stroke:#00C853,fill:none
    linkStyle 2 stroke:#2962FF,fill:none
    linkStyle 4 stroke:#2962FF
    linkStyle 5 stroke:#00C853,fill:none
    linkStyle 6 stroke:#D50000,fill:none

Características da Função Hash

É desejável que a função hash possua as seguintes características.

Fácil de ser calculada;
Distribuição uniforme dos dados;
Minimiza as colisões;
Capaz de resolver possíveis colisões.

A vantagem da tabela hash é a velocidade de busca, uma função muito complicada para calcular é incoveniente, pois pode demorar mais que uma busca em uma árvore binária, por exemplo. Além disso, se a função não distribui as chaves de maneira uniforme, muitas delas irão se concentrar em um local do vetor, aumentando a probabilidade de colisões.

Se liga! Quando muitas chaves se concentram um lugar, dizemos que se formou um cluster (aglomerado).

A seguir, vamos estudar os métodos clássicos para criação de funções hash.

Método da Divisão

No método da divisão, usamos o resultado do resto da divisão do valor da chave pelo tamanho da tabela. \[h(k) = k \bmod m\]

O ideal é que $m$ seja um número primo e não muito próximo de potências de $2$.

Por exemplo, se $k=12345$ e $m=101$, então \[h(k) = h(12345)= 12345 \bmod 101 = 23\]

A chave $12345$ deve ser alocada na posição $23$ do vetor de $101$ posições.

Se liga! Nem sempre trateremos com chaves inteiras simples como as vistas até aqui. Nesses casos, precisamos de um mecanismo para transformar em um valor inteiro antes de processar a função hash. Veremos isso à frente.

Este é o método mais simples e fácil de gerar um valor de hash. A função hash divide o valor $k$ (chave) por $m$ (tamanho da tabela) e, em seguida, usa o resto obtido. É mais adequado que $m$ seja um número primo, pois isso pode garantir que as chaves sejam distribuídas de forma mais uniforme.

Embora simples, o método da divisão leva a um desempenho ruim, uma vez que chaves consecutivas mapeiam para valores de hash consecutivos na tabela de hash.

Exercício

Dada a função hash $h(k) = k^2\bmod 7$, calcule os valores hash para as chaves \[4, 17, 13, 35, 25, 11, 2, 10, 32\].

Solução (clique para ver)

$h(4)\,\,\,=\,\,\,4^2\bmod 7=16\bmod 7\,\,\,\,\,\,=2$
$h(17)=17^2\bmod 7=289\bmod 7\,\,\,=2$
$h(13)=13^2\bmod 7=169\bmod 7\,\,\,=1$
$h(35)=35^2\bmod 7=1225\bmod 7=0$
$h(25)=25^2\bmod 7=625\bmod 7\,\,\,=2$
$h(11)=11^2\bmod 7=121\bmod 7\,\,\,=2$
$h(2)\,\,\,=\,\,\,2^2\bmod 7=4\bmod 7\,\,\,\,\,\,\,\,\,=4$
$h(10)=10^2\bmod 7=100\bmod 7\,\,\,=2$
$h(32)=32^2\bmod 7=1024\bmod 7=2$

Muitas colisões ocorreram! Era evidente que haveria sobreposição de chaves, pois temos somentes sete espaços.

Método da Multiplicação

No método da multiplicação, realizamos os seguintes passos:

Multiplicamos a chave ($k$) por uma constante $A$ entre $0$ e $1$;
Extraímos a parte fracionária de $kA$;
Multiplicamos esse valor por $m$ (tamanho da tabela);
Arredondamos para baixo;

Ou seja, \[h(k) = \lfloor m (kA \bmod 1) \rfloor, \text{ com } 0 < A < 1\]

Por exemplo, considere $k = 123$, $m = 1000$, e $A \approx 0,618$.

\[\begin{align*} h(k) &= \lfloor 1000 (123 \cdot 0,618 \bmod 1) \rfloor \\ &=\lfloor 1000 (76,014 \bmod 1) \rfloor \\ &=\lfloor 1000\cdot 0,014 \rfloor=14 \end{align*}\]

A vantagem deste método é que ele pode trabalhar com qualquer valor entre 0 e 1.

Se liga! O método de multiplicação é geralmente adequado quando o tamanho da tabela é uma potência de dois.

Exercício

Seja a chave $k = 12345$, a constante $A = 0,357840$ e o tamanho da tabela $m = 100$, calcule o valor hash usando o método da multiplicação.

Solução (clique para ver)

\[h(k) = \lfloor m (kA \bmod 1) \rfloor\] $h(12345) = \lfloor 100 (12345\cdot 0,357840 \bmod 1) \rfloor=\lfloor 100 (4417,5348 \bmod 1) \rfloor=\lfloor 100 (0,5348) \rfloor=\lfloor 53,48 \rfloor=53$

Hashing Universal

O hash universal tenta resolver o problema das colisões usando uma família de funções de hash, $\mathcal{H}$, que possui uma propriedade matemática crucial:

Para quaisquer duas chaves distintas, $k_1$ e $k_2$, a probabilidade de que a função de hash $h \in \mathcal{H}$ escolhida aleatoriamente cause uma colisão é no máximo igual à probabilidade de colisão aleatória, que é $1/m$, onde $m$ é o número de posições na tabela hash.

Uma das famílias universais mais usadas para chaves que são números inteiros e uma tabela de tamanho $m$ é definida da seguinte forma:

Seja $p$ um número primo maior que qualquer chave possível, e $m$ o tamanho da tabela hash. A família $\mathcal{H}$ é o conjunto de funções $h_{a,b}$ dadas pela fórmula: \[h_{a,b}(k) = ((ak + b) \bmod p) \bmod m\]

Onde $a$ e $b$ são parâmetros inteiros aleatórios escolhidos no início, com $a\in[1, p-1]$ e $b\in[0, p-1]$.

Os parâmetros aleatórios ajudam a dispersar o valor da chave. Já a operação de módulo por um primo $p$ ajuda a garantir que a distribuição do resultado seja uniforme no intervalo $[0, p-1]$. Finalmente, o resultado final é mapeado para o índice da tabela hash, no intervalo $[0, m-1]$.

Por exemplo, digamos uma tabela com $m=10$ slots e escolhamos $p=103$.

Sorteamos $a$ entre $1$ e $p-1$, ou seja, no intervalo $[1, 102]$
Sorteamos $b$ entre $0$ e $p-1$, ou seja, no intervalo $[0, 102]$

Digamos que $a=5$ e $b=13$, então nossa função sorteada da família universal será: \[h_{5,13}(k)=((5k+13)\bmod103)\bmod 10\]

Vamos calcular alguns valores de hash para fixação.

$h(4)\,\,\,=\,\,\,((5\cdot4+13)\bmod103)\bmod 10=\,\,\,(33\bmod103)\bmod 10=33 \bmod 10=3$
$h(17)=((5\cdot17+13)\bmod103)\bmod 10=\,\,\,(98\bmod103)\bmod 10= 98\bmod 10=8$
$h(25)=((5\cdot25+13)\bmod103)\bmod 10=(138\bmod103)\bmod 10=35\bmod 10=5$
$h(32)=((5\cdot32+13)\bmod103)\bmod 10=(173\bmod103)\bmod 10=70\bmod 10=0$

Mesmo com os melhores métodos, é impossível evitar colisões. Quando acontece, devemos tratá-la de modo que o desempenho da busca não seja muito afetado. No entanto, antes de estudarmos os tratamentos de colições, iremos abordar as estratégias para mapeamento de chaves em inteiros.

Estratégias para Mapeamento

Quando falamos em mapeamento de chaves em inteiros, estamos nos referindo a um pré-processamento que transforma uma chave (como uma string ou um número muito grande) em um inteiro mais adequado para ser usado por uma função de hash.

Embora seja possível criar suas próprias estratégias, apresentamos a seguir alguns métodos clássicos encontrados na literatura.

Chaves do tipo string

Os métodos clássicos para tratar strings usam o fato de cada letra ter um inteiro correspondente na tabela ASCII.

Soma

Muitas vezes, as chaves que estamos trabalhando são strings. Uma forma simples de convertê-las em inteiros é somar os valores ASCII de cada caractere: \[k=\sum_{i=0}^{n-1}s[i]=s[0]+s[1]+s[2]+\cdots+s[n-1]\]

onde $n$ é o tamanho da palavra.

Por exemplo, a palavra “PAI” (P = 80, A = 65 e I = 73): \[k=\sum_{i=0}^{3-1}s[i]=\sum_{i=0}^{2}s[i]=s[0]+s[1]+s[2]=80+65+73=218\]

Esse método é simples, mas apresenta má distribuição, ou seja, palavras com as mesmas letras em ordem diferente geram o mesmo valor.

Multiplicação Polinomial

Um método mais robusto é o da multiplicação polinomial. Aqui, tratamos a string como um número em uma base $\beta$ (geralmente um número primo pequeno): \[k=\sum_{i=0}^{n-1}s[i]\beta^{(n-1)-i}=s[0]\cdot\beta^{n-1}+s[1]\cdot\beta^{n-2}+\cdots+s[n-1]\cdot\beta^{0}\]

Por exemplo, a palavra “PAI” (P = 80, A = 65 e I = 73) e $\beta=13$: \[\begin{align*} k&=s[0]\cdot 13^{3-1}+s[1]\cdot 13^{3-2}+s[2]\cdot 13^{3-3}\\ &=80\cdot13^2+65\cdot13^1+73\cdot13^0\\ &=14438 \end{align*}\]

Se liga! A multiplicação por um número primo ajuda a espalhar os valores de forma mais uniforme do que se usássemos um número composto.

Essa técnica é superior à soma simples, pois considera a ordem dos caracteres. Para palavras como “cama” e “maca”, a soma simples irá retornar os mesmos valores, enquanto que a multiplicação polinomial não.

Exemplo simples:

$BA : 66\cdot13^1 + 65\cdot13^0 = 923$.
$AB : 65\cdot13^1 + 66\cdot13^0 = 911$.

Dessa forma, “BA” e “AB” produzem resultados distintos, evitando colisões triviais.

Chaves do tipo int grandes

Quando lidamos com inteiros muito grandes, precisamos reduzi-los para evitar estouro de capacidade (overflow) ou para encaixá-los em um intervalo menor. A seguir, apresentamos três métodos comuns: dobramento (folding), XOR e quadrado central (mid-square).

Dobramento (Folding)

Consiste em dividir a chave em partes menores e, em seguida, somá-las ou aplicar XOR entre elas para gerar um número reduzido. Por exemplo, suponha $k = 83.529.170$, vamos dividir a chave assim:

$k_1 = 835$
$k_2 = 291$
$k_3 = 70$

O dobramento por soma resulta em $k_1+k_2+k_3=835+291+70=1196$.

No dobramento por XOR, as partes são combinadas usando a operação lógica OU exclusivo (XOR), muito comum em funções de hash criptográficas. Primeiro, convertemos as partes para binário (aqui, usando 10 bits para simplificar):

Parte	Decimal	Binário (10 bits)
$k_1$	835	1101000011
$k_2$	291	0100100011
$k_3$	70	0001000110

Realizamos a operação XOR bit a bit entre as partes. \[k_1 \oplus k_2 \oplus k_3\]\[\begin{array}{r l l} & 1101000011 & (k_1) \\ \oplus & 0100100011 & (k_2) \\ \hline & 1001100000 & (k_1 \oplus k_2) \\ \oplus & 0001000110 & (k_3) \\ \hline & \mathbf{1000100110} & (\text{Resultado}) \end{array}\]

Transformando o resultado de volta para decimal: \[1000100110_2=512+64+8+4+2=590\]

O método XOR tende a preservar melhor as características de todas as partes da chave, ainda que seja um pouco mais complexo de implementar do que a soma simples.

Mid-Square

O método do quadrado central é uma técnica clássica de extração. A chave é elevada ao quadrado, e então o hash é formado pelos dígitos centrais do resultado. A quantidade de dígitos extraídos é indicada por $d$.

Apesar de ser simples, ele pode gerar um código hash razoavelmente bem distribuído. Como exemplo, considere uma $k=931$ e $d=3$. \[k^2=931^2=866761\] Assim, podemos selecionar $676$, ou até $667$.

Esses métodos apresentados podem ser combinados ou até mesmo utilizados como substitutos de uma função hash. Em sistemas mais complexos, essas abordagens costumam ser empregadas como etapas auxiliares dentro de funções de hash mais sofisticadas.

Nesta unidade, você aprendeu

✅ quais características uma função hash deve possuir

✅ metódos clássicos para definir funções hash

✅ como mapear palavras e grandes números em chaves

# O que é uma função hash? > Pense no papel dela dentro de uma tabela de dispersão. 1. [ ] Um algoritmo que ordena elementos de forma crescente. 1. [x] Uma função que transforma uma chave em um índice de armazenamento. 1. [ ] Uma técnica de compressão de dados. 1. [ ] Uma estrutura de dados hierárquica. # Quais são características desejáveis de uma boa função hash? > Elas influenciam diretamente na eficiência e distribuição das chaves. - [x] Ser fácil de calcular. - [x] Produzir distribuição uniforme dos dados. - [x] Minimizar colisões. - [ ] Depender de operações aleatórias complexas. # No método da divisão, qual das opções expressa corretamente a função hash? > Observe a operação usada para gerar o índice. 1. [x] $h(k) = k \bmod m$ 1. [ ] $h(k) = k / m$ 1. [ ] $h(k) = k^2 \bmod m$ 1. [ ] $h(k) = \sqrt{k} \bmod m$ # Por que é ideal escolher $m$ como um número primo no método da divisão? > Isso afeta a forma como os valores se espalham na tabela. 1. [x] Porque ajuda a distribuir as chaves de forma mais uniforme. 1. [ ] Porque facilita o cálculo de raízes quadradas. 1. [ ] Porque garante que não ocorram colisões. 1. [ ] Porque simplifica a implementação de XOR. # Considere $h(k) = k \bmod 101$. Qual o valor de $h(12345)$? > Aplique o operador módulo diretamente. 1. [ ] 12 1. [x] 22 1. [ ] 45 1. [ ] 99 # Quais são as etapas do método da multiplicação? > Relembre a ordem dos cálculos realizados. 1. Multiplicar a chave ($k$) por uma constante $A$ entre 0 e 1. 2. Extrair a parte fracionária de $kA$. 3. Multiplicar o resultado por $m$. 4. Arredondar para baixo. # No método da multiplicação, qual é uma vantagem importante? > Observe a observação sobre o tamanho da tabela. 1. [ ] É ideal quando $m$ é primo. 1. [x] É adequado quando o tamanho da tabela é uma potência de dois. 1. [ ] Garante ausência total de colisões. 1. [ ] Dispensa o uso do operador módulo. # O que caracteriza o hashing universal? > Está relacionado à escolha aleatória de funções. 1. [ ] Usa apenas o método da divisão. 1. [ ] Calcula o hash como a média de várias funções. 1. [x] Escolhe aleatoriamente uma função de uma família de funções que minimiza colisões. 1. [ ] Utiliza constantes irracionais para dispersão. # A fórmula do hashing universal $h_{a,b}(k)=((ak+b)\bmod p)\bmod m$ contém quais parâmetros aleatórios? > Eles são escolhidos no início do processo. - [x] $a$ - [x] $b$ - [ ] $p$ - [ ] $m$ # Quais são métodos clássicos para transformar _strings_ em inteiros? > Pense nos dois tipos mencionados no texto. - [x] Soma dos valores ASCII. - [x] Multiplicação polinomial. - [ ] Hashing universal. - [ ] Método da divisão. # Por que a multiplicação polinomial é superior à soma simples? > Compare o que cada método considera. 1. [x] Porque considera a ordem dos caracteres. 1. [ ] Porque ignora os valores ASCII. 1. [ ] Porque usa números compostos. 1. [ ] Porque sempre gera números primos. # Se $\beta = 13$, qual é o valor de $k$ para a palavra "BA"? > Use a fórmula da multiplicação polinomial. 1. [ ] 911 1. [x] 923 1. [ ] 1213 1. [ ] 1001 # No método de dobramento (folding), o que fazemos com a chave? > Veja como ela é reduzida. 1. [x] Dividimos em partes menores e as combinamos por soma ou XOR. 1. [ ] Multiplicamos por um número primo e aplicamos módulo. 1. [ ] Extraímos os dígitos centrais do quadrado da chave. 1. [ ] Aplicamos o logaritmo da chave. # No exemplo do método XOR, qual foi o resultado decimal final? > Observe a conversão final do número binário. 1. [ ] 512 1. [ ] 5900 1. [x] 590 1. [ ] 676 # O método do quadrado central (mid-square) consiste em: > Ele é simples, mas eficaz. 1. [ ] Somar as partes da chave. 1. [x] Elevar a chave ao quadrado e extrair os dígitos centrais. 1. [ ] Dividir a chave por um número primo. 1. [ ] Converter a chave em binário e aplicar XOR. # Quais métodos são indicados para mapear inteiros muito grandes? > Lembre dos três apresentados no texto. - [x] Dobramento (folding) - [x] XOR - [x] Quadrado central (mid-square) - [ ] Divisão inteira simples

De volta ao topo