FNV1A64 hash

 

Acerca de FNV1A64 hash

FNV-1a 64-bit (Fowler-Noll-Vo hash function, variante 1a) es una versión de la función de hash FNV-1a que genera un hash de 64 bits. Este algoritmo es conocido por su simplicidad y su buena distribución de hashes, lo que lo hace adecuado para diversas aplicaciones, como sistemas de archivos, tablas hash y bases de datos.

Características de FNV-1a 64-bit

  1. Longitud de salida:

    • Genera un hash de 64 bits (8 bytes).

  2. Constantes:

    • Offset basis: 0xCBF29CE484222325
    • Prime: 0x100000001B3

  3. Proceso de cálculo:

    • Inicializa el hash con el offset basis.
    • Para cada byte del dato de entrada, realiza una operación XOR con el byte del dato y luego multiplica el hash por el prime.
    • La operación es simple y rápida, adecuada para aplicaciones que requieren un hash rápido y efectivo.

Proceso de cálculo de FNV-1a 64-bit

  1. Inicialización:

    • Inicia con un valor de hash igual a 0xCBF29CE484222325.

  2. Iteración sobre cada byte del dato:

    • hash = hash XOR byte
    • hash = hash * 0x100000001B3

Ejemplo de implementación de FNV-1a 64-bit en Python

def fnv1a_64(input_string):
    # Constantes de FNV-1a 64-bit
    FNV_prime = 0x100000001B3
    offset_basis = 0xCBF29CE484222325

    # Convertimos la cadena a bytes
    input_bytes = input_string.encode('utf-8')

    # Inicializamos el hash
    hash_value = offset_basis

    # Calculamos el hash
    for byte in input_bytes:
        hash_value = hash_value ^ byte
        hash_value = hash_value * FNV_prime

    # Devolvemos el hash como un número hexadecimal
    return hash_value & 0xFFFFFFFFFFFFFFFF

# Ejemplo de uso
input_string = "Hola, Mundo!"
hash_result = fnv1a_64(input_string)
print(f"Hash FNV-1a 64-bit para '{input_string}': {hash_result:#018x}")

En este ejemplo, la cadena "Hola, Mundo!" se convierte en bytes y se calcula su hash FNV-1a 64-bit. El resultado se muestra en formato hexadecimal.

Ejemplo de implementación de FNV-1a 64-bit en C

#include <stdio.h>
#include <stdint.h>
#include <string.h>

uint64_t fnv1a_64(const char *input_string) {
    // Constantes de FNV-1a 64-bit
    const uint64_t FNV_prime = 0x100000001B3;
    const uint64_t offset_basis = 0xCBF29CE484222325;

    // Inicializamos el hash
    uint64_t hash_value = offset_basis;

    // Calculamos el hash
    for (size_t i = 0; i < strlen(input_string); i++) {
        hash_value ^= (uint8_t)input_string[i];
        hash_value *= FNV_prime;
    }

    // Devolvemos el hash
    return hash_value;
}

int main() {
    // Cadena de entrada
    const char *input_string = "Hola, Mundo!";

    // Calculamos el hash
    uint64_t hash_result = fnv1a_64(input_string);

    // Mostramos el hash en formato hexadecimal
    printf("Hash FNV-1a 64-bit para '%s': %016llx\n", input_string, hash_result);

    return 0;
}

En este ejemplo, la cadena "Hola, Mundo!" se utiliza para calcular el hash FNV-1a 64-bit. El resultado se muestra en formato hexadecimal.

Aplicaciones de FNV-1a 64-bit

  • Tablas hash: FNV-1a 64-bit se utiliza en implementaciones de tablas hash debido a su velocidad y buena distribución.
  • Sistemas de archivos: Se utiliza para la verificación rápida de nombres de archivos y rutas.
  • Bases de datos: Utilizado para generar claves hash para la indexación y búsqueda rápida.

Ventajas y desventajas de FNV-1a 64-bit

Ventajas:

  • Rapidez: FNV-1a 64-bit es rápido de calcular debido a su simplicidad.
  • Buena distribución: Proporciona una mejor distribución de hashes para una amplia variedad de datos de entrada en comparación con FNV-1.
  • Simplicidad: Fácil de implementar y entender.

Desventajas:

  • No criptográficamente seguro: FNV-1a 64-bit no está diseñado para ser resistente a ataques intencionales y no debe usarse para aplicaciones de seguridad.
  • Colisiones: Aunque es raro, es posible que dos cadenas diferentes generen el mismo hash FNV-1a 64-bit, lo que se conoce como colisión.

FNV-1a 64-bit es una opción popular y efectiva para aplicaciones que requieren un hash rápido y con buena distribución, pero debe utilizarse con precaución en contextos que requieren alta seguridad debido a su vulnerabilidad a colisiones y ataques intencionales.