FNV132 hash

 

Acerca de FNV132 hash

FNV-1 32-bit (Fowler–Noll–Vo hash function) es un algoritmo de hash no criptográfico diseñado para ser rápido y proporcionar una buena distribución de hash. Es parte de una familia de funciones de hash que incluyen FNV-1 y FNV-1a, con variaciones en el tamaño del hash (32-bit, 64-bit, 128-bit, etc.). La versión FNV-1 32-bit produce un hash de 32 bits y es utilizada en aplicaciones como sistemas de archivos, bases de datos y tablas hash.

Características de FNV-1 32-bit

  1. Longitud de salida:

    • Genera un hash de 32 bits (4 bytes).

  2. Constantes:

    • Offset basis: 0x811C9DC5
    • Prime: 0x01000193

  3. Proceso de cálculo:

    • Inicializa el hash con el offset basis.
    • Para cada byte del dato de entrada, multiplica el hash por el prime y luego realiza una operación XOR con el byte del dato.
    • 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-1 32-bit

  1. Inicialización:

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

  2. Iteración sobre cada byte del dato:

    • hash = hash * 0x01000193
    • hash = hash XOR byte

Ejemplo de implementación de FNV-1 32-bit en Python

def fnv1_32(input_string):
    # Constantes de FNV-1 32-bit
    FNV_prime = 0x01000193
    offset_basis = 0x811C9DC5

    # 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 * FNV_prime
        hash_value = hash_value ^ byte

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

# Ejemplo de uso
input_string = "Hola, Mundo!"
hash_result = fnv1_32(input_string)
print(f"Hash FNV-1 32-bit para '{input_string}': {hash_result:#010x}")

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

Ejemplo de implementación de FNV-1 32-bit en C

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

uint32_t fnv1_32(const char *input_string) {
    // Constantes de FNV-1 32-bit
    const uint32_t FNV_prime = 0x01000193;
    const uint32_t offset_basis = 0x811C9DC5;

    // Inicializamos el hash
    uint32_t hash_value = offset_basis;

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

    // Devolvemos el hash
    return hash_value;
}

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

    // Calculamos el hash
    uint32_t hash_result = fnv1_32(input_string);

    // Mostramos el hash en formato hexadecimal
    printf("Hash FNV-1 32-bit para '%s': %08x\n", input_string, hash_result);

    return 0;
}

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

Aplicaciones de FNV-1 32-bit

  • Tablas hash: FNV-1 32-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-1 32-bit

Ventajas:

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

Desventajas:

  • No criptográficamente seguro: FNV-1 32-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-1 32-bit, lo que se conoce como colisión.

FNV-1 32-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.