Mapa hash en Python

Los mapas hash son estructuras de datos indexados. Un mapa hash utiliza una función hash para calcular un índice con una clave en una array de cubos o ranuras. Su valor se asigna al depósito con el índice correspondiente. La clave es única e inmutable. Piense en un mapa hash como un gabinete con cajones con etiquetas para las cosas almacenadas en ellos. Por ejemplo, almacenar información del usuario: considere el correo electrónico como la clave, y podemos asignar los valores correspondientes a ese usuario, como el nombre, el apellido, etc., en un depósito.  

La función hash es el núcleo de la implementación de un mapa hash. Toma la clave y la traduce al índice de un depósito en la lista de depósitos. El hashing ideal debería producir un índice diferente para cada clave. Sin embargo, pueden ocurrir colisiones. Cuando el hashing proporciona un índice existente, simplemente podemos usar un depósito para múltiples valores agregando una lista o rehaciendo.

En Python, los diccionarios son ejemplos de mapas hash. Veremos la implementación del mapa hash desde cero para aprender cómo construir y personalizar tales estructuras de datos para optimizar la búsqueda.

El diseño del mapa hash incluirá las siguientes funciones:

  • set_val(clave, valor): inserta un par clave-valor en el mapa hash. Si el valor ya existe en el mapa hash, actualice el valor.
  • get_val(clave): Devuelve el valor al que se asigna la clave especificada, o «No se encontró ningún registro» si este mapa no contiene ninguna asignación para la clave.
  • delete_val(key): elimina la asignación de la clave específica si el mapa hash contiene la asignación de la clave.

A continuación se muestra la implementación.

Python3

class HashTable:
  
    # Create empty bucket list of given size
    def __init__(self, size):
        self.size = size
        self.hash_table = self.create_buckets()
  
    def create_buckets(self):
        return [[] for _ in range(self.size)]
  
    # Insert values into hash map
    def set_val(self, key, val):
        
        # Get the index from the key
        # using hash function
        hashed_key = hash(key) % self.size
          
        # Get the bucket corresponding to index
        bucket = self.hash_table[hashed_key]
  
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
              
            # check if the bucket has same key as
            # the key to be inserted
            if record_key == key:
                found_key = True
                break
  
        # If the bucket has same key as the key to be inserted,
        # Update the key value
        # Otherwise append the new key-value pair to the bucket
        if found_key:
            bucket[index] = (key, val)
        else:
            bucket.append((key, val))
  
    # Return searched value with specific key
    def get_val(self, key):
        
        # Get the index from the key using
        # hash function
        hashed_key = hash(key) % self.size
          
        # Get the bucket corresponding to index
        bucket = self.hash_table[hashed_key]
  
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
              
            # check if the bucket has same key as 
            # the key being searched
            if record_key == key:
                found_key = True
                break
  
        # If the bucket has same key as the key being searched,
        # Return the value found
        # Otherwise indicate there was no record found
        if found_key:
            return record_val
        else:
            return "No record found"
  
    # Remove a value with specific key
    def delete_val(self, key):
        
        # Get the index from the key using
        # hash function
        hashed_key = hash(key) % self.size
          
        # Get the bucket corresponding to index
        bucket = self.hash_table[hashed_key]
  
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
              
            # check if the bucket has same key as
            # the key to be deleted
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket.pop(index)
        return
  
    # To print the items of hash map
    def __str__(self):
        return "".join(str(item) for item in self.hash_table)
  
  
hash_table = HashTable(50)
  
# insert some values
hash_table.set_val('gfg@example.com', 'some value')
print(hash_table)
print()
  
hash_table.set_val('portal@example.com', 'some other value')
print(hash_table)
print()
  
# search/access a record with key
print(hash_table.get_val('portal@example.com'))
print()
  
# delete or remove a value
hash_table.delete_val('portal@example.com')
print(hash_table)

Producción:

Complejidad del tiempo:

El acceso al índice de memoria lleva un tiempo constante y el hashing lleva un tiempo constante. Por lo tanto, la complejidad de búsqueda de un mapa hash también es constante en el tiempo, es decir, O(1).

Publicación traducida automáticamente

Artículo escrito por akshisaxena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *