Google+ Seguidores

sábado, 23 de junio de 2018

Tabla Hash en Python

Introducción:

Que hay amigos de Internet? Mi nombre es Luis y les doy nuevamente la bienvenida a Mi Diario Pyhton, el Blog ideal para Aprender Python y sus conceptos básicos.

En el articulo de hoy nos centraremos en conocer el concepto de "Tabla Hash" y al final implementaremos una utilizando el lenguaje de programación Python

¿Que es una Tabla Hash?

Ejemplo de Tabla Hash.


Una tabala hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soportan de manera eficiente las tablas hash es la búsqueda: permite el acceso a los elemnentos almacenados a partir de una clave generada. Por ejemplo, podrías encontrar el numero telefónico de una persona utilizando solo su nombre.

Esta tabla hash funciona transformando la clave con una función hash en un hash, un número que identifica la posición donde la tabla hash localiza el valor deseado.

Y cabe destacar que comparada con otras estructura de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información.

Las operaciones básicas implementadas en la tabla hash son:

Inserción:

La forma de implementar en función esta operación es pidiendo la llave y el valor, para con estos poder hacer la inserción del dato.


  1. Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen (hash) a la clave del elemento.
  1. El resultado de la función resumen ha de mapearse al espacio de direcciones del vector que se emplea como soporte, lo cual se consigue con la función módulo. Tras este paso se obtiene un índice válido para la tabla.
  1. El elemento se almacena en la posición de la tabla obtenido en el paso anterior.

Búsqueda:

La forma de implementar en función esta operación es pidiendo la llave y con esta devolver el valor.
  1. Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
  2. El valor obtenido se mapea al espacio de direcciones de la tabla.
  3. Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.
La mayoría de las implementaciones también incluyen la función de borrar a la cual se le envía una llave que deberá eliminar. También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave.

Implementación en Python:

Hora de escribir código. Lo que haremos sera realizar una implemtación sencilla de una tabla hash en Python:

class hash_table:
    def __init__(self):
        self.table = [None] * 127
    
    # Función hash
    def Hash_func(self, value):
        key = 0
        for i in range(0,len(value)):
            key += ord(value[i])
        return key % 127

    def Insert(self, value): # Metodo para ingresar elementos
        hash = self.Hash_func(value)
        if self.table[hash] is None:
            self.table[hash] = value
   
    def Search(self,value): # Metodo para buscar elementos
        hash = self.Hash_func(value);
        if self.table[hash] is None:
            return None
        else:
            return hex(id(self.table[hash]))
  
    def Remove(self,value): # Metodo para eleminar elementos
        hash = self.Hash_func(value);
        if self.table[hash] is None:
            print("No hay elementos con ese valor", value)
        else:
            print("Elemento con valor", value, "eliminado")
            self.table[hash] is None;
        
        
H = hash_table()
H.Insert("A")
H.Insert("B")
H.Insert("C")

print(H.Search("B"))

0x5c56a0

Puedes ver el código en acción Ingresando Aquí.

¿Alguna duda? No dudes en dejar un comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.

1 comentario :
Write comentarios
  1. Hola Luis, tengo varias dudas.
    Primero, hay algún motivo en concreto por el que se cree la tabla con 127 valores?
    Y segundo, el método de búsqueda retornamos el id en hexadecimal, porque?

    ResponderEliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .