A tabla de picadillo es una estructura de datos que permite la rápida inserción, eliminación y recuperación de datos. Funciona mediante el uso de una función hash para asignar una clave a un índice en una matriz. En este artículo, implementaremos una tabla hash en Python utilizando encadenamientos separados para manejar colisiones.

Componentes del hashing

El encadenamiento separado es una técnica utilizada para manejar colisiones en una tabla hash. Cuando dos o más claves se asignan al mismo índice en la matriz, las almacenamos en una lista vinculada en ese índice. Esto nos permite almacenar múltiples valores en el mismo índice y aún poder recuperarlos usando su clave.

Manera de implementar Hash Table usando encadenamiento separado

Manera de implementar Hash Table usando encadenamiento separado:

Crea dos clases: ' Nodo ' y ' Tabla de picadillo ‘.

El ' Nodo 'la clase representará un nodo en una lista vinculada. Cada nodo contendrá un par clave-valor, así como un puntero al siguiente nodo de la lista.

Python3

class> Node:> > def> __init__(> self> , key, value):> > self> .key> => key> > self> .value> => value> > self> .> next> => None>

La clase 'HashTable' contendrá la matriz que contendrá las listas vinculadas, así como métodos para insertar, recuperar y eliminar datos de la tabla hash.

Python3

class> HashTable:> > def> __init__(> self> , capacity):> > self> .capacity> => capacity> > self> .size> => 0> > self> .table> => [> None> ]> *> capacity>

El ' __caliente__ 'El método inicializa la tabla hash con una capacidad determinada. Establece el ' capacidad ' y ' tamaño 'variables e inicializa la matriz en 'Ninguno'.

El siguiente método es el ' _picadillo ' método. Este método toma una clave y devuelve un índice en la matriz donde se debe almacenar el par clave-valor. Usaremos la función hash incorporada de Python para codificar la clave y luego usaremos el operador de módulo para obtener un índice en la matriz.

Python3

def> _hash(> self> , key):> > return> hash> (key)> %> self> .capacity>

El 'insertar' El método insertará un par clave-valor en la tabla hash. Toma el índice donde se debe almacenar el par usando el comando ' _picadillo ' método. Si no hay una lista vinculada en ese índice, crea un nuevo nodo con el par clave-valor y lo establece como encabezado de la lista. Si hay una lista vinculada en ese índice, repita la lista hasta que se encuentre el último nodo o la clave ya exista, y actualice el valor si la clave ya existe. Si encuentra la clave, actualiza el valor. Si no encuentra la clave, crea un nuevo nodo y lo agrega al encabezado de la lista.

Python3

def> insert(> self> , key, value):> > index> => self> ._hash(key)> > if> self> .table[index]> is> None> :> > self> .table[index]> => Node(key, value)> > self> .size> +> => 1> > else> :> > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > current.value> => value> > return> > current> => current.> next> > new_node> => Node(key, value)> > new_node.> next> => self> .table[index]> > self> .table[index]> => new_node> > self> .size> +> => 1>

El buscar El método recupera el valor asociado con una clave determinada. Primero obtiene el índice donde se debe almacenar el par clave-valor usando el _picadillo método. Luego busca la clave en la lista vinculada en ese índice. Si encuentra la clave, devuelve el valor asociado. Si no encuentra la clave, levanta una Error de clave .

Python3

def> search(> self> , key):> > index> => self> ._hash(key)> > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > return> current.value> > current> => current.> next> > raise> KeyError(key)>

El 'eliminar' El método elimina un par clave-valor de la tabla hash. Primero obtiene el índice donde se debe almacenar el par usando el ` _picadillo `método. Luego busca la clave en la lista vinculada en ese índice. Si encuentra la clave, elimina el nodo de la lista. Si no encuentra la clave, genera un ` Error de clave `.

Python3

def> remove(> self> , key):> > index> => self> ._hash(key)> > > previous> => None> > current> => self> .table[index]> > > while> current:> > if> current.key> => => key:> > if> previous:> > previous.> next> => current.> next> > else> :> > self> .table[index]> => current.> next> > self> .size> -> => 1> > return> > previous> => current> > current> => current.> next> > > raise> KeyError(key)>

'__cadena__' Método que devuelve una representación de cadena de la tabla hash.

Python3

