7.1 Definición de colisiones en una tabla hash
Una colisión en una tabla hash ocurre cuando dos claves diferentes se hashmean al mismo índice en el array. Esto lleva a que más de un elemento intente ocupar la misma celda en la tabla hash.
Ejemplo de colisión:
Supongamos que tenemos una función hash simple que devuelve el resto de dividir la clave por el tamaño de la tabla. Para las claves 5 y 15 con un tamaño de tabla de 10, ambas claves darán el mismo índice: 5 % 10 = 5 y 15 % 10 = 5. Esto es una colisión.
Otro ejemplo:
Supongamos, estás haciendo un diccionario de nombres, y tienes una función hash simple que devuelve la primera letra del nombre. Pero resulta que el 80% de los nombres comienzan con la letra "A". Esto no es solo una colisión, es un problema.
7.2 Métodos para resolver colisiones – cadenas
Existen varios métodos para resolver colisiones en tablas hash. Los dos métodos más comunes son las cadenas (chaining) y la dirección abierta (open addressing).
Cadenas (Chaining)
Ventajas:
- Facilidad de implementación.
- Eficiencia con un pequeño número de colisiones.
- Menor dependencia de la densidad de llenado de la tabla hash.
Desventajas:
- Requiere memoria adicional para los punteros en la lista enlazada.
- El rendimiento puede disminuir con un gran número de colisiones debido a las cadenas largas.
Ejemplo de implementación del método de cadenas:
Puedes solo estudiar cómo trabaja la función insert, pero he decidido dar el código completo por conveniencia.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# Ejemplo de uso:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Salida: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Salida: None
7.3 Método número dos – dirección abierta
El método de dirección abierta implica buscar la siguiente celda disponible en el array si ocurre una colisión. Existen diferentes estrategias para buscar una nueva celda: sondeo lineal, sondeo cuadrático y doble hash.
Ventajas:
- No requiere memoria adicional para almacenar punteros.
- Representación de datos más compacta.
Desventajas:
- El rendimiento puede disminuir significativamente con alta densidad de llenado de la tabla.
- Requiere más recursos computacionales para resolver colisiones.
Ejemplos de estrategias de dirección abierta
Sondeo lineal (Linear Probing):
- Sondeo con paso 1:
index = (index + 1) % size. - Sencillo, pero puede llevar a "clusterización".
Sondeo cuadrático (Quadratic Probing):
- Sondeo con paso que aumenta cuadráticamente:
index = (index + i^2) % size. - Reduce problemas de clusterización, pero es más complejo de implementar.
Doble hash (Double Hashing):
- Uso de una segunda función hash para calcular el paso:
index = (index + i * hash2(key)) % size. - Menos problemas de clusterización, pero más complejo de implementar.
Ejemplo de implementación del método de dirección abierta (sondeo lineal): Proporcionaré el código completo, para simplificar puedes analizar solo cómo trabaja la función insert
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("La tabla hash está llena")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
def delete(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = (index + 1) % self.size
if index == original_index:
break
# Ejemplo de uso:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Salida: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Salida: None
7.4 Impacto de las colisiones en la tabla hash
Impacto de las colisiones en el rendimiento.
Tiempo promedio de acceso:
- En condiciones ideales (sin colisiones) el tiempo promedio de acceso a elementos en la tabla hash es
O(1). - Las colisiones incrementan el tiempo de acceso, ya que se requiere manejar cadenas o sondeo de celdas, lo que aumenta el número de operaciones.
Aumento de la longitud de las cadenas:
- En el método de cadenas, el aumento de la longitud de las cadenas con un gran número de colisiones puede llevar a un tiempo de acceso lineal
O(n)para operaciones de búsqueda, inserción y eliminación. - Cadenas largas incrementan el número de comparaciones necesarias para encontrar o insertar un elemento.
Complejidad espacial:
- En el método de cadenas, se requiere memoria adicional para almacenar los punteros en las listas enlazadas.
- En el método de dirección abierta, llenar la tabla por encima de cierto nivel (generalmente alrededor del 70-80%) incrementa significativamente el número de colisiones y, por lo tanto, el tiempo de acceso.
Clusterización: En el método de dirección abierta (especialmente con sondeo lineal) ocurre una clusterización cuando varias celdas consecutivas se vuelven ocupadas, lo que incrementa la probabilidad de colisiones y empeora el rendimiento.
Ejemplo de análisis del impacto de las colisiones en el rendimiento:
Esto es para los que les gusta profundizar
import time
import random
# Sondeo lineal
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("La tabla hash está llena")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
# Generación de una gran cantidad de datos para inserción
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]
# Inserción de datos y medición del tiempo
start_time = time.time()
for key in keys:
hash_table.insert(key, key)
print(f"Tiempo de inserción: {time.time() - start_time:.6f} segundos")
# Búsqueda de datos y medición del tiempo
start_time = time.time()
for key in keys:
hash_table.search(key)
print(f"Tiempo de búsqueda: {time.time() - start_time:.6f} segundos")
GO TO FULL VERSION