Map - Tablas

Las tablas son estructuras de datos que permiten almacenar elementos en pares clave-valor. En esta sección se presentan las implementaciones de tablas que se encuentran en el módulo DataStructures.Map.

Como usar la documentación

Para leer la guía de uso de la documentación, por favor diríjase a la sección Guía de documentación.

Elementos

map_entry.py

Estructura de una entrada de una tabla. Una entrada de una tabla es un elemento que contiene una llave y un valor.

new_map_entry(key, value)

Crea una nueva entrada (de tipo map_entry) de una tabla con una llave y un valor dados.

La entrada es creada con los siguientes atributos:

key: Llave de la entrada. Inicializada con el valor de la llave dada key.
value: Valor de la entrada. Inicializada con el valor del valor dado value.

Parameters:

key (any) – Llave de la entrada.
value (any) – Valor de la entrada.

Returns:

Entrada de una tabla.

Return type:

map_entry

Example:

# App/logic.py
from DataStructures.Map import map_entry as me

# Crear una nueva entrada de una tabla
entry = me.new_map_entry(1, {'name': 'John', 'age': 25})
print(entry)
# Salida esperada:{'key': 1, 'value': {'name': 'John', 'age': 25}}

set_key(my_entry, key)

Establece un valor nuevo a la key de una entrada recibida.

Parameters:

my_entry (map_entry) – Entrada a modificar.
key (any) – Llave nueva de la entrada.

Returns:

Entrada con la llave modificada.

Return type:

map_entry

Example:

# App/logic.py
from DataStructures.Map import map_entry as me

# Crear una nueva entrada de una tabla
entry = me.new_map_entry(1, {'name': 'John', 'age': 25})
print(entry)
# Salida esperada:{'key': 1, 'value': {'name': 'John', 'age': 25}}

# Establecer la llave nueva de la entrada
entry = me.set_key(entry, "new_key")
print(entry)
# Salida esperada:{'key': "new_key", 'value': {'name': 'John', 'age': 25}}

set_value(my_entry, value)

Establece un valor nuevo al value de una entrada recibida.

Parameters:

my_entry (map_entry) – Entrada a modificar.
value (any) – Valor nuevo de la entrada.

Returns:

Entrada con el valor modificado.

Return type:

map_entry

Example:

# App/logic.py
from DataStructures.Map import map_entry as me

# Crear una nueva entrada de una tabla
entry = me.new_map_entry(1, {'name': 'John', 'age': 25})
print(entry)
# Salida esperada:{'key': 1, 'value': {'name': 'John', 'age': 25}}

# Establecer el valor nuevo de la entrada
entry = me.set_value(entry, "otra cosa")
print(entry)
# Salida esperada:{'key': 1, 'value': "otra cosa"}

get_key(my_entry)

Obtiene la llave key de una entrada recibida.

Parameters:

my_entry (map_entry) – Entrada de la cual se desea obtener la llave.

Returns:

Llave de la entrada.

Return type:

any

Example:

# App/logic.py
from DataStructures.Map import map_entry as me

# Crear una nueva entrada de una tabla
entry = me.new_map_entry(1, {'name': 'John', 'age': 25})
print(entry)
# Salida esperada:{'key': 1, 'value': {'name': 'John', 'age': 25}}

# Obtener la llave de la entrada
key = me.get_key(entry)
print(key)
# Salida esperada:1

get_value(my_entry)

Obtiene el valor value de una entrada recibida.

Parameters:

my_entry (map_entry) – Entrada de la cual se desea obtener el valor.

Returns:

Valor de la entrada.

Return type:

any

Example:

# App/logic.py
from DataStructures.Map import map_entry as me

# Crear una nueva entrada de una tabla
entry = me.new_map_entry(1, {'name': 'John', 'age': 25})
print(entry)
# Salida esperada:{'key': 1, 'value': {'name': 'John', 'age': 25}}

# Obtener el valor de la entrada
value = me.get_value(entry)
print(value)
# Salida esperada:{'name': 'John', 'age': 25}

Funciones comunes de tablas

map_functions.py

Funciones comunes que se utilizan en las implementaciones de tablas, como las funciones de hash.

is_prime(n)

Verifica si el número n dado es primo.

Parameters:

n (int) – Número a verificar si es primo.

Returns:

Verdadero si el número es primo, falso en caso contrario.

Return type:

bool

Example:

# App/logic.py
from DataStructures.Map import map_functions as mf

# Verificar si el número 5 es primo
print(mf.is_prime(5))
# Salida esperada: True

# Verifica si el número 6 es primo
print(mf.is_prime(6))
# Salida esperada: False

next_prime(n)

Obtiene el siguiente número primo después del número n dado.

Parameters:

n (int) – Número a partir del cual se desea obtener el siguiente número primo.

Returns:

Siguiente número primo después de n.

Return type:

int

Example:

# App/logic.py
from DataStructures.Map import map_functions as mf

# Obtener el siguiente número primo después de 5
print(mf.next_prime(5))
# Salida esperada: 7

# Obtener el siguiente número primo después de 6
print(mf.next_prime(6))
# Salida esperada: 7

hash_value(my_table, key)

Calcula el hash para una llave dada, utitiizando el método:

MAD: ((a * hash_key + b) % p) % m, donde:

hash_key es el valor de la función nativa de Python hash() para la llave key.
m es el tamaño de la tabla.
p es un número primo mayor a m.
a y b son enteros aleatorios entre 0 y p-1. con a mayor de 0.

Parameters:

my_table (map_linear_probing o map_separate_chaining) – Tabla en la que se desea calcular el hash.
key (any) – Llave para la cual se desea calcular el hash.

Returns:

Valor del hash para la llave dada. (Que es un índice de la tabla).

Return type:

int

Example:

# App/logic.py
from DataStructures.Map import map_functions as mf
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla con tamaño 10
my_table = ml.new_map_linear_probing(10, 0.5)

# Calcular el hash para la llave 5
print(mf.hash_code(my_table, 5))
# Salida esperada: 5

# Calcular el hash para la llave 6
print(mf.hash_code(my_table, 6))
# Salida esperada: 6

Como hacer pruebas con tablas

Importante

Las modifcaciones usadas para hacer pruebas en tablas deben estar definidas SOLO para las PRUEBAS. Una vez terminadas las pruebas, se deben eliminar las modificaciones para asegurar el buen funcionamiento de la función .

La siguiente modificación se debe hacer en la función new_map de las implementaciones para asegurar la reproducibilidad de los ejemplos presentados en la documentación. Para esto, se debe modificar la función new_map de la siguiente manera:

Default code:

def new_map(num_elements, load_factor, prime=109345121):
   ...

   # Establecer los valores de scale y shift para asegurar la reproducibilidad de los resultados
   my_table['scale'] = random.randint(1, prime - 1)
   my_table['shift'] = random.randint(0, prime - 1)
   ...
      return my_table

Test code:

def new_map(num_elements, load_factor, prime=109345121):
   ...

   # Establecer los valores de scale y shift para asegurar la reproducibilidad de los resultados
   my_table['scale'] = 1
   my_table['shift'] = 0
   ...
   return my_table

Test example:

Prueba sin modificación en scale y shift:

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla de simbolos con 10 elementos y factor de carga 0.5
my_table = ml.new_map(1, 0.5)
print(my_table)
#  {
#     'prime': 109345121,
#     'capacity': 3,
#     'scale': 6828135,   (ESTE VALOR ES ALEATORIO, PUEDE NO SER EL MISMO QUE EN LA SALIDA)
#     'shift': 61638967,  (ESTE VALOR ES ALEATORIO, PUEDE NO SER EL MISMO QUE EN LA SALIDA)
#     'table': {
#        'size': 3,
#        'elements': [
#           {
#           'key': None,
#           'value': None
#           },
#           {
#           'key': None,
#           'value': None
#           },
#           {
#           'key': None,
#           'value': None
#           }
#        ]
#     },
#     'current_factor': 0,
#     'limit_factor': 0.5,
#     'size': 0
#  }

Prueba con modificación en scale y shift:

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla de simbolos con 10 elementos y factor de carga 0.5
my_table = ml.new_map(1, 0.5)
print(my_table)
# Salida esperada:
#  {
#     'prime': 109345121,
#     'capacity': 3,
#     'scale': 1,   (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#     'shift': 0,   (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#     'table': {
#        'size': 3,
#        'elements': [
#           {
#           'key': None,
#           'value': None
#           },
#           {
#           'key': None,
#           'value': None
#           },
#           {
#           'key': None,
#           'value': None
#           }
#        ]
#     },
#     'current_factor': 0,
#     'limit_factor': 0.5,
#     'size': 0
#  }

Importante

Recuerde volver a la implementación original una vez terminadas las pruebas. Si no se hace, la implementación de la tabla no funcionará correctamente.

Implementaciones

map_linear_probing.py

new_map(num_elements, load_factor, prime=109345121)

Crea una nueva tabla de simbolos (map) sin elementos.

La tabla de simbolos es creada con los siguientes atributos:

prime: Número primo usado para calcular el hash. Inicializado con el valor de prime y en caso de no ser dado, con el valor por defecto de 109345121.
capacity: Tamaño de la tabla. Inicializado con el siguiente primo mayor a num_elements/ load_factor.
scale: Número entero aleatorio entre 1 y prime- 1.
shift: Número entero aleatorio entre 0 y prime- 1.
table: Lista de tamaño capacity con las entradas de la tabla de tipo array_list. Inicializado con una lista donde cada elemento es una map_entry con llave y valor None.
current_factor: Factor de carga actual de la tabla. Inicializado en 0.
limit_factor: Factor de carga límite de la tabla antes de hacer un rehash. Inicializado con el valor de load_factor.
size: Número de elementos en la tabla. Inicializado en 0.

Parameters:

num_elements (int) – Número de elementos que se desean almacenar en la tabla.
load_factor (float) – Factor de carga límite de la tabla antes de hacer un rehash.
prime (int) – Número primo utilizado para el cálculo del hash. Por defecto es 109345121.

Returns:

Tabla recien creada.

Return type:

map_linear_probing

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacía
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 11,
   'scale': 1,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'size': 11,
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': None,
            'value': None
         }
      ]
   },
   'current_factor': 0,
   'limit_factor': 0.5,
   'size': 0,
}

put(my_map, key, value)

Agrega una nueva entrada llave-valor a la tabla de hash. Si la llave ya existe en la tabla, se actualiza el value de la entrada.

Para agregar un nuevo elemento a la tabla, se realiza el siguiente procedimiento:

Se calcula el hash de la llave, usando la función hash_value.
Se busca la posición en la tabla con la función find_slot. Si la posición está ocupada, se busca la siguiente posición disponible.
Se inserta la entrada en la tabla.
Se actualiza el current_factor de la tabla si se agrega un nuevo elemento.
Si el current_factor supera el limit_factor, se realiza un rehash de la tabla.
Se retorna la tabla con el nuevo elemento agregado.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos a la cual se desea agregar el elemento.
key (any) – Llave del elemento a agregar.
value (any) – Valor del elemento a agregar.

Returns:

Tabla de simbolos con el nuevo elemento agregado.

Return type:

map_linear_probing

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)

# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 11,
#    'scale': 1,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'shift': 0,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'table': {
#       'size': 11,
#       'elements': [
#          {
#              'key': None,
#              'value': None
#          },
#          ... (10 elementos más)
#       ]
#    },
#    'current_factor': 0,
#    'limit_factor': 0.5,
#    'size': 0,
# }

# Agregar un nuevo elemento a la tabla
# La llave 1 se encuentra en la posición 1 de la tabla debido al hash de la llave que se modificó para las pruebas.

my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 11,
   'scale': 1,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': None,
            'value': None
         },
         ... (8 elementos más)
      ],
      'size': 11
   },
   'current_factor': 0.09090909090909091,
   'limit_factor': 0.5,
   'size': 1
}

Test Scenarios:

Agrega un elemento a la tabla: Se agrega un nuevo elemento a una tabla vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla de simbolos con 0 elementos y factor de carga 0.5
my_table = ml.new_map(5, 0.5)

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Se espera la misma respuesta del example de esta función

Agrega un elemento a la tabla sin colision: Se agrega un nuevo elemento a una tabla sin colisión.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table) # Se espera la misma respuesta del example de esta función

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 3, {'name': 'Jane', 'age': 22})
print(my_table)

Salida esperada

{
   'prime': 109345121,
   'capacity': 11,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': 3,
            'value': {
               'name': 'Jane',
               'age': 22
            }
         },
         ... (7 elementos más)
      ],
      'size': 11
   },
   'current_factor': 0.18181818181818182,
   'limit_factor': 0.5,
   'size': 2
}

Agrega un elemento a la tabla con colisión: Se agrega un nuevo elemento a una tabla con una colisión.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table) # Se espera la misma respuesta del example de esta función

# Agregar un nuevo elemento a la tabla con colisión
# La llave 12 se encuentra en la posición 1 de la tabla debido al hash de la llave que se modificó para las pruebas.
my_table = ml.put(my_table, 12, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 11,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': 12,
            'value': {
               'name': 'Jane',
               'age': 22
            }
         },
         ... (8 elementos más)
      ],
      'size': 11
   },
   'current_factor': 0.18181818181818182,
   'limit_factor': 0.5,
   'size': 2
}

find_slot(my_map, key, hash_value)

Busca la posición en la tabla donde se debe insertar/encontrar una entrada con una llave dada.

Utiliza la función de hash_value para calcular la posición inicial y busca la siguiente posición disponible si la posición inicial está ocupada.

Utiliza las funciónes de validación is_available y comparación default_compare.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos en la que se desea buscar la posición.
key (any) – Llave de la entrada que se desea buscar.
hash_value (int) – Valor del hash de la llave.

Returns:

Retorna una tupla con dos valores. El primero indica si la posición está ocupada, True si se encuentra la key de lo contrario False. El segundo la posición en la tabla de hash donde se encuentra o posición libre para agregarla

Return type:

bool, int

Code:

from DataStructures.List import array_list as lt
from DataStructures.Map import map_entry as me

def find_slot(my_map, key, hash_value):
   first_avail = None
   found = False
   ocupied = False
   while not found:
      if is_available(my_map["table"], hash_value):
            if first_avail is None:
               first_avail = hash_value
            entry = lt.get_element(my_map["table"], hash_value)
            if me.get_key(entry) is None:
               found = True
      elif default_compare(key, lt.get_element(my_map["table"], hash_value)) == 0:
            first_avail = hash_value
            found = True
            ocupied = True
      hash_value = (hash_value + 1) % my_map["capacity"]
   return ocupied, first_avail

is_available(table, pos)

Verifica si la posición pos en la tabla de simbolos está disponible.

Se entiende que una posición está disponible si su contenido es igual a None (no se ha usado esa posición) o a __EMPTY__ (la posición fue liberada).

Parameters:

table (array_list) – Tabla de simbolos en la que se desea verificar la disponibilidad de la posición.
pos (int) – Posición en la tabla de simbolos que se desea verificar.

Returns:

True si la posición está disponible, False en caso contrario

Return type:

bool

Code:

from DataStructures.List import array_list as lt
from DataStructures.Map import map_entry as me

def is_available(table, pos):

   entry = lt.get_element(table, pos)
   if me.get_key(entry) is None or me.get_key(entry) == "__EMPTY__":
      return True
   return False

default_compare(key, entry)

Funcion de comparacion por defecto. Compara la llave key con la llave de una entry dada.

Parameters:

key (any) – Llave con la que se desea comparar.
entry (map_entry) – Entrada de la tabla de simbolos con la que se desea comparar.

Returns:

0 si son iguales, 1 si key > la llave del entry, -1 si key < que la llave del entry

Return type:

int

Code:

from DataStructures.Map import map_entry as me

def default_compare(key, entry):

   if key == me.get_key(entry):
      return 0
   elif key > me.get_key(entry):
      return 1
   return -1

contains(my_map, key)

Valida si una llave dada se encuentra en la tabla de simbolos.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos en la que se desea buscar la llave.
key (any) – Llave que se desea buscar en la tabla.

Returns:

True si la llave se encuentra en la tabla, False en caso contrario.

Return type:

bool

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada la misma respuesta de la función put()

# Verificar si la llave 1 se encuentra en la tabla
print(ml.contains(my_table, 1))
# Salida esperada: True

# Verificar si la llave 2 se encuentra en la tabla
print(ml.contains(my_table, 2))
# Salida esperada: False

remove(my_map, key)

Elimina una entrada de la tabla de simbolos asociada a una llave dada.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos de la cual se desea eliminar la entrada.
key (any) – Llave de la entrada que se desea eliminar.

Returns:

Tabla de simbolos sin la entrada asociada a la llave dada.

Return type:

map_linear_probing

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 2, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 3, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 5, {'name': 'Mary', 'age': 20})
print(my_table)

# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 11,
#    'scale': 1,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'shift': 0,    # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'table': {
#       'elements': [
#          {
#             'key': None,
#             'value': None
#          },
#          {
#             'key': 1,
#             'value': {
#                'name': 'John',
#                'age': 25
#             }
#          },
#          {
#             'key': 2,
#             'value': {
#                'name': 'Jane',
#                'age': 22
#             }
#          },
#          {
#             'key': 3,
#             'value': {
#                'name': 'Doe',
#                'age': 30
#             }
#          },
#          {
#             'key': None,
#             'value': None
#          },
#          {
#             'key': 5,
#             'value': {
#                'name': 'Mary',
#                'age': 20
#             }
#          },
#          ... (6 elementos más)
#       ],
#       'size': 11
#    },
#    'current_factor': 0.36363636363636365,
#    'limit_factor': 0.5,
#    'size': 4
# }

# Eliminar la entrada asociada a la llave 1
my_table = ml.remove(my_table, 2)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 11,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': '__EMPTY__',
            'value': '__EMPTY__'
         },
         {
            'key': 3,
            'value': {
               'name': 'Doe',
               'age': 30
            }
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': 5,
            'value': {
               'name': 'Mary',
               'age': 20
            }
         },
        ... (6 elementos más)
      ],
      'size': 11
   },
   'current_factor': 0.2727272727272727,
   'limit_factor': 0.5,
   'size': 3
}

Test Scenarios:

Elimina por llave existente: Se elimina un elemento de la tabla.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 2, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 3, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 5, {'name': 'Mary', 'age': 20})
print(my_table) # Se espera la misma respuesta del example de esta función

# Eliminar la entrada asociada a la llave 1
my_table = ml.remove(my_table, 2)
print(my_table)
# Se espera la misma respuesta del example de esta función

Elimina por llave inexistente: Se intenta eliminar un elemento que no se encuentra en la tabla, retorna la tabla.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 2, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 3, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 5, {'name': 'Mary', 'age': 20})
print(my_table) # Se espera la misma respuesta del example de esta función

# Eliminar la entrada asociada a la llave 4
my_table = ml.remove(my_table, 4)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 11,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': 2,
            'value': {
               'name': 'Jane',
               'age': 22
            }
         },
         {
            'key': 3,
            'value': {
               'name': 'Doe',
               'age': 30
            }
         },
         {
            'key': None,
            'value': None
         },
         {
            'key': 5,
            'value': {
               'name': 'Mary',
               'age': 20
            }
         },
         ... (6 elementos más)
      ],
      'size': 11
   },
   'current_factor': 0.36363636363636365,
   'limit_factor': 0.5,
   'size': 4
}

get(my_map, key)

Obtiene el valor asociado a una llave dada en la tabla de simbolos.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos en la que se desea buscar el valor.
key (any) – Llave de la cual se desea obtener el valor.

Returns:

Valor asociado a la llave dada. Si la llave no se encuentra en la tabla, se retorna None.

Return type:

any

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada la misma respuesta de la función put()

# Obtener el valor asociado a la llave 1
print(ml.get(my_table, 1))
# Salida esperada: {'name': 'John', 'age': 25}

# Obtener el valor asociado a la llave 2
print(ml.get(my_table, 2))
# Salida esperada: None

Test Scenarios:

Buscar por llave existente: Se obtiene el valor asociado a una llave que se encuentra en la tabla.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table) # Se espera la misma respuesta del example de esta función

# Obtener el valor asociado a la llave 1
print(ml.get(my_table, 1))
# Salida esperada: {'name': 'John', 'age': 25}

Buscar por llave inexistente: Se obtiene el valor asociado a una llave que no se encuentra en la tabla.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table) # Se espera la misma respuesta del example de esta función

# Obtener el valor asociado a la llave 2
print(ml.get(my_table, 2))
# Salida esperada: None

Buscar por llave existente con elementos eliminados: Se obtiene el valor asociado a una llave que se encuentra en la tabla pero fueron eliminados elementos en el mismo cluster.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla tal que se genere un cluster
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 12, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 23, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 34, {'name': 'Mary', 'age': 20})
print(my_table)

# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 11,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'key': None,
#             'value': None
#          },
#          {
#             'key': 1,
#             'value': {
#                'name': 'John',
#                'age': 25
#             }
#          },
#          {
#             'key': 12,
#             'value': {
#                'name': 'Jane',
#                'age': 22
#             }
#          },
#          {
#             'key': 23,
#             'value': {
#                'name': 'Doe',
#                'age': 30
#             }
#          },
#          {
#             'key': 34,
#             'value': {
#                'name': 'Mary',
#                'age': 20
#             }
#          },
#          ... (7 elementos más)
#       ],
#       'size': 11
#    },
#    'current_factor': 0.36363636363636365,
#    'limit_factor': 0.5,
#    'size': 4
# }

# Eliminar la entrada asociada a la llave 12
my_table = ml.remove(my_table, 12)
print(my_table)

# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 11,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'key': None,
#             'value': None
#          },
#          {
#             'key': 1,
#             'value': {
#                'name': 'John',
#                'age': 25
#             }
#          },
#          {
#             'key': '__EMPTY__',
#             'value': '__EMPTY__'
#          },
#          {
#             'key': 23,
#             'value': {
#                'name': 'Doe',
#                'age': 30
#             }
#          },
#          {
#             'key': 34,
#             'value': {
#                'name': 'Mary',
#                'age': 20
#             }
#          },
#          ... (7 elementos más)
#       ],
#       'size': 11
#    },
#    'current_factor': 0.2727272727272727,
#    'limit_factor': 0.5,
#    'size': 3
# }

# Obtener el valor asociado a la llave 23
print(ml.get(my_table, 23))
# Salida esperada: {'name': 'Doe', 'age': 30}

size(my_map)

Obtiene la cantidad de elementos en la tabla de simbolos.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos de la cual se desea obtener la cantidad de elementos.

Returns:

Cantidad de elementos en la tabla de simbolos.

Return type:

int

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 2, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 3, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 5, {'name': 'Mary', 'age': 20})
print(my_table)

# Obtener la cantidad de elementos en la tabla
print(ml.size(my_table))
# Salida esperada: 4

Test Scenarios:

Tabla vacía: Se obtiene la cantidad de elementos en una tabla vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Obtener la cantidad de elementos en la tabla
print(ml.size(my_table))
# Salida esperada: 0

Tabla con elementos: Se obtiene la cantidad de elementos en una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 2, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 3, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 5, {'name': 'Mary', 'age': 20})

# Obtener la cantidad de elementos en la tabla
print(ml.size(my_table))
# Salida esperada: 4

