Hash FNV con python

Luis Peralta

Los hashes o resúmenes FNV (de Fowler / Noll / Vo) son útiles por varias razones:

  • Es muy rápido generarlos
  • El tamaño del hash es fácilmente manipulable
  • Se portan muy bien, es decir, producen pocas colisiones

Pues hoy necesitaba usarlos con mi querido Python y curiosamente nadie lo había implementado. Así que no me ha quedado más remedio que ponerme (no sé quién me ha dicho esta tarde que eso sería sólo un algoritmo , que no tendría complicación… en cuanto lo recuerde se va a acordar). Por si a alguien le viene bien:

    def FNV1a32(key):
        fnv_prime = long(0x1000193)
        hash = long(0x811C9DC5)
        for i in range(len(key)):
          hash ^= ord(key[i])
          hash += (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24)
        return (hash & 0x00000000ffffffffL)
    
    def FNV132(key):
        fnv_prime = long(0x1000193)
        hash = long(0x811C9DC5)
        for i in range(len(key)):
          hash += (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24)
          hash ^= ord(key[i])
        return (hash & 0x00000000ffffffffL)

La diferencia entre FNV132 y FNV1a32 es el orden en el que se hace la multiplicación. Y aquí sólo he puesto los métodos que calculan el hash de 32 bits, en la referencia de arriba tenéis cómo hacer para generarlos variables (escoger un buen primo inicial, fnv_prime, y un valor inicial del hash, hash, adecuados y quedarnos sólo con la parte del resultado que nos interese).