Hash Bidimensional

Em ciência da computação, hashing é uma função que associa chaves a valores, isto é, se um objeto tem determinada chave (que o identifica), a função hashing recebe essa chave e retorna uma posição onde o objeto será alocado em um vetor. Uma característica importante de um hashing é que, por ser apenas uma função, ele realiza buscas apenas com essa função, tendo um custo amortizado constante para as operações que faz.

Expansão quadrática

Frequentemente, vê-se o hashing ser utilizado em vetores, estruturas unidimensionais de dados. De fato, muitos problemas podem ser resolvidos apenas com isso e outros usam isso como parte da solução, mas existem problemas que envolvem duas dimensões (ou mais) que não são triviais de se mapear para uma dimensão só.

Uma heurística muito conhecida de hashing é o hashing duplo (ou double hashing), que consiste em aplicar uma função inicial na chave e depois uma função auxiliar de saltos, para evitar colisões. A ideia é expandir de um vetor para uma matriz e acrescentar uma função para que, dada a chave, escolher a linha onde o elemento vai ser inserido.

É possível estender o hashing duplo para suportar mais uma dimensão, aumentando sua dispersibilidade, bem como suas aplicações.

Double Hashing

Como base para a expansão, alguns aspectos do Double Hashing devem ser definidos:

O tamanho do vetor é primo (vamos denotá-lo T).
A primeira função na chave k é o resto da divisão (inteira) de k por T.
A segunda função pode ser denotada por C − (k (mod C)), onde C é um primo menor que T.

Para resolver colisões, a segunda função é aplicada enquanto a posição atual (sendo olhada) não estiver livre.

Funções de espalhamento

As funções de espalhamento têm como característica principal a capacidade de gerar todos os valores entre 0 e T-1.

Uma função sem isso não deve ser usada para hashing no momento em que aumenta a probabilidade de ocorrência em uma região e anula a ocorrência em outra, dado que uma boa função de hash é aquela que consegue espalhar uniformemente os valores dentro do vetor.

A segunda função é de tratamento de colisões, então ela serve para dar saltos de um local com colisão para outro com boa probabilidade de não haver ninguém, por isso ela não precisa ser entre 0 e T-1, mas deve estar compreendida nesse intervalo.

Deve-se levar em conta essas características para montar uma boa função, além de observar o padrão das chaves que serão recebidas (pois, conhecendo as chaves, pode-se otimizar a função).

Uma função usada com frequência é a de módulo, por obviamente, para um vetor de tamanho T, a função $f(x)=x\ (mod\ T)$ pode retornar todos os valores entre 0 e T-1.

Construção

Seja $M$ uma matriz de dimensões $m\times n$ .

Para mapear uma chave a uma posição em uma matriz, pode-se seguir o seguinte procedimento:

Calcula-se a linha utilizando uma função $f_{1}$
Calcula-se a coluna utilizando duas funções $f_{2}$ e $f_{3}$

Inicialmente, deve-se calcular a linha. Sabe-se que a matriz tem $m$ linhas. Por simplicidade, pode-se adotar $f_{1}$ como $f_{1}(k)=k\ (mod\ m)$ . Apesar de simples, essa função é eficiente.

Da mesma forma, pode-se definir $f_{2}$ como $f_{2}(k)=k\ (mod\ n)$ , mas é notável que $f_{1}$ e $f_{2}$ retornariam o mesmo resultado para uma chave que fosse menor que $m$ e $n$ ou para uma matriz quadrada. Por segurança, toma-se duas precauções:

Evitar que $m$ e $n$ sejam iguais (pois se $m=n$ , $f_{1}=f_{2}$ )
Usar outro método para calcular o hash da chave

É preciso mudar o tipo de hashing, pois para um valor $k$ menor que $m$ e $n$ , teríamos $k\ (mod\ m)=k\ (mod\ n)=k$ .

Para redefinir $f_{1}$ , é possível utilizar o método de Horner, construído recursivamente da seguinte forma:

$f_{1}(k)={\begin{cases}1,&{\text{se }}k=0\\{\biggl (}f_{1}{\Bigl (}{\frac {k}{10}}{\Bigr )}\cdot P\ +k\ (mod\ 10){\biggr )}\ mod\ m,&{\text{se }}k>0\end{cases}}$

Onde P é um número primo (próximo de m)

Com isso, tem-se funções diferentes para o espalhamento. Abstraindo para qualquer m, n > 0:

$f_{1}(k,m)={\begin{cases}1,&{\text{se }}k=0\\{\biggl (}f_{1}{\Bigl (}{\frac {k}{10}}\ ,m{\Bigr )}\cdot P\ +k\ (mod\ 10){\biggr )}\ mod\ m,&{\text{se }}k>0\end{cases}}$

$f_{2}(k,n)=k\ (mod\ n)$

$f_{3}(k,n)=C-(k\ (mod\ C))$

Tendo em vista que, na última função, C é um número primo menor que n, não é necessário usar módulo em n, pois o valor retornado vai ser sempre menor que n. A presença de n na função deve-se ao fato de que é necessário tê-lo para encontrar um primo menor que ele.

Otimização

Com a montagem acima, a linha da inserção é definida e após isso, nunca é alterada, mas é possível fazer com que a posição olhada mude tanto na coluna quanto na linha (pois só a coluna é alterada).

Para isso, utiliza-se a função $f_{4}$ semelhante à $f_{3}$ , mas com um primo diferente.

Dado que a posição vista já está ocupada, o hashing vai ser capaz de ir procurar um lugar vazio em outra linha e coluna.

Essa abordagem evita alguns problemas como o primary e secondary clustering (agrupamentos que se formam quando o hash segue padrões mais simples de inserção e pioram a complexidade das operações).

Implementação

Eis uma implementação simples da estrutura em C++:

struct HashTable2D{

	int M[103][107];
	#define P 137
	#define C1 89
	#define C2 83

	HashTable2D(){memset(M, 0, sizeof(M));}

	int f1(int k){
		if(k == 0) return 1;
		return (f1(k/10) * P + k%10) % 103;
	}

	int f2(int k){
		return k % 107;
	}

	int f3(int k){
		return C1 - (k % C1);
	}

	int f4(int k){
		return C2 - (k % C2);
	}

	pair<int, int> inserir(int k){
		int linha = f1(k), coluna = f2(k);
		int saltoHorizontal = f3(k);
		int saltoVertical = f4(k);

		pair<int, int> inicio = make_pair(linha, coluna);

		while(M[linha][coluna] != 0){
			coluna = (coluna + saltoHorizontal) % 107;
			linha = (linha + saltoVertical) % 103;
			if(inicio == make_pair(linha, coluna)) return make_pair(-1, -1);
		}

		return make_pair(linha, coluna);
	}
};

Números primos

A questão dos números primos na construção das funções é crucial pelo fato de que, quando dois números a e b são primos entre si, é possível testar todas as casas de um vetor, sem repetir.

Por exemplo, sejam a = 7 e b = 8, a e b são primos entre si.

Se o tamanho do vetor for b, as casas testadas poderiam ser os múltiplos de 7 em módulo 8, isso é: 7, 14, 21, 28, 35, 42, 49 e 64 corresponderiam a 7, 6, 5, 4, 3, 2, 1 e 0.

Pode-se reparar que são todas casas diferentes, isso significa que se o tamanho do salto e o tamanho do vetor forem primos entre si, todas as casas vão ser testadas.

Dois números primos quaisquer sempre são primos entre si, então é mais prático usar vários números primos do que vários números compostos e testar se eles são primos entre si, dois a dois.

Abstração dimensional

Dado que os números primos e o método de Horner evitam o problema de funções de hash parecidas, é possível usá-los para criar novas funções capazes de abstrair a dimensão do hash e navegar por várias dimensões ao mesmo tempo.

Seja $M$ uma matriz de $n$ dimensões $m_{1}\times m_{2}\times \ ...\times \ m_{n}$ .

Seja $A$ um vetor de $n$ elementos $a_{1},\ a_{2},\ ...,\ a_{n}$ onde:

