Tabele hash

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Definiție

  • Stochează o colecție de elemente

  • Perechi cheie-valoare

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • Aproape orice limbaj de programare are un tabel hash integrat:

    • hashes, hash maps, dicționare, tablouri asociative
    • Python: dicționare
Structuri de date și algoritmi în Python

Structură

  • Fiecare poziție: slot/bucket

Reprezentare schematică a unui tabel hash gol.

Structuri de date și algoritmi în Python

Funcții hash

Reprezentare schematică a unui tabel hash gol. Prețul lasagnei a fost inserat pe poziția a cincea.

Structuri de date și algoritmi în Python

Funcții hash

Reprezentare schematică a unui tabel hash cu textul „Funcție hash" în mijlocul unei săgeți care asociază cuvântul „Lasagna" cu valoarea de pe poziția a cincea.

  • La fiecare aplicare a funcției hash
    • trebuie returnată aceeași valoare pentru aceeași intrare
Structuri de date și algoritmi în Python

Căutări

Reprezentare schematică a unui tabel hash cu câteva valori.

  • Căutare „lasagna"
    • hash("lasagna") -> 5
Structuri de date și algoritmi în Python

Căutări

Reprezentare schematică a unui tabel hash cu câteva valori. Valoarea de pe poziția a cincea este colorată cu verde.

  • Căutare „lasagna"
    • hash("lasagna") -> 5
    • returnează 14,75
  • $O(1)$
Structuri de date și algoritmi în Python

Coliziuni

  • Funcțiile hash pot returna aceeași ieșire pentru intrări diferite
  • hash("moussaka") -> 1

Reprezentare schematică a unui tabel hash cu câteva valori. Valoarea de pe prima poziție este colorată cu galben.

  • inserare: moussaka -> 21,15
  • Coliziune!
    • trebuie rezolvată
    • mai multe tehnici
Structuri de date și algoritmi în Python

Dicționarul Python

  • Dicționar gol
my_empty_dictionary = {}
  • Dicționar cu elemente
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Structuri de date și algoritmi în Python

Dicționar 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
Structuri de date și algoritmi în Python

Dicționar Python - items, keys & values

  • Obținere elemente
print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])
  • Obținere chei
print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])
  • Obținere valori
print(my_menu.values())

dict_values([14.75, 21.15, 16.05])
Structuri de date și algoritmi în Python

Dicționar Python - inserare

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Structuri de date și algoritmi în Python

Dicționar Python - modificare

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Structuri de date și algoritmi în Python

Dicționar Python - ștergere

  • Șterge complet un dicționar
del my_menu
  • Elimină o pereche cheie-valoare
del my_menu["sushi"]
  • Golește un dicționar
my_menu.clear()
Structuri de date și algoritmi în Python

Dicționar Python - iterare

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
Structuri de date și algoritmi în Python

Dicționar Python - iterare

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05
Structuri de date și algoritmi în Python

Dicționar Python - dicționare imbricate

  • Dicționar imbricat
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...