Tabla con elementos eliminados: Se obtiene la cantidad de elementos en una tabla con elementos eliminados.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla tal que se genere un cluster
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 12, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 23, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 34, {'name': 'Mary', 'age': 20})
print(my_table)

# Eliminar la entrada asociada a las llaves 12 y 34
my_table = ml.remove(my_table, 12)
my_table = ml.remove(my_table, 34)

# Obtener la cantidad de elementos en la tabla
print(ml.size(my_table))
# Salida esperada: 2

is_empty(my_map)

Valida si la tabla de simbolos está vacía.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos de la cual se desea verificar si está vacía.

Returns:

True si la tabla está vacía, False en caso contrario.

Return type:

bool

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Verificar si la tabla está vacía
print(ml.is_empty(my_table))
# Salida esperada: True

Test Scenarios:

Tabla vacía: Se verifica si una tabla vacía está vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Verificar si la tabla está vacía
print(ml.is_empty(my_table))
# Salida esperada: True

Tabla con elementos: Se verifica si una tabla con elementos está vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})

# Verificar si la tabla está vacía
print(ml.is_empty(my_table))
# Salida esperada: False

key_set(my_map)

Obtiene la lista de llaves de la tabla de simbolos.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos de la cual se desea obtener el conjunto de llaves.

Returns:

Lista de llaves de la tabla de simbolos.

Return type:

array_list

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 3, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 5, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 8, {'name': 'Mary', 'age': 20})
print(my_table)

# Obtener el conjunto de llaves de la tabla
print(ml.key_set(my_table))
# Salida esperada: {'elements': [1, 3, 5, 8], 'size': 4}

Test Scenarios:

Tabla vacía: Se obtiene el conjunto de llaves de una tabla vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Obtener el conjunto de llaves de la tabla
print(ml.key_set(my_table))
# Salida esperada: {'elements': [ ], 'size': 0}

Tabla con elementos: Se obtiene el conjunto de llaves de una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 3, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 5, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 8, {'name': 'Mary', 'age': 20})

# Obtener el conjunto de llaves de la tabla
print(ml.key_set(my_table))
# Salida esperada: {'elements': [1, 3, 5, 8], 'size': 4}

value_set(my_map)

Obtiene la lista de valores de la tabla de simbolos.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos de la cual se desea obtener el conjunto de valores.

Returns:

Lista de valores de la tabla de simbolos.

Return type:

array_list

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 3, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 5, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 8, {'name': 'Mary', 'age': 20})
print(my_table)

# Obtener el conjunto de valores de la tabla
print(ml.value_set(my_table))
# Salida esperada:
# {
#    'elements': [
#       {
#          'name': 'John',
#          'age': 25
#       },
#       {
#          'name': 'Jane',
#          'age': 22
#       },
#       {
#          'name': 'Doe',
#          'age': 30
#       },
#       {
#          'name': 'Mary',
#          'age': 20
#       }
#    ],
#    'size': 4
# }

Test Scenarios:

Tabla vacía: Se obtiene el conjunto de valores de una tabla vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Obtener el conjunto de valores de la tabla
print(ml.value_set(my_table))
# Salida esperada: {'elements': [ ], 'size': 0}

Tabla con elementos: Se obtiene el conjunto de valores de una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 3, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 5, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 8, {'name': 'Mary', 'age': 20})

# Obtener el conjunto de valores de la tabla
print(ml.value_set(my_table))
# Salida esperada:
# {
#    'elements': [
#       {
#          'name': 'John',
#          'age': 25
#       },
#       {
#          'name': 'Jane',
#          'age': 22
#       },
#       {
#          'name': 'Doe',
#          'age': 30
#       },
#       {
#          'name': 'Mary',
#          'age': 20
#       }
#    ],
#    'size': 4
# }

rehash(my_map)

Realiza un rehash de la tabla de simbolos.

Para realizar un rehash se debe seguir los siguientes pasos:

Crear una nueva tabla map_linear_probing con capacity que sea el siguiente primo al doble del capacity actual.
Insertar los elementos de la tabla actual en la nueva tabla uno por uno.
Asignar la nueva tabla a la tabla actual.
Retornar la tabla nueva.

Parameters:

my_map (map_linear_probing) – Tabla de simbolos de la cual se desea realizar el rehash.

Returns:

Tabla de simbolos con el rehash realizado.

Return type:

map_linear_probing

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

# Crear una tabla vacia
my_table = ml.new_map(5, 0.5)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Realizar un rehash de la tabla
my_table = ml.rehash(my_table)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 7,
   'capacity': 23,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         ... (22 elementos)
      ],
      'size': 23
   },
   'current_factor': 0,
   'limit_factor': 0.5,
   'size': 0
}

Test Scenarios:

Rehash de tabla vacía: Se realiza un rehash de una tabla vacía.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Realizar un rehash de la tabla
my_table = ml.rehash(my_table)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 7,
   'capacity': 23,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         ... (22 elementos)
      ],
      'size': 23
   },
   'current_factor': 0,
   'limit_factor': 0.5,
   'size': 0
}

Rehash de tabla con elementos: Se realiza un rehash de una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 3, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 5, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 8, {'name': 'Mary', 'age': 20})
print(my_table)

# Realizar un rehash de la tabla
my_table = ml.rehash(my_table)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 7,
   'capacity': 23,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': 3,
            'value': {
               'name': 'Jane',
               'age': 22
            }
         },
         {
            'key': 5,
            'value': {
               'name': 'Doe',
               'age': 30
            }
         },
         {
            'key': 8,
            'value': {
               'name': 'Mary',
               'age': 20
            }
         },
         ... (19 elementos más)
      ],
      'size': 23
   },
   'current_factor': 0.17391304347826086,
   'limit_factor': 0.5,
   'size': 4
}

Rehash de tabla con elementos eliminados: Se realiza un rehash de una tabla con elementos eliminados.

# App/logic.py
from DataStructures.Map import map_linear_probing as ml

my_table = ml.new_map(5, 0.5)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla tal que se genere un cluster
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = ml.put(my_table, 12, {'name': 'Jane', 'age': 22})
my_table = ml.put(my_table, 23, {'name': 'Doe', 'age': 30})
my_table = ml.put(my_table, 34, {'name': 'Mary', 'age': 20})
print(my_table)

# Eliminar la entrada asociada a las llaves 12 y 34
my_table = ml.remove(my_table, 12)
my_table = ml.remove(my_table, 34)

# Realizar un rehash de la tabla
my_table = ml.rehash(my_table)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 7,
   'capacity': 23,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'key': None,
            'value': None
         },
         {
            'key': 1,
            'value': {
               'name': 'John',
               'age': 25
            }
         },
         {
            'key': 23,
            'value': {
               'name': 'Doe',
               'age': 30
            }
         },
         ... (21 elementos más)
      ],
      'size': 23
   },
   'current_factor': 0.08695652173913043,
   'limit_factor': 0.5,
   'size': 2
}

map_separate_chaining.py

new_map(num_elements, load_factor, prime=109345121)

Crea una nueva tabla de simbolos (map) sin elementos.

La tabla de simbolos es creada con los siguientes atributos:

prime: Número primo usado para calcular el hash. Inicializado con el valor de prime y en caso de no ser dado, con el valor por defecto de 109345121.
capacity: Tamaño de la tabla. Inicializado con el siguiente primo mayor a num_elements/ load_factor.
scale: Número entero aleatorio entre 1 y prime- 1.
shift: Número entero aleatorio entre 0 y prime- 1.
table: array_list de tamaño capacity inicializada con una single_linked_list en cada uno de elementos.
current_factor: Factor de carga actual de la tabla. Inicializado en 0.
limit_factor: Factor de carga límite de la tabla antes de hacer un rehash. Inicializado con el valor de load_factor.
size: Número de elementos en la tabla. Inicializado en 0.

Parameters:

num_elements (int) – Número de elementos que se espera almacenar en la tabla.
load_factor (float) – Factor de carga límite de la tabla antes de hacer un rehash.
prime (int) – Número primo usado para calcular el hash. Por defecto es 109345121.

Returns:

Tabla recien creada.

Return type:

map_separate_chaining

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'first': None,
            'last': None,
            'size': 0
         },
         {
            'first': None,
            'last': None,
            'size': 0
         }
      ],
      'size': 2
   },
   'current_factor': 0,
   'limit_factor': 4,
   'size': 0
}

put(my_map, key, value)

Agrega una nueva entrada llave-valor a la tabla. Si la llave ya existe en la tabla, se actualiza el value de la entrada.

Para agregar una nueva entrada se debe seguir los siguientes pasos:

Calcular el hash de la llave, usando la función hash_value.
Se busca la lista en la posición del hash en la tabla.
Si la llave ya existe en la lista, se actualiza el valor de la entrada.
Si la llave no existe en la lista, se agrega una nueva entrada al final de la lista.
Se actualiza el current_factor de la tabla si se agrega una nueva entrada.
Si el current_factor supera el limit_factor, se realiza un rehash de la tabla.
Se retorna la tabla con la nueva entrada.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos a la cual se desea agregar un nuevo elemento.
key (any) – Llave del nuevo elemento.
value (any) – Valor del nuevo elemento.

Returns:

Tabla de simbolos con el nuevo elemento agregado.

Return type:

map_separate_chaining

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)

# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'table': {
#       'elements': [
#          {
#             'first': None,
#             'last': None,
#             'size': 0
#          },
#          {
#             'first': None,
#             'last': None,
#             'size': 0
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 0,
#    'limit_factor': 4,
#    'size': 0
# }

# Agregar un nuevo elemento a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'first': None,
            'last': None,
            'size': 0
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'size': 1
         }
      ],
      'size': 2
   },
   'current_factor': 0.5,
   'limit_factor': 4,
   'size': 1
}

Test Scenarios:

Agregar un nuevo elemento: Se agrega un nuevo elemento a la tabla.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'first': None,
            'last': None,
            'size': 0
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'size': 1
         }
      ],
      'size': 2
   },
   'current_factor': 0.5,
   'limit_factor': 4,
   'size': 1
}

Agregar un elemento a la tabla sin colision: Se agrega un nuevo elemento a la tabla sin colision.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'first': {
               'info': {
                  'key': 2,
                  'value': {
                     'name': 'Jane',
                     'age': 22
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 2,
                  'value': {
                     'name': 'Jane',
                     'age': 22
                  }
               },
               'next': None
            },
            'size': 1
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'size': 1
         }
      ],
      'size': 2
   },
   'current_factor': 1.0,
   'limit_factor': 4,
   'size': 2
}

Agregar un elemento a la tabla con colision: Se agrega un nuevo elemento a la tabla con colision.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 11, {'name': 'Jane', 'age': 22})
print(my_table)

# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'first': None,
            'last': None,
            'size': 0
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': {
                  'info': {
                     'key': 11,
                     'value': {
                        'name': 'Jane',
                        'age': 22
                     }
                  },
                  'next': None
               }
            },
            'last': {
               'info': {
                  'key': 11,
                  'value': {
                     'name': 'Jane',
                     'age': 22
                  }
               },
               'next': None
            },
            'size': 2
         }
      ],
      'size': 2
   },
   'current_factor': 1.0,
   'limit_factor': 4,
   'size': 2
}

default_compare(key, entry)

Funcion de comparacion por defecto. Compara la llave key con la llave de una entry dada.

Parameters:

key (any) – Llave con la que se desea comparar.
entry (map_entry) – Entrada de la tabla de simbolos con la que se desea comparar.

Returns:

0 si son iguales, 1 si key > la llave del entry, -1 si key < que la llave del entry

Return type:

int

Code:

from DataStructures.Map import map_entry as me

def default_compare(key, element):

   if (key == me.get_key(element)):
      return 0
   elif (key > me.get_key(element)):
      return 1
   return -1

contains(my_map, key)

Verifica si una llave se encuentra en la tabla de simbolos.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos en la cual se desea verificar si la llave se encuentra.
key (any) – Llave que se desea verificar si se encuentra en la tabla.

Returns:

True si la llave se encuentra en la tabla, False en caso contrario.

Return type:

bool

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})

# Verificar si la llave 1 se encuentra en la tabla
print(msc.contains(my_table, 1))
# Salida esperada: True

# Verificar si la llave 2 se encuentra en la tabla
print(msc.contains(my_table, 2))
# Salida esperada: False

remove(my_map, key)

Elimina una entrada de la tabla de simbolos asociada a una llave dada.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos de la cual se desea eliminar una entrada.
key (any) – Llave de la entrada que se desea eliminar.

Returns:

Tabla de simbolos con la entrada eliminada.

Return type:

map_separate_chaining

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': {
#                   'info': {
#                      'key': 4,
#                      'value': {
#                         'name': 'Mary',
#                         'age': 20
#                      }
#                   },
#                   'next': None
#                }
#             },
#             'last': {
#                'info': {
#                   'key': 4,
#                   'value': {
#                      'name': 'Mary',
#                      'age': 20
#                   }
#                },
#                'next': None
#             },
#             'size': 2
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': {
#                   'info': {
#                   'key': 3,
#                   'value': {
#                      'name': 'Doe',
#                      'age': 30
#                   }
#                   },
#                   'next': None
#                }
#             },
#             'last': {
#                'info': {
#                   'key': 3,
#                   'value': {
#                      'name': 'Doe',
#                      'age': 30
#                   }
#                },
#                'next': None
#             },
#             'size': 2
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 2.0,
#    'limit_factor': 4,
#    'size': 4
# }

# Eliminar la entrada asociada a la llave 1
my_table = msc.remove(my_table, 1)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
   'table': {
      'elements': [
         {
            'first': {
               'info': {
                  'key': 4,
                  'value': {
                     'name': 'Mary',
                     'age': 20
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 4,
                  'value': {
                     'name': 'Mary',
                     'age': 20
                  }
               },
               'next': None
            },
            'size': 1
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': {
                  'info': {
                     'key': 3,
                     'value': {
                        'name': 'Doe',
                        'age': 30
                     }
                  },
                  'next': None
               }
            },
            'last': {
               'info': {
                  'key': 3,
                  'value': {
                     'name': 'Doe',
                     'age': 30
                  }
               },
               'next': None
            },
            'size': 2
         }
      ],
      'size': 2
   },
   'current_factor': 2.0,
   'limit_factor': 4,
   'size': 3
}

Test Scenarios:

Elimina por llave existente: Se elimina un elemento de la tabla.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Eliminar la entrada asociada a la llave 1
my_table = msc.remove(my_table, 1)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'first': None,
            'last': None,
            'size': 0
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'size': 1
         }
      ],
      'size': 2
   },
   'current_factor': 1.0,
   'limit_factor': 4,
   'size': 1
}

Elimina por llave inexistente: Se intenta eliminar un elemento de la tabla que no existe.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       '
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Eliminar la entrada asociada a la llave 3
my_table = msc.remove(my_table, 3)
print(my_table)
# Salida esperada a continuación

Salida esperada:

{
   'prime': 109345121,
   'capacity': 2,
   'scale': 1,
   'shift': 0,
   'table': {
      'elements': [
         {
            'first': {
               'info': {
                  'key': 2,
                  'value': {
                     'name': 'Jane',
                     'age': 22
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 2,
                  'value': {
                     'name': 'Jane',
                     'age': 22
                  }
               },
               'next': None
            },
            'size': 1
         },
         {
            'first': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'last': {
               'info': {
                  'key': 1,
                  'value': {
                     'name': 'John',
                     'age': 25
                  }
               },
               'next': None
            },
            'size': 1
         }
      ],
      'size': 2
   },
   'current_factor': 1.0,
   'limit_factor': 4,
   'size': 2
}

get(my_map, key)

Obtiene el valor asociado a una llave en la tabla de simbolos.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos de la cual se desea obtener el valor asociado a una llave.
key (any) – Llave de la cual se desea obtener el valor asociado.

Returns:

Valor asociado a la llave en la tabla de simbolos.

Return type:

any

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'table': {
#       'elements': [
#          {
#             'first': None,
#             'last': None,
#             'size': 0
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 0.5,
#    'limit_factor': 4,
#    'size': 1
# }

# Obtener el valor asociado a la llave 1
print(msc.get(my_table, 1))
# Salida esperada: {'name': 'John', 'age': 25}

# Obtener el valor asociado a la llave 2
print(msc.get(my_table, 2))
# Salida esperada: None

Test Scenarios:

Obtener valor por llave existente: Se obtiene el valor asociado a una llave existente.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Obtener el valor asociado a la llave 1
print(msc.get(my_table, 1))
# Salida esperada: {'name': 'John', 'age': 25}

Obtener valor por llave inexistente: Se intenta obtener el valor asociado a una llave inexistente.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Obtener el valor asociado a la llave 3
print(msc.get(my_table, 3))
# Salida esperada: None

size(my_map)

Obtiene la cantidad de elementos en la tabla de simbolos.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos de la cual se desea obtener la cantidad de elementos.

Returns:

Cantidad de elementos en la tabla de simbolos.

Return type:

int

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'shift': 0, # (ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
#    'table': {
#       'elements': [
#          {
#             'first': None,
#             'last': None,
#             'size': 0
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 0.5,
#    'limit_factor': 4,
#    'size': 1
# }

# Obtener la cantidad de elementos en la tabla
print(msc.size(my_table))
# Salida esperada: 1

Test Scenarios:

Obtener cantidad de elementos en tabla vacia: Se obtiene la cantidad de elementos en una tabla vacia.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Obtener la cantidad de elementos en la tabla
print(msc.size(my_table))
# Salida esperada: 0

Obtener cantidad de elementos en tabla con elementos: Se obtiene la cantidad de elementos en una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Obtener la cantidad de elementos en la tabla
print(msc.size(my_table))
# Salida esperada: 2

is_empty(my_map)

Verifica si la tabla de simbolos se encuentra vacia.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos de la cual se desea verificar si se encuentra vacia.

Returns:

True si la tabla se encuentra vacia, False en caso contrario.

Return type:

bool

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Verificar si la tabla está vacía
print(ml.is_empty(my_table))
# Salida esperada: True

Test Scenarios:

Tabla vacía: Se verifica si una tabla vacía está vacía.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Verificar si la tabla está vacía
print(msc.is_empty(my_table))
# Salida esperada: True

Tabla con elementos: Se verifica si una tabla con elementos está vacía.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar un nuevo elemento a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})

