10.1 Introducción a las funciones hash y tablas hash
Vamos a recordar y profundizar nuestro entendimiento de las funciones hash y tablas. Una función hash es un algoritmo que transforma datos de entrada de longitud arbitraria en una cadena de longitud fija. Las propiedades principales de las funciones hash:
- Determinismo: los mismos datos de entrada siempre dan el mismo resultado.
- Cálculo rápido: el hash debe calcularse lo suficientemente rápido.
- Irreversibilidad (para funciones hash criptográficas): es imposible (o extremadamente difícil) recuperar los datos originales del hash.
- Distribución uniforme: pequeños cambios en los datos de entrada provocan cambios significativos en el hash.
Para simplificar, esta función en objetos idénticos coincide necesariamente, pero si la función hash en dos objetos es la misma, esos objetos no necesariamente son iguales. En matemáticas, esto se llama una condición necesaria, pero no suficiente.
Una tabla hash es una estructura de datos que utiliza una función hash para almacenar y buscar información de manera eficiente. Está compuesta por:
- Un arreglo de "cestas" para almacenar datos.
- Una función hash que determina en qué cesta colocar los datos.
Las tablas hash proporcionan acceso rápido a los datos, generalmente con una complejidad de O(1) en promedio.
Aplicación de funciones hash en la vida real
Ejemplo: Tecnologías Blockchain
En blockchain, las funciones hash se utilizan para crear identificadores únicos de bloques y asegurar la integridad de los datos. Cada bloque contiene el hash del bloque anterior, lo que crea una cadena y hace que el sistema sea resistente a los cambios.
import hashlib
import time
class Block:
def __init__(self, data, previous_hash):
self.timestamp = time.time()
self.data = data
self.previous_hash = previous_hash
self.hash = self.calculate_hash()
def calculate_hash(self):
hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
return hashlib.sha256(hash_string.encode()).hexdigest()
# Ejemplo de uso
block1 = Block("Transacción 1", "0")
block2 = Block("Transacción 2", block1.hash)
print(f"Hash del bloque 1: {block1.hash}")
print(f"Hash del bloque 2: {block2.hash}")
Comparación de rendimiento
Consideremos la tarea de encontrar duplicados en un arreglo. Comparemos la solución usando una tabla hash y sin ella:
import time
def find_duplicates_with_hash(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
def find_duplicates_without_hash(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j] and arr[i] not in duplicates:
duplicates.append(arr[i])
return duplicates
# Prueba de rendimiento
arr = list(range(10000)) + list(range(5000)) # Arreglo con duplicados
start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Tiempo de ejecución con tabla hash: {end - start} segundos")
start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Tiempo de ejecución sin tabla hash: {end - start} segundos")
Ejecuta el programa y observa cuánto acelera la búsqueda de duplicados el uso de una tabla hash. Especialmente en grandes conjuntos de datos.
10.2 Ejemplos de aplicación de funciones hash en tareas reales
1. Hashing de contraseñas
Las funciones hash se utilizan para el almacenamiento seguro de contraseñas. En lugar de almacenar las contraseñas en texto claro, los sistemas almacenan sus hashes. Al ingresar una contraseña, el sistema hashea la contraseña ingresada y la compara con el hash almacenado en la base de datos.
Ejemplo de implementación:
import hashlib
def hash_password(password):
return hashlib.sha256(password.encode()).hexdigest()
# Ejemplo de uso:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash de la contraseña: {hashed_password}")
2. Control de integridad de datos
Las funciones hash se utilizan para verificar la integridad de archivos y datos. Por ejemplo, para comprobar si un archivo ha sido modificado o dañado durante la transmisión.
Ejemplo de implementación:
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()
# Ejemplo de uso:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash del archivo: {file_hash}")
3. Motores de búsqueda e indexación
Los motores de búsqueda utilizan funciones hash para crear índices y buscar información rápidamente. Cada documento se indexa por palabras clave, y las funciones hash ayudan a encontrar rápidamente documentos que contienen las palabras dadas.
Ejemplo de implementación:
def create_index(text):
index = {}
words = text.split()
for word in words:
word_hash = hash(word)
if word_hash not in index:
index[word_hash] = []
index[word_hash].append(word)
return index
# Ejemplo de uso:
text = "This is an example text for indexing"
index = create_index(text)
print(f"Índice: {index}")
10.3 Optimización de búsqueda utilizando funciones hash
1. Uso de tablas hash para encontrar duplicados
Las tablas hash permiten encontrar rápidamente duplicados en un arreglo comparando los valores hash de los elementos.
Ejemplo de implementación:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Ejemplo de uso:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Salida: [2, 4]
2. Optimización de la búsqueda de pares con suma dada
Las tablas hash permiten encontrar eficientemente pares de números en un arreglo cuya suma es igual a un valor dado.
Ejemplo de implementación:
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# Ejemplo de uso:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Salida: [(4, 2), (3, 3), (8, -2)]
10.4 Ejemplos de uso de funciones hash en varios algoritmos
1. Conteo de palabras en un texto
Usa una tabla hash para contar la frecuencia de cada palabra en un texto.
Ejemplo de implementación:
def count_words(text):
word_count = {}
words = text.split()
for word in words:
if word in word_count:
word_count[word] += 1
else:
word_count[word] = 1
return word_count
# Ejemplo de uso:
text = "this is a test this is only a test"
print(count_words(text)) # Salida: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}
2. Verificación de intersección de dos arreglos
Verifica si dos arreglos se intersectan (si tienen al menos un elemento común).
Ejemplo de implementación:
def has_intersection(arr1, arr2):
set1 = set(arr1)
for item in arr2:
if item in set1:
return True
return False
# Ejemplo de uso:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2)) # Salida: True
print(has_intersection(arr1, arr3)) # Salida: False
3. Verificación de unicidad de elementos en un arreglo
Verifica si un arreglo contiene solo elementos únicos.
Ejemplo de implementación:
def all_unique(arr):
seen = set()
for item in arr:
if item in seen:
return False
seen.add(item)
return True
# Ejemplo de uso:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1)) # Salida: True
print(all_unique(arr2)) # Salida: False
GO TO FULL VERSION