Implementación de Hash Tables Personalizadas en ZIG
La implementación de hash tables personalizadas es una habilidad fundamental para cualquier programador. En este artículo, exploraremos cómo crear un hash table personalizado en el lenguaje ZIG. Un hash table es una estructura de datos que almacena pares clave-valor y permite una búsqueda eficiente de elementos. Para implementar un hash table personalizado, debemos considerar varios factores, como la función de hash, la gestión de colisiones y la memoria.
Función de Hash
La función de hash es un componente crítico en un hash table. Su función es tomar una clave y convertirla en un índice que se puede utilizar para acceder a la tabla. Una buena función de hash debería ser rápida, determinista y uniforme. Aquí hay algunos requisitos para una función de hash:
- Debería ser rápida de calcular
- Debería ser determinista, es decir, siempre devuelve el mismo resultado para la misma entrada
- Debería ser uniforme, es decir, debería distribuir las claves de manera uniforme en la tabla
Por ejemplo, aquí hay una función de hash simple en ZIG que toma una cadena como clave y devuelve un índice:
“`zig
const std = @import(“std”);
pub fn hash(clave: []const u8) u32 {
var hash: u32 = 0;
for (clave) |caracter| {
hash = hash * 31 + caracter;
}
return hash;
}
“`
Esta función de hash utiliza el algoritmo de hash de cadena de caracteres, que es simple y rápido, pero no es adecuado para claves largas o para aplicaciones criptográficas.
Gestión de Colisiones
La gestión de colisiones es otro aspecto importante en un hash table. Una colisión ocurre cuando dos claves diferentes producen el mismo índice. Hay varias formas de gestionar colisiones, como la encadenamiento (linked chaining) o la sondaje lineal (linear probing). En este ejemplo, utilizaremos la encadenamiento.
Aquí hay un ejemplo de cómo podríamos implementar un hash table con encadenamiento en ZIG:
“`zig
const std = @import(“std”);
pub fn HashTable(comptime Valor: type) type {
return struct {
const Entrada = struct {
clave: []const u8,
valor: Valor,
};
tabla: []Entrada,
capacidad: usize,
pub fn init(capacidad: usize) HashTable(Valor) {
return HashTable(Valor){
.tabla = try std.heap.page_allocator.alloc(Entrada, capacidad),
.capacidad = capacidad,
};
}
pub fn insertar(self: *HashTable(Valor), clave: []const u8, valor: Valor) !void {
const indice = hash(clave) % self.capacidad;
for (self.tabla[indice..]) |*entrada| {
if (std.mem.eql(u8, entrada.clave, clave)) {
entrada.valor = valor;
return;
}
}
// Encadenamiento
self.tabla[indice].clave = clave;
self.tabla[indice].valor = valor;
}
pub fn buscar(self: HashTable(Valor), clave: []const u8) ?Valor {
const indice = hash(clave) % self.capacidad;
for (self.tabla[indice..]) |entrada| {
if (std.mem.eql(u8, entrada.clave, clave)) {
return entrada.valor;
}
}
return null;
}
};
}
“`
Este ejemplo define un hash table que almacena pares clave-valor, donde la clave es una cadena y el valor es de un tipo genérico `Valor`. La función `init` inicializa el hash table con una capacidad determinada, la función `insertar` inserta un par clave-valor en el hash table, y la función `buscar` busca un valor en el hash table por su clave.
Ejemplo de Uso
Aquí hay un ejemplo de cómo podríamos utilizar el hash table que hemos implementado:
“`zig
test “hash table” {
var hash_table = HashTable(i32).init(10);
try hash_table.insertar(“clave1”, 10);
try hash_table.insertar(“clave2”, 20);
std.debug.print(“Valor de clave1: {d}n”, .{hash_table.buscar(“clave1”).?});
std.debug.print(“Valor de clave2: {d}n”, .{hash_table.buscar(“clave2”).?});
}
“`
Este ejemplo crea un hash table que almacena valores enteros, inserta dos pares clave-valor, y luego busca y imprime los valores de las claves “clave1” y “clave2”.
En resumen, la implementación de un hash table personalizado en ZIG requiere considerar varios factores, como la función de hash, la gestión de colisiones y la memoria. En este artículo, hemos explorado cómo crear un hash table personalizado con encadenamiento y hemos proporcionado ejemplos de código para ilustrar su uso.
