b'\n_START_ARTICLE_\nHash Bidimensional\n_START_PARAGRAPH_\nEm ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, hashing \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o que associa chaves a valores, isto \xc3\xa9, se um objeto tem determinada chave (que o identifica), a fun\xc3\xa7\xc3\xa3o hashing recebe essa chave e retorna uma posi\xc3\xa7\xc3\xa3o onde o objeto ser\xc3\xa1 alocado em um vetor. Uma caracter\xc3\xadstica importante de um hashing \xc3\xa9 que, por ser apenas uma fun\xc3\xa7\xc3\xa3o, ele realiza buscas apenas com essa fun\xc3\xa7\xc3\xa3o, tendo um custo amortizado constante para as opera\xc3\xa7\xc3\xb5es que faz.\n_START_SECTION_\nExpans\xc3\xa3o quadr\xc3\xa1tica\n_START_PARAGRAPH_\nFrequentemente, v\xc3\xaa-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\xc3\xa7\xc3\xa3o, mas existem problemas que envolvem duas dimens\xc3\xb5es (ou mais) que n\xc3\xa3o s\xc3\xa3o triviais de se mapear para uma dimens\xc3\xa3o s\xc3\xb3._NEWLINE_Uma heur\xc3\xadstica muito conhecida de hashing \xc3\xa9 o hashing duplo (ou double hashing), que consiste em aplicar uma fun\xc3\xa7\xc3\xa3o inicial na chave e depois uma fun\xc3\xa7\xc3\xa3o auxiliar de saltos, para evitar colis\xc3\xb5es. A ideia \xc3\xa9 expandir de um vetor para uma matriz e acrescentar uma fun\xc3\xa7\xc3\xa3o para que, dada a chave, escolher a linha onde o elemento vai ser inserido._NEWLINE_\xc3\x89 poss\xc3\xadvel estender o hashing duplo para suportar mais uma dimens\xc3\xa3o, aumentando sua dispersibilidade, bem como suas aplica\xc3\xa7\xc3\xb5es.\n_START_SECTION_\nFun\xc3\xa7\xc3\xb5es de espalhamento\n_START_PARAGRAPH_\nAs fun\xc3\xa7\xc3\xb5es de espalhamento t\xc3\xaam como caracter\xc3\xadstica principal a capacidade de gerar todos os valores entre 0 e T-1._NEWLINE_Uma fun\xc3\xa7\xc3\xa3o sem isso n\xc3\xa3o deve ser usada para hashing no momento em que aumenta a probabilidade de ocorr\xc3\xaancia em uma regi\xc3\xa3o e anula a ocorr\xc3\xaancia em outra, dado que uma boa fun\xc3\xa7\xc3\xa3o de hash \xc3\xa9 aquela que consegue espalhar uniformemente os valores dentro do vetor._NEWLINE_A segunda fun\xc3\xa7\xc3\xa3o \xc3\xa9 de tratamento de colis\xc3\xb5es, ent\xc3\xa3o ela serve para dar saltos de um local com colis\xc3\xa3o para outro com boa probabilidade de n\xc3\xa3o haver ningu\xc3\xa9m, por isso ela n\xc3\xa3o precisa ser entre 0 e T-1, mas deve estar compreendida nesse intervalo._NEWLINE_Deve-se levar em conta essas caracter\xc3\xadsticas para montar uma boa fun\xc3\xa7\xc3\xa3o, al\xc3\xa9m de observar o padr\xc3\xa3o das chaves que ser\xc3\xa3o recebidas (pois, conhecendo as chaves, pode-se otimizar a fun\xc3\xa7\xc3\xa3o)._NEWLINE_Uma fun\xc3\xa7\xc3\xa3o usada com frequ\xc3\xaancia \xc3\xa9 a de m\xc3\xb3dulo, por obviamente, para um vetor de tamanho T, a fun\xc3\xa7\xc3\xa3o  pode retornar todos os valores entre 0 e T-1.\n_START_SECTION_\nOtimiza\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nCom a montagem acima, a linha da inser\xc3\xa7\xc3\xa3o \xc3\xa9 definida e ap\xc3\xb3s isso, nunca \xc3\xa9 alterada, mas \xc3\xa9 poss\xc3\xadvel fazer com que a posi\xc3\xa7\xc3\xa3o olhada mude tanto na coluna quanto na linha (pois s\xc3\xb3 a coluna \xc3\xa9 alterada)._NEWLINE_Para isso, utiliza-se a fun\xc3\xa7\xc3\xa3o  semelhante \xc3\xa0 , mas com um primo diferente._NEWLINE_Dado que a posi\xc3\xa7\xc3\xa3o vista j\xc3\xa1 est\xc3\xa1 ocupada, o hashing vai ser capaz de ir procurar um lugar vazio em outra linha e coluna._NEWLINE_Essa abordagem evita alguns problemas como o primary e secondary clustering (agrupamentos que se formam quando o hash segue padr\xc3\xb5es mais simples de inser\xc3\xa7\xc3\xa3o e pioram a complexidade das opera\xc3\xa7\xc3\xb5es).\n_START_SECTION_\nImplementa\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nEis uma implementa\xc3\xa7\xc3\xa3o simples da estrutura em C++:_NEWLINE_struct HashTable2D{_NEWLINE__NEWLINE_int M[103][107];_NEWLINE_#define P 137_NEWLINE_#define C1 89_NEWLINE_#define C2 83_NEWLINE__NEWLINE_HashTable2D(){memset(M, 0, sizeof(M));}_NEWLINE__NEWLINE_int f1(int k){_NEWLINE_if(k == 0) return 1;_NEWLINE_return (f1(k/10) * P + k%10) % 103;_NEWLINE_}_NEWLINE__NEWLINE_int f2(int k){_NEWLINE_return k % 107;_NEWLINE_}_NEWLINE__NEWLINE_int f3(int k){_NEWLINE_return C1 - (k % C1);_NEWLINE_}_NEWLINE__NEWLINE_int f4(int k){_NEWLINE_return C2 - (k % C2);_NEWLINE_}_NEWLINE__NEWLINE_pair<int, int> inserir(int k){_NEWLINE_int linha = f1(k), coluna = f2(k);_NEWLINE_int saltoHorizontal = f3(k);_NEWLINE_int saltoVertical = f4(k);_NEWLINE__NEWLINE_pair<int, int> inicio = make_pair(linha, coluna);_NEWLINE__NEWLINE_while(M[linha][coluna] != 0){_NEWLINE_coluna = (coluna + saltoHorizontal) % 107;_NEWLINE_linha = (linha + saltoVertical) % 103;_NEWLINE_if(inicio == make_pair(linha, coluna)) return make_pair(-1, -1);_NEWLINE_}_NEWLINE__NEWLINE_return make_pair(linha, coluna);_NEWLINE_}};\n_START_SECTION_\nN\xc3\xbameros primos\n_START_PARAGRAPH_\nA quest\xc3\xa3o dos n\xc3\xbameros primos na constru\xc3\xa7\xc3\xa3o das fun\xc3\xa7\xc3\xb5es \xc3\xa9 crucial pelo fato de que, quando dois n\xc3\xbameros a e b s\xc3\xa3o primos entre si, \xc3\xa9 poss\xc3\xadvel testar todas as casas de um vetor, sem repetir._NEWLINE_Por exemplo, sejam a = 7 e b = 8, a e b s\xc3\xa3o primos entre si._NEWLINE_Se o tamanho do vetor for b, as casas testadas poderiam ser os m\xc3\xbaltiplos de 7 em m\xc3\xb3dulo 8, isso \xc3\xa9: 7, 14, 21, 28, 35, 42, 49 e 64 corresponderiam a 7, 6, 5, 4, 3, 2, 1 e 0._NEWLINE_Pode-se reparar que s\xc3\xa3o todas casas diferentes, isso significa que se o tamanho do salto e o tamanho do vetor forem primos entre si, todas as casas v\xc3\xa3o ser testadas._NEWLINE_Dois n\xc3\xbameros primos quaisquer sempre s\xc3\xa3o primos entre si, ent\xc3\xa3o \xc3\xa9 mais pr\xc3\xa1tico usar v\xc3\xa1rios n\xc3\xbameros primos do que v\xc3\xa1rios n\xc3\xbameros compostos e testar se eles s\xc3\xa3o primos entre si, dois a dois.\n_START_SECTION_\nAplica\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nO hash em 2D pode ser utilizado para a resolu\xc3\xa7\xc3\xa3o de diversos problemas matem\xc3\xa1ticos, como por exemplo, encontrar uma ocorr\xc3\xaancia de uma palavra numa matriz de letras, encontrar o ret\xc3\xa2ngulo de \xc3\xa1rea fixa com maior soma dentro de uma matriz de n\xc3\xbameros, etc. _NEWLINE_Pode-se utilizar contra\xc3\xa7\xc3\xb5es de uma matriz de hashes para gerar mensagens criptografadas. Ap\xc3\xb3s a inser\xc3\xa7\xc3\xa3o das informa\xc3\xa7\xc3\xb5es na matriz, pode-se aplicar outras fun\xc3\xa7\xc3\xb5es para transformar essa matriz numa string ou outro tipo de objeto de forma a contra\xc3\xad-lo. _NEWLINE_Os hashes s\xc3\xa3o intensamente utilizados em criptografia, a exemplo do SHA-2. Outros tipos de hash s\xc3\xa3o utilizados para fun\xc3\xa7\xc3\xb5es de autentica\xc3\xa7\xc3\xa3o de identidade, a exemplo da assinatura utilizada nos protocolos de Bitcoin. As fun\xc3\xa7\xc3\xb5es utlizadas nesses protocolos s\xc3\xa3o consideradas "perfeitos" pelo fato de que decifrar seus padr\xc3\xb5es \xc3\xa9 imposs\xc3\xadvel e que nunca haver\xc3\xa1 colis\xc3\xa3o. Esses fatos n\xc3\xa3o s\xc3\xa3o verdades absolutas, mas s\xc3\xa3o coisas poss\xc3\xadveis de assumir, j\xc3\xa1 que quebrar a criptografia de uma fun\xc3\xa7\xc3\xa3o assim levaria um tempo absurdamente grande e que h\xc3\xa1 espa\xc3\xa7o suficiente para que n\xc3\xa3o haja colis\xc3\xb5es.'