Transformação de Chave Hashing - din.uem.br yandre/AEDEP/hashing-mini.pdf · colisões proporcionada…

  • Published on
    02-Feb-2019

  • View
    213

  • Download
    0

Embed Size (px)

Transcript

<p>1</p> <p>1</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>Transformao de Chave(Hashing)</p> <p>Prof. Yandre Maldonado e Gomes da Costayandre@din.uem.br</p> <p>UNIVERSIDADE ESTADUAL DE MARINGDEPARTAMENTO DE INFORMTICA</p> <p>2</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Transformaes de Chave, ou Tabela Hash, ou Tabelas de Disperso;</p> <p> Hashing: fazer picadinho, ou fazer uma baguna;</p> <p> Tcnica que objetiva organizar um conjunto de dados, caracterizados por uma chave, de forma que o acesso tenha o menor custo possvel;</p> <p> Em estruturas tradicionais (j estudadas), se os registros forem mantidos ordenados, algoritmos eficientes podem garantir busca um custo O(log n) ;</p> <p>3</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Tabelas hash, se bem projetadas, podem garantir buscas um custo constante O(1);</p> <p> Os registros armazenados em uma tabela so diretamente endereados a partir de uma transformao aritmtica sobre a chave de pesquisa;</p> <p> O preo pago por esta eficincia ser o uso maior de memria;</p> <p>2</p> <p>4</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Exemplo: Suponhamos um sistema acadmico que </p> <p>utiliza como chave o nmero de matrcula do aluno (RA) composto por 7 dgitos numricos;</p> <p> Para permitir a busca um registro de um aluno com um custo constante poderia ser utilizada a sua prpria matrcula como ndice de um vetor vet;</p> <p> Se isto fosse feito, poderamos acessar os dados do aluno cuja matrcula mat atravs de vet[mat];</p> <p>5</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Assim, o acesso ocorre em ordem constante, entretanto o custo de memria para manter esse acesso muito alto;</p> <p> Vamos considerar que o registro correspondente a cada aluno tenha a seguinte estrutura:</p> <p>struct Aluno{</p> <p>int mat;char nome [80];char email [30];char turma;</p> <p>};</p> <p>struct Aluno{</p> <p>int mat;char nome [80];char email [30];char turma;</p> <p>};</p> <p>6</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Considerando que o nmero de matrcula composto por 7 dgitos , ele poderia ser caracterizado por qualquer nmero entre 0 e 9.999.999;</p> <p> Assim, existe 10 milhes de possveis nmeros de matrcula;</p> <p> Para isto, seria necessrio um vetor com 10 milhes de elementos, que poderia ser estabelecido por:</p> <p>#define MAX 10000000</p> <p>Aluno vet[MAX];</p> <p>#define MAX 10000000</p> <p>Aluno vet[MAX];</p> <p>3</p> <p>7</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Dessa forma, o nome do aluno de matrcula mat acessado simplesmente atravs de vet[mat].nome ;</p> <p> Embora o acesso seja rpido o custo de memria proibitivo;</p> <p> Para a struct definida anteriormente teramos um gasto de 115 bytes de memria para cada aluno;</p> <p> Assim, o vetor descrito anteriormente consumiria 1.150.000.000 bytes , ou seja, acima de 1 Gbyte de memria;</p> <p>8</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Em uma situao prtica, seria comum encontrar um cadastro com algo em torno de 1.000 alunos , o que necessitaria de apenas 115 Kbytes de memria para armazenamento;</p> <p> Uma forma de resolver o problema do gasto excessivo de memria, garantindo um acesso rpido, atravs do uso de tabela hash;</p> <p>9</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Um mtodo de pesquisa atravs de hashing, constitudo de duas etapas principais: Computar o valor da funo de transformao </p> <p>(funo hashing), a qual transforma a chave de pesquisa em um endereo de tabela;</p> <p> Considerando que duas ou mais chaves podem ser transformadas em um mesmo endereo de tabela, necessrio existir um mtodo para lidar com colises ;</p> <p>4</p> <p>10</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Mesmo que o nmero de registros a serem armazenados seja muito menor do que o tamanho da tabela, qualquer que seja a funo de transformao, fatalmente ocorrero algumas colises ;</p> <p> Paradoxo do aniversrio (Feller, 1968):Em um grupo de 23 ou mais pessoas juntas ao acaso, a </p> <p>probabilidade de que 2 pessoas comemorem aniversrio no mesmo dia maior do que 50%.</p> <p>11</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Assim, em uma tabela com 365 endereos a probabilidade de coliso entre 23 chaves escolhidas aleatoriamente maior do que 50%;</p> <p> Alta probabilidade de colises, mesmo com distribuio uniforme;</p> <p> Exemplos: Armazenar registros cuja chave o RG de pessoas, </p> <p>com 7 dgitos numricos, em uma tabela com 10000 endereos;</p> <p> Armazenar registros cuja chave consiste de nomes compostos por at 16 letras (2616 chaves possveis) em uma tabela com 1000 endereos;</p> <p>12</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Funes de Transformao: Uma funo de transformao deve mapear </p> <p>chaves em inteiros dentro do intervalo [0..M-1], onde M o tamanho da tabela;</p> <p> A funo ideal aquela que: seja simples de ser computada; para cada chave de entrada, qualquer uma das </p> <p>sadas possveis igualmente provvel de ocorrer.</p> <p> Considerando que as transformaes sobre as chaves so aritmticas, se houverem chaves no numricas, elas devem ser transformadas em nmeros;</p> <p>5</p> <p>13</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Um dos mtodos que funciona muito bem para a transformao de chave, utiliza o resto da diviso por M:</p> <p>h(K) = K mod M Onde K um inteiro correspondente chave;</p> <p> Este um mtodo muito simples; Cuidado na escolha do valor de M:</p> <p> Se M par, ento h(K) par quando K par, e h(K) mpar quando K mpar;</p> <p> Assim, uma boa estratgia escolher um valor primo para M;</p> <p>14</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Um exemplo de funo em linguagem C:</p> <p>const n=10, M=7;typedef char TipoChave[n];</p> <p>int h(TipoChave Chave){int i, Soma=0;for (i=0; i</p> <p>6</p> <p>16</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Um estudo de caso: Armazenar dados de alunos utilizando como chave o </p> <p>RA; Alta probabilidade de colises , mesmo com </p> <p>distribuio uniforme; Identificando partes significativas da chave :</p> <p> Nmero de matrcula:</p> <p> Pode-se adotar uma parte da chave de acordo com o tamanho da tabela que se pretende utilizar;</p> <p>9 9 2 0 0 0 1</p> <p>Indicadores seqenciais</p> <p>Vestibular de ingresso</p> <p>Ano de ingresso</p> <p>17</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Para armazenar apenas dados de alunos pertencentes uma determinada turma: Considerando que:</p> <p> muitos alunos provavelmente ingressaram no mesmo ano; muitos alunos provavelmente ingressaram no mesmo </p> <p>vestibular; uma tabela de tamanho 100 seria suficiente para armazenar </p> <p>os dados dos alunos de uma turma;</p> <p> Poderiam ser tomados os dois ltimos dgitos dos indicadores seqenciais para compor a chave;</p> <p>9 9 2 0 0 0 1</p> <p>Indicadores seqenciais</p> <p>Vestibular de ingresso</p> <p>Ano de ingresso</p> <p>18</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Assim, a tabela poderia ser dada por:</p> <p> Neste caso, o acesso ao nome do aluno cujo nmero de matrcula mat seria dado por:</p> <p> A funo de busca que mapeia uma chave para um ndice da tabela poderia ser:</p> <p>Aluno* tab[100];Aluno* tab[100];</p> <p>vet[mat%100]-&gt;nome;vet[mat%100]-&gt;nome;</p> <p>int hash (int mat){</p> <p>return (mat%100);</p> <p>}</p> <p>int hash (int mat){</p> <p>return (mat%100);</p> <p>}</p> <p>7</p> <p>19</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> De forma geral, para uma tabela de tamanho N, a funo poderia ser dada por:</p> <p> Na prtica, costuma-se utilizar um nmero primo para estabelecer o tamanho da tabela;</p> <p> Para minimizar o nmero de colises, utiliza-se como regra emprica [Celes et al., 2004]: Evitar taxa de ocupao superior a 75%; Taxas em torno de 50%, em geral, trazem bons resultados; Taxas menores do que 25% podem representar gasto excessivo </p> <p>de memria;</p> <p>int hash (int mat){</p> <p>return (mat%N);}</p> <p>int hash (int mat){</p> <p>return (mat%N);}</p> <p>20</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Tratamento de colises: Vamos considerar um vetor de ponteiros, dado </p> <p>por:</p> <p> Uso da posio consecutiva livre : Os elementos que colidem so armazenados em </p> <p>posies da tabela ainda no ocupadas; Uma das estratgias consiste em buscar a prxima </p> <p>posio livre (utilizando incremento circular):</p> <p>#define N 127</p> <p>typedef Aluno* Hash[N];</p> <p>#define N 127</p> <p>typedef Aluno* Hash[N];</p> <p>| | | | | | | | | | | o | | | | | </p> <p>x h(x) busca por posio livre</p> <p>21</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Em uma busca, depois de mapeada a chave, procura-se a mesma no vetor at que ela ou uma posio vazia seja encontrada;</p> <p>Aluno* hsh_busca (Hash tab, int mat)</p> <p>{</p> <p>int h=hash(mat);</p> <p>while (tab[h] != NULL) {</p> <p>if (tab[h]-&gt;mat == mat)</p> <p>return tab[h];</p> <p>h=(h+1)%N;</p> <p>}</p> <p>return NULL;</p> <p>}</p> <p>Aluno* hsh_busca (Hash tab, int mat)</p> <p>{</p> <p>int h=hash(mat);</p> <p>while (tab[h] != NULL) {</p> <p>if (tab[h]-&gt;mat == mat)</p> <p>return tab[h];</p> <p>h=(h+1)%N;</p> <p>}</p> <p>return NULL;</p> <p>}</p> <p>8</p> <p>22</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Uma funo que insere ou modifica um elemento poderia ser dada por:</p> <p>Aluno* hsh_insere (Hash tab, int mat, char n[81], char e[41], char t){</p> <p>int h=hash(mat);while (tab[h] != NULL) {</p> <p>if (tab[h]-&gt;mat == mat)break;</p> <p>h=(h+1)%N;}if (tab[h]==NULL) { //no encontrou o elemento</p> <p>tab[h] = (Aluno*) malloc (sizeof (Aluno));tab[h]-&gt;mat = mat;</p> <p>}strcpy (tab[h]-&gt;nome, n); // atribui ou modifica i nformaostrcpy (tab[h]-&gt;email, e);tab[h]-&gt;turma = t;return tab[h];</p> <p>}</p> <p>Aluno* hsh_insere (Hash tab, int mat, char n[81], char e[41], char t){</p> <p>int h=hash(mat);while (tab[h] != NULL) {</p> <p>if (tab[h]-&gt;mat == mat)break;</p> <p>h=(h+1)%N;}if (tab[h]==NULL) { //no encontrou o elemento</p> <p>tab[h] = (Aluno*) malloc (sizeof (Aluno));tab[h]-&gt;mat = mat;</p> <p>}strcpy (tab[h]-&gt;nome, n); // atribui ou modifica i nformaostrcpy (tab[h]-&gt;email, e);tab[h]-&gt;turma = t;return tab[h];</p> <p>}</p> <p>23</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Uso de listas encadeadas : Estratgia diferente, consiste em fazer com que </p> <p>cada elemento da tabela hash represente um ponteiro para uma lista encadeada;</p> <p>| | | | | | | | | | | | | | | | </p> <p>x h(x)</p> <p>24</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Neste caso, a estrutura poderia ser dada por:</p> <p>struct Aluno {</p> <p>int mat;</p> <p>char nome [80];</p> <p>char email [30];</p> <p>char turma;</p> <p>sturct Aluno* prox;</p> <p>};</p> <p>struct Aluno {</p> <p>int mat;</p> <p>char nome [80];</p> <p>char email [30];</p> <p>char turma;</p> <p>sturct Aluno* prox;</p> <p>};</p> <p>9</p> <p>25</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> A operao de busca poderia ser descrita da seguinte forma:</p> <p>Aluno* hsh_busca (Hash tab, int mat)</p> <p>{</p> <p>int h = hash(mat);</p> <p>Aluno* a = tab[h];</p> <p>while (a != NULL) {</p> <p>if (a-&gt;mat == mat)</p> <p>return a;</p> <p>a = a-&gt;prox;</p> <p>}</p> <p>return NULL;</p> <p>}</p> <p>Aluno* hsh_busca (Hash tab, int mat)</p> <p>{</p> <p>int h = hash(mat);</p> <p>Aluno* a = tab[h];</p> <p>while (a != NULL) {</p> <p>if (a-&gt;mat == mat)</p> <p>return a;</p> <p>a = a-&gt;prox;</p> <p>}</p> <p>return NULL;</p> <p>}</p> <p>26</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Custo mdio de uma consulta [Ziviani, 2002]: Uso de posio consecutiva livre:</p> <p> Considerando um fator de carga dado por: =Q/N</p> <p> Onde Q a quantidade de elementos inseridos na estrutura e N o tamanho da tabela;</p> <p> O custo mdio dado por: Custo mdio = (1+1/(1- ))</p> <p> Lista encadeada: Custo mdio = (1+ )</p> <p> Onde =Q/N, e Q a quantidade de elementos inseridos na estrutura e N o tamanho da tabela;</p> <p> A constante 1 corresponde ao tempo gasto para clculo da funo hash;</p> <p>27</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Evoluo do custo mdio para posio consecutiva livre:</p> <p>Q N Custo10 100 1,0620 100 1,1325 100 1,1730 100 1,2140 100 1,3350 100 1,5060 100 1,7570 100 2,1775 100 2,5080 100 3,0090 100 5,5099 100 50,5012</p> <p>1110987654321</p> <p>Evoluo do custo</p> <p>0,00</p> <p>20,00</p> <p>40,00</p> <p>60,00</p> <p>1 3 5 7 9 11</p> <p>Carga</p> <p>Cus</p> <p>to</p> <p>Custo</p> <p>10</p> <p>28</p> <p>Prof. Y</p> <p>andre Maldonado</p> <p>TransformaTransforma o de Chave o de Chave -- HashingHashing</p> <p> Referncias Bibliogrficas: Celes, Waldemar et al. Introduo a </p> <p>Estruturas de Dados . Rio de Janeiro: Elsevier, 2004;</p> <p> Pereira, Silvio do Lago. Estruturas de Dados Fundamentais . So Paulo: rica, 1996;</p> <p> Wirth, Niklaus. Algoritmos e Estruturas de Dados . Rio de Janeiro: LTC, 1999;</p> <p> Ziviani, Nivio. Projeto de Algoritmos com implementaes em Pascal e C . So Paulo: Pioneira Thomson Learning, 2002;</p>