Tablas hash

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Definición

Almacena una colección de elementos

Pares clave-valor

  lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

Casi todos los lenguajes tienen tabla hash integrada:
- hashes, hash maps, diccionarios, arreglos asociativos
- Python: diccionarios

Estructura

Cada posición: slot/bucket

Representación esquemática de una tabla hash vacía.

Funciones hash

Representación esquemática de una tabla hash vacía. El precio de la lasagna se insertó en la quinta posición.

Funciones hash

Representación esquemática de una tabla hash con las palabras "Hash function" en medio de una flecha que asigna la palabra "Lasagna" al valor en la quinta posición.

Cada vez que se aplica una función hash
- debe devolver el mismo valor para la misma entrada

Búsquedas

Representación esquemática de una tabla hash con algunos valores.

Buscar "lasagna"
- hash("lasagna") -> 5

Búsquedas

Representación esquemática de una tabla hash con algunos valores. El valor en la quinta posición está en verde.

Buscar "lasagna"
- hash("lasagna") -> 5
- devuelve 14,75
$O(1)$

Colisiones

Las funciones hash pueden devolver el mismo resultado para entradas distintas
hash("moussaka") -> 1

Representación esquemática de una tabla hash con algunos valores. El valor en la primera posición está en amarillo.

insertar: moussaka -> 21,15
Colisión
- hay que resolverla
- varias técnicas

Diccionario en Python

Diccionario vacío

my_empty_dictionary = {}

Diccionario con elementos

my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}

Diccionario en Python - get

print(my_menu['sushi'])

16.05

print(my_menu['paella'])

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'paella'

print(my_menu.get('paella'))

None

Diccionario en Python - items, keys y values

Obtener elementos

print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])

Obtener claves

print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])

Obtener valores

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Diccionario en Python - insertar

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])

Diccionario en Python - modificar

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

Diccionario en Python - eliminar

Elimina un diccionario por completo

del my_menu

Quita un par clave-valor

del my_menu["sushi"]

Vacía un diccionario

my_menu.clear()

Diccionario en Python - iterar

for key, value in my_menu.items():
  print(f"\nkey: {key}")
  print(f"value: {value}")

key: lasagna
value: 14.75

key: moussaka
value: 21.15

key: sushi
value: 16.05

Diccionario en Python - iterar

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

for prices in my_menu.values():
  print(prices)

14.75
21.15
16.05

Diccionario en Python - diccionarios anidados

Diccionario anidado

my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python