def> __str__(> self> ):> > elements> => []> > for> i> in> range> (> self> .capacity):> > current> => self> .table[i]> > while> current:> > elements.append((current.key, current.value))> > current> => current.> next> > return> str> (elements)>

Aquí está la implementación completa de la clase 'HashTable':

Python3

class> Node:> > def> __init__(> self> , key, value):> > self> .key> => key> > self> .value> => value> > self> .> next> => None> > > class> HashTable:> > def> __init__(> self> , capacity):> > self> .capacity> => capacity> > self> .size> => 0> > self> .table> => [> None> ]> *> capacity> > > def> _hash(> self> , key):> > return> hash> (key)> %> self> .capacity> > > def> insert(> self> , key, value):> > index> => self> ._hash(key)> > > if> self> .table[index]> is> None> :> > self> .table[index]> => Node(key, value)> > self> .size> +> => 1> > else> :> > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > current.value> => value> > return> > current> => current.> next> > new_node> => Node(key, value)> > new_node.> next> => self> .table[index]> > self> .table[index]> => new_node> > self> .size> +> => 1> > > def> search(> self> , key):> > index> => self> ._hash(key)> > > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > return> current.value> > current> => current.> next> > > raise> KeyError(key)> > > def> remove(> self> , key):> > index> => self> ._hash(key)> > > previous> => None> > current> => self> .table[index]> > > while> current:> > if> current.key> => => key:> > if> previous:> > previous.> next> => current.> next> > else> :> > self> .table[index]> => current.> next> > self> .size> -> => 1> > return> > previous> => current> > current> => current.> next> > > raise> KeyError(key)> > > def> __len__(> self> ):> > return> self> .size> > > def> __contains__(> self> , key):> > try> :> > self> .search(key)> > return> True> > except> KeyError:> > return> False> > > # Driver code> if> __name__> => => '__main__'> :> > > # Create a hash table with> > # a capacity of 5> > ht> => HashTable(> 5> )> > > # Add some key-value pairs> > # to the hash table> > ht.insert(> 'apple'> ,> 3> )> > ht.insert(> 'banana'> ,> 2> )> > ht.insert(> 'cherry'> ,> 5> )> > > # Check if the hash table> > # contains a key> > print> (> 'apple'> in> ht)> # True> > print> (> 'durian'> in> ht)> # False> > > # Get the value for a key> > print> (ht.search(> 'banana'> ))> # 2> > > # Update the value for a key> > ht.insert(> 'banana'> ,> 4> )> > print> (ht.search(> 'banana'> ))> # 4> > > ht.remove(> 'apple'> )> > # Check the size of the hash table> > print> (> len> (ht))> # 3>

Producción

True False 2 4 3 

Complejidad temporal y complejidad espacial:

• El complejidad del tiempo del insertar , buscar y eliminar Los métodos en una tabla hash que utilizan encadenamiento separado dependen del tamaño de la tabla hash, el número de pares clave-valor en la tabla hash y la longitud de la lista vinculada en cada índice.
• Suponiendo una buena función hash y una distribución uniforme de claves, la complejidad temporal esperada de estos métodos es O(1) para cada operación. Sin embargo, en el peor de los casos, la complejidad del tiempo puede ser En) , donde n es el número de pares clave-valor en la tabla hash.
• Sin embargo, es importante elegir una buena función hash y un tamaño apropiado para la tabla hash para minimizar la probabilidad de colisiones y garantizar un buen rendimiento.
• El complejidad espacial El uso de una tabla hash mediante encadenamiento separado depende del tamaño de la tabla hash y del número de pares clave-valor almacenados en la tabla hash.
• La propia tabla hash toma O(m) espacio, donde m es la capacidad de la tabla hash. Cada nodo de la lista enlazada toma O(1) espacio, y puede haber como máximo n nodos en las listas vinculadas, donde n es el número de pares clave-valor almacenados en la tabla hash.
• Por lo tanto, la complejidad total del espacio es O(metro + norte) .

Conclusión:

En la práctica, es importante elegir una capacidad adecuada para que la tabla hash equilibre el uso del espacio y la probabilidad de colisiones. Si la capacidad es demasiado pequeña, aumenta la probabilidad de colisiones, lo que puede provocar una degradación del rendimiento. Por otro lado, si la capacidad es demasiado grande, la tabla hash puede consumir más memoria de la necesaria.