4- Tablas Hash4.3 Funciones hash

Funciones Hash para claves strings

Método de la división

Dada una cadena c:
1. Sumar los valores ord(c[i]) para todo i
2. calcular el resto módulo maxTam

No funciona bien si maxTam es demasiado grande, por ejemplo si maxTam=10.007 y los strings tienen todos 8 ó menos caracteres, ¿qué ocurre?

Hay muchos otros casos en que da problemas, por ejemplo si maxTam=100 y las claves son 'A18', 'A27', 'A36', ..., 'A90'
 

Otros métodos

  • Calcular la suma ponderada de los valores ord(c[i]) para todo i, por ejemplo interpretando la cadena como si fuera un entero en base 256 (o menos, según el conjunto de caracteres usados).
      •  
      algoritmo h(c: in cadena[10]) return 0..maxTam-1;
      i,suma:entero;
      principio
        suma:=0;
        para i:=10 hasta 1 hacer
          suma:=(suma*256+ord(c[i])) mod maxTam;
        fpara
        devuelve(suma);
      fin.
 


  E.Mayordomo y K. Urzelai 
elvira at posta.unizar.es
karmelo at posta.unizar.es
Fecha de actualización: 3-9-01