$\forall a_{i}\in A,\ a_{i}{\text{ é primo}}$
$\forall a_{i}\in A,\ a_{i}>m_{i}$
$\forall \ i,j\leq n\in \mathbb {N} ,\quad i\neq j\ \Rightarrow \ a_{i}\neq a_{j}$

Seja $B$ um vetor de $n$ elementos $b_{1},\ b_{2},\ ...,\ b_{n}$ , com as mesmas características de $A$ , exceto a segunda:

$\forall \ b_{i}\in B,\ b_{i}{\text{ é primo}}$
$\forall b_{i}\in B,\ b_{i}<m_{i}$
$\forall \ i,j\leq n\in \mathbb {N} ,\quad i\neq j\ \Rightarrow \ b_{i}\neq b_{j}$

Para inserir uma chave $k$ em $M$ , cria-se uma função $H$ que tenha disjunção quanto às posições que ela associa a chave em cada dimensão $m_{i}$ .

$H$ deve receber a chave e dimensão atual sendo vista, de forma que possa usar os primos de $A$ para aplicar o método de Horner.

$H(k,\ i)={\begin{cases}1,&{\text{se }}k=0\\{\biggl (}H{\Bigl (}{\frac {k}{10}},\ i{\Bigr )}\cdot a_{i}\ +k\ (mod\ 10){\biggr )}\ mod\ m_{i},&{\text{se }}k>0\end{cases}}$

Por último, o salto para cada dimensão $m_{i}$ pode ser calculado usando os elementos de $B$ .

$S(k,\ i)=b_{i}\ -\ (k\ \ (mod\ b_{i}))$

É importante mencionar que, quanto maior a dimensão, mais lenta será a inserção, pois o método de Horner não é constante: a cada passagem, ele realiza uma chamada recursiva da chave dividida por 10, até que ela seja em 0, levando a uma complexidade logarítmica.

A complexidade amortizada da inserção usando o método de Horner é $n\log(k_{\text{max}})$ onde:

$n$ é o número de dimensões
$\log$ é a função logarítmica na base 10
$k_{\text{max}}$ é a maior chave possível

Supondo que não se use esse método e se defina funções (sem chamadas recursivas ou iterações) para cada dimensão, a complexidade amortizada será $n$ .

No pior caso, a busca por um lugar vai passar por todas as casas da matriz, levando a uma complexidade de $(m_{1}\times m_{2}\times \ \dots \times \ m_{n})\log(k_{\text{max}})$ , que pode-se chamar de $n^{n}\log(n)$ , por simplicidade.

Essa complexidade é absurdamente grande, mas é necessário levar em conta que isso é muito raro de acontecer e que as operações só começam a ficar custosas depois de preencher aproximadamente ${\frac {3}{5}}$ das casas de $M$ .

Aplicação

O hash em 2D pode ser utilizado para a resolução de diversos problemas matemáticos, como por exemplo, encontrar uma ocorrência de uma palavra numa matriz de letras, encontrar o retângulo de área fixa com maior soma dentro de uma matriz de números, etc.

Pode-se utilizar contrações de uma matriz de hashes para gerar mensagens criptografadas. Após a inserção das informações na matriz, pode-se aplicar outras funções para transformar essa matriz numa string ou outro tipo de objeto de forma a contraí-lo.

Os hashes são intensamente utilizados em criptografia, a exemplo do SHA-2. Outros tipos de hash são utilizados para funções de autenticação de identidade, a exemplo da assinatura utilizada nos protocolos de Bitcoin. As funções utlizadas nesses protocolos são consideradas "perfeitas" pelo fato de que decifrar seus padrões ou existência de colisões é impossível na prática. Esses fatos não são verdades absolutas, mas são afirmações possíveis de assumir, já que quebrar a criptografia de tais funções levaria um tempo absurdamente grande e que há espaço suficiente para que não haja colisões.

Referências

http://faculty.cs.niu.edu/~freedman/340/340notes/340hash.htm

http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-23.html

http://www.cs.cmu.edu/afs/cs/academic/class/15210-f13/www/lectures/lecture24.pdf