Concepto de función hash

5.1 Definición de función hash y su aplicación

Función hash — es una función que toma datos de entrada (o clave) y devuelve un tamaño fijo de bits, usualmente llamado hash o valor hash. El propósito principal de la función hash es distribuir eficientemente los datos en una tabla hash para asegurar un acceso rápido a los elementos.

Aplicación:

• Tablas hash: Se utilizan para implementar arrays asociativos (diccionarios en Python), proporcionando acceso rápido a los datos por clave.
• Control de integridad de datos: Las funciones hash se utilizan para verificar la integridad de archivos y datos (por ejemplo, algoritmos MD5, SHA-1, SHA-256).
• Criptografía: Las funciones hash se usan en algoritmos criptográficos para el cifrado y la creación de firmas digitales.
• Motores de búsqueda: Se utilizan para la indexación de datos y búsqueda rápida de información.
• Gestión de caché: Se utilizan para organizar cachés, para encontrar datos rápidamente.

Ejemplo de aplicación de una función hash en Python:

# Ejemplo de uso de una función hash en Python para una tabla hash (diccionario)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Obtener valor hash de la clave
key = "banana"
hash_value = hash(key)

print(f"Valor hash para la clave '{key}': {hash_value}")

5.2 Analogías de la vida real

Con una función hash se puede dividir un gran grupo de objetos en grupos aproximadamente iguales. Además, si sigues agregando nuevos objetos, estos continuarán distribuyéndose uniformemente entre los grupos.

Supongamos que tienes 1000 personas y necesitas distribuirlas en 30 grupos. Así es como se podría hacer.

Método 1. Por la primera letra del nombre.

El primer grupo es para todos los que tienen un nombre que comienza con "A", el segundo grupo para los de "B", y así sucesivamente. La regla "Tu grupo es la primera letra de tu nombre" es una función hash. Pero con esta función hash, corremos el riesgo de tener muchas personas en el grupo "A" y pocas en la "Z".

Método 2. Por la fecha de nacimiento.

Si naciste el primer día de cualquier mes, perteneces al primer grupo, si es el segundo día, al segundo, y así sucesivamente. Habrá 31 grupos. En el grupo 31 habrá alrededor de la mitad de personas que en los demás, pero las personas estarán distribuidas de manera mucho más uniforme que en el primer caso.

Método 3. Número de teléfono

La opción ideal es obtener un número que, por un lado, sea lo más aleatorio posible (así los números estarán distribuidos uniformemente), y por otro lado, siempre debe calcularse rápidamente y ser siempre el mismo.

Vamos a tomar los últimos 4 dígitos del número de teléfono - esto será 10,000 opciones. Luego dividimos este número por 30. Entonces tendremos 30 posibles restos de la división: 0, 1, 2, ..., 29. Estos serán los números de nuestros grupos.

¡Útil! Por cierto, casi cualquier función hash utiliza el resto de la división - esto es muy simple y permite ajustar el número de grupos en los que se deben dividir los elementos.

5.3 Propiedades principales de una función hash

Propiedades principales de una buena función hash:

Determinismo: La misma función hash siempre debe devolver el mismo valor hash para el mismo valor de entrada.

Ejemplo:

key = "example"
assert hash(key) == hash(key)

Importante! El operador assert verifica que a la derecha se encuentra una expresión verdadera True. Si la expresión no es verdadera False, se lanzará una excepción.

Uniformidad: Una buena función hash debe distribuir los valores uniformemente en todo el rango de posibles valores hash para evitar colisiones.

Ejemplo de la vida de un desarrollador de Python: En un diccionario (clase dict) de Python, la función hash hash() distribuye las claves uniformemente.

Eficiencia de cálculo: La función hash debe ser rápida y eficiente, para no ralentizar las operaciones de inserción y búsqueda.

Ejemplo de la vida de un desarrollador de Python: Las funciones hash estándar en Python están diseñadas para trabajar con claves de varios tipos, como cadenas y números.

Minimización de colisiones: Una colisión ocurre cuando dos claves diferentes tienen el mismo valor hash. Una buena función hash debe minimizar la probabilidad de colisiones.

Ejemplo de la vida de un desarrollador de Python: El algoritmo SHA-256 minimiza la probabilidad de colisiones al hashear datos.

Distribución de hashes: Para grandes volúmenes de datos, la función hash debe proporcionar una distribución uniforme de los valores hash en toda la tabla hash.

Ejemplo de la vida de un desarrollador de Python: Las funciones hash estándar en Python manejan bien la distribución de claves en tablas hash.

5.4 Ejemplos de funciones hash y su implementación

Las funciones hash toman datos de tamaño arbitrario y devuelven un tamaño fijo de valor hash. Revisemos algunos ejemplos de funciones hash y su implementación.

Ejemplo 1: Función hash simple para cadenas

Una de las funciones hash más simples para cadenas puede ser implementada usando la suma de los códigos de los caracteres de la cadena:

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Supongamos que nuestra tabla tiene tamaño 1000

# Ejemplo de uso:
key = "example"
print(f"Valor hash para la clave '{key}': {simple_hash(key)}")

Ejemplo 2: Función hash para cadenas usando hashing polinomial

El hashing polinomial es una técnica más compleja pero efectiva:

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Ejemplo de uso:
key = "example"
print(f"Valor hash para la clave '{key}': {polynomial_hash(key)}")

Ejemplo 3: Función hash incorporada en Python

Python proporciona la función incorporada hash() para obtener el valor hash para varios tipos de datos:

key = "example"
print(f"Valor hash para la clave '{key}': {hash(key)}")

Ejemplo 4: Función hash criptográfica (SHA-256)

Las funciones hash criptográficas, como SHA-256, se usan para garantizar la seguridad de los datos:

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Ejemplo de uso:
key = "example"
print(f"Valor hash para la clave '{key}': {sha256_hash(key)}")

5.5 Introducción al hashing y su aplicación

Hashing — es el proceso de transformar datos de entrada de tamaño arbitrario en un tamaño fijo de valores hash usando una función hash. El hashing se utiliza ampliamente en ciencias de la computación y programación para optimización y seguridad.

Aplicaciones principales del hashing:

1. Tablas hash (diccionarios): Las tablas hash utilizan funciones hash para organizar y acceder rápidamente a los datos.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Valor hash para la clave '{key}': {hash_value}")

2. Control de integridad de datos: Las funciones hash se utilizan para verificar la integridad de archivos y datos.

Ejemplo: Verificación de integridad de archivo usando SHA-256:

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash del archivo: {file_hash}")

3. Criptografía y seguridad: Las funciones hash se utilizan para crear primitivas criptográficas, como firmas digitales y hashes de contraseñas.

Ejemplo: Hashing de contraseña usando SHA-256:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash de la contraseña: {hashed_password}")

4. Motores de búsqueda e indexación: El hashing se utiliza para crear índices y búsqueda rápida de datos.

Ejemplo: Creación de un índice para búsqueda de texto:

def create_index(text):
    index = {}
    for word in text.split():
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

text = "This is an example text for indexing"
index = create_index(text)
print(f"Índice: {index}")

5. Gestión de caché: El hashing se utiliza para organizar cachés, para encontrar datos rápidamente.

Ejemplo: Caché simple usando una función hash:

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Añadir y obtener datos del caché
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Salida: test_value