Tecnologia da informaçao

Cap´ ıtulo 7

“Hash” universal e perfeito
Neste cap´ ıtulo vamos estudar alguns aspectos importantes sobre os m´todos de “hash” e, em e especial o “hash” universal e “hash” perfeito. Os m´todos de “hash” s˜o de certo modo uma e a generaliza¸˜o dos algoritmos baseados na indexa¸˜o (ver a Sec¸˜o 5.1.2, p´gina 80) permitindo ca ca ca a tempo m´dio O(1) nas opera¸˜es de dicion´rio1 . Mais especificamente, pretende-se construir uma e co a fun¸˜o (de “hash”) que transforme elementos de um universo arbitr´rio em inteiros positivos ca a relativamente pequenos que indexem uma tabela – a tabela de “hash” – generalizando-se assim a opera¸˜o de indexa¸˜o. Com o m´todo tradicional de “hash” consegue-se obter tempos de ca ca e pesquisa, inser¸˜o e elimina¸˜o constantes (o que ´ excelente), mas apenas em termos do tempo ca ca e m´dio – n˜o no pior caso. e a Pr´-requesitos. Pressupomos que o leitor tem j´ um conhecimento gen´rico dos m´todos de e a e e “hash” e da sua eficiˆncia; neste cap´ e ıtulo vamos focar a nossa aten¸˜o em alguns t´picos mais ca o avan¸ados. c

7.1

Considera¸oes gerais sobre os m´todos de “hash” c˜ e

Nesta Sec¸˜o vamos rever alguns dos conceitos ligados aos m´todos de “hash”. ca e

7.1.1

Universos grandes, fun¸oes de “hash” c˜

Os dicion´rios s˜o uma das estruturas b´sicas utilizadas em programa¸˜o e a sua implementa¸˜o a a a ca ca eficiente ´ de importˆncia fundamental. Podemos considerar 2 tipos de dicion´rios: e a a – Dicion´rios est´ticos: dado um conjunto N de elementos, pretendemos represent´-los numa a a a
1 Neste

Cap´ ıtulo supomos que a fun¸ao de “hash” ´ calculada em tempo constante. c˜ e

T´picos Avan¸ados de Algoritmos – Armando B. Matos – DCC-FC-UP – 2009 o c

112

CAP´ ITULO 7.

“HASH” UNIVERSAL E PERFEITO

estrutura de informa¸˜o que permita uma procura eficiente. S˜o aplica¸˜es poss´ ca a co ıveis o dicion´rio das palavras reservadas de uma determinada linguagem de programa¸˜o e o dia ca cion´rio que cont´m as