Funció hash

Archiu:Hash table 4 1 1 0 0 0 0 LL.svg

Funció hash

Archiu:Hash function2-es.svg

Una funció de hash en funcionament.

Una funció resumixen, en anglés hash function, també coneguda en els híbrits funció hash o funció de hash, convertix un o varis elements d'entrada a una funció en un atre element. També li les coneix com a funció extracte, de l'anglés digest function, funció de extractado i per l'híbrit funció digest.

Una funció hash H és una funció computable per mig d'un algoritme tal que:

$H:U\to M$

$x\to h(x)$

La funció hash té com a entrada un conjunt d'elements, que solen ser cadenes, i els convertix en un ranc d'eixida finito, normalment cadenes de llongitut fixa. És dir, la funció actua com una proyecció del conjunt O sobre el conjunt M.

Cal tindre en conte que M pot ser un conjunt definit de sancers. En este cas, podem considerar que la llongitut és fixa si el conjunt és un ranc de números de sancers, ya que podem considerar que la llongitut fixa és la del número en major cantitat de sifres. cal destacar que és possible convertir tots els números a una cantitat específica de sifres simplement anteponent zeros.

Normalment el conjunt O té un número elevat d'elements i M és un conjunt de cadenes en un número acotat de símbols. L'idea bàsica d'un valor hash és que servixca com una representació compacta de la cadena de l'entrada. Per esta raó, es diu que estes funcions permeten resumir senyes del conjunt domini.

Orígens del terme

El terme hash prové, aparentment, de l'analogia en el significat estàndar (en anglés) de dita paraula en el món real: «picar i mesclar». Donald Knuth creu que H. P. Luhn, amprat d'IBM, va anar el primer en utilisar el concepte en un memoràndum datat en giner de 1953, encara que la seua utilisació massiva no es va produir fins al cap de 10 anys.

Terminologia associada

• Al conjunt O se li crida domini de la funció hash. A un element d'O se li crida preimagen o, depenent del context, clau o mensage.
• Al conjunt M se li crida image de la funció hash. A un element de M se li crida valor resumixen, còdic hash o simplement hash.

Es diu que es produïx una colisió quan dos entrades distintes de la funció resumixen produïxen la mateixa eixida. De la definició de funció resumixen podem dir que O, el domini de la funció, pot tindre infinits elements. No obstant M, el ranc de la funció, té un número finito d'elements degut a que el tamany de les seues cadenes és fix. Per tant la possibilitat d'existència de colisions és intrínseca a la definició de funció hash. Una bona funció resumixen és una que té poques colisions en el conjunt esperat d'entrada. És dir, es desija que la provabilitat de colisió siga molt baixa.

Vore també

• Funció hash criptográfica
• Còdic de detecció de modificacions
• Còdic d'autenticació de mensages