# Verificar si la tabla está vacía
print(msc.is_empty(my_table))
# Salida esperada: False

key_set(my_map)

Obtiene la lista de llaves de la tabla de simbolos.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos de la cual se desea obtener el conjunto de llaves.

Returns:

Lista de llaves de la tabla de simbolos.

Return type:

array_list

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': {
#                   'info': {
#                   'key': 4,
#                   'value': {
#                      'name': 'Mary',
#                      'age': 20
#                   }
#                   },
#                   'next': None
#                }
#             },
#             'last': {
#                'info': {
#                   'key': 4,
#                   'value': {
#                   'name': 'Mary',
#                   'age': 20
#                   }
#                },
#                'next': None
#             },
#             'size': 2
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                   'name': 'John',
#                   'age': 25
#                   }
#                },
#                'next': {
#                   'info': {
#                   'key': 3,
#                   'value': {
#                      'name': 'Doe',
#                      'age': 30
#                   }
#                   },
#                   'next': None
#                }
#             },
#             'last': {
#                'info': {
#                   'key': 3,
#                   'value': {
#                   'name': 'Doe',
#                   'age': 30
#                   }
#                },
#                'next': None
#             },
#             'size': 2
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 2.0,
#    'limit_factor': 4,
#    'size': 4
# }

# Obtener la lista de llaves de la tabla
print(msc.key_set(my_table))
# Salida esperada: {'elements': [2, 4, 1, 3], 'size': 4}

Test Scenarios:

Tabla vacía: Se obtiene la lista de llaves de una tabla vacía.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Obtener la lista de llaves de la tabla
print(msc.key_set(my_table))
# Salida esperada: {'elements': [], 'size': 0}

Tabla con elementos: Se obtiene la lista de llaves de una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Obtener la lista de llaves de la tabla
print(msc.key_set(my_table))
# Salida esperada: {'elements': [2, 1], 'size': 2}

value_set(my_map)

Obtiene la lista de valores de la tabla de simbolos.

Parameters:

my_map (map_separate_chaining) – Tabla de simbolos de la cual se desea obtener el conjunto de valores.

Returns:

Lista de valores de la tabla de simbolos.

Return type:

array_list

Example:

Importante

Para asegurar obtener los mismos resultados en los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

# Crear una tabla vacia
my_table = msc.new_map(5, 4)
print(my_table)
# Salida esperada la misma respuesta de la función new_map()

# Agregar un nuevo elemento a la tabla
my_table = ml.put(my_table, 1, {'name': 'John', 'age': 25})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': None,
#             'last': None,
#             'size': 0
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 0.5,
#    'limit_factor': 4,
#    'size': 1
# }

# Obtener la lista de valores de la tabla
print(msc.value_set(my_table))
# Salida esperada: {'elements': [{'name': 'John', 'age': 25}], 'size': 1}

Test Scenarios:

Tabla vacía: Se obtiene la lista de valores de una tabla vacía.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Obtener la lista de valores de la tabla
print(msc.value_set(my_table))
# Salida esperada: {'elements': [], 'size': 0}

Tabla con elementos: Se obtiene la lista de valores de una tabla con elementos.

# App/logic.py
from DataStructures.Map import map_separate_chaining as msc

my_table = msc.new_map(5, 4)
print(my_table) # Se espera la misma respuesta de new_map()

# Agregar varios elementos a la tabla
my_table = msc.put(my_table, 1, {'name': 'John', 'age': 25})
my_table = msc.put(my_table, 2, {'name': 'Jane', 'age': 22})
print(my_table)
# Salida esperada:
# {
#    'prime': 109345121,
#    'capacity': 2,
#    'scale': 1,
#    'shift': 0,
#    'table': {
#       'elements': [
#          {
#             'first': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 2,
#                   'value': {
#                      'name': 'Jane',
#                      'age': 22
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          },
#          {
#             'first': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'last': {
#                'info': {
#                   'key': 1,
#                   'value': {
#                      'name': 'John',
#                      'age': 25
#                   }
#                },
#                'next': None
#             },
#             'size': 1
#          }
#       ],
#       'size': 2
#    },
#    'current_factor': 1.0,
#    'limit_factor': 4,
#    'size': 2
# }

# Obtener la lista de valores de la tabla
print(msc.value_set(my_table))
# Salida esperada: {'elements': [{'name': 'Jane', 'age': 22}, {'name': 'John', 'age': 25}], 'size': 2}

rehash(my_map)

Realiza un rehashing de la tabla de simbolos.

Para realizar un rehash se debe seguir los siguientes pasos:

Crear una nueva tabla map_separate_chaining con capacity que sea el siguiente primo al doble del capacity actual.

Recorrer la tabla actual y reinsertar cada elemento en la nueva tabla.

Asignar la nueva tabla como la tabla actual.

Retornar la tabla nueva.

Parameters:: my_map (map_separate_chaining) – Tabla de simbolos a la cual se le desea realizar un rehashing.
Returns:: Tabla de simbolos con un nuevo tamaño.
Return type:: map_separate_chaining