Hashovací tabulky

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Definice

  • Ukládá kolekci položek

  • Páry klíč–hodnota

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • Téměř každý programovací jazyk má vestavěnou hashovací tabulku:

    • hash, hash mapy, slovníky, asociativní pole
    • Python: slovníky
Datové struktury a algoritmy v Pythonu

Struktura

  • Každá pozice: slot/bucket

Schematické znázornění prázdné hashovací tabulky.

Datové struktury a algoritmy v Pythonu

Hashovací funkce

Schematické znázornění prázdné hashovací tabulky. Cena lasagne byla vložena na pátou pozici.

Datové struktury a algoritmy v Pythonu

Hashovací funkce

Schematické znázornění hashovací tabulky s nápisem „Hash function" uprostřed šipky, která mapuje slovo „Lasagna" na hodnotu na páté pozici.

  • Při každém použití hashovací funkce
    • musí vrátit stejnou hodnotu pro stejný vstup
Datové struktury a algoritmy v Pythonu

Vyhledávání

Schematické znázornění hashovací tabulky s hodnotami.

  • Hledání „lasagna"
    • hash("lasagna") -> 5
Datové struktury a algoritmy v Pythonu

Vyhledávání

Schematické znázornění hashovací tabulky s hodnotami. Hodnota na páté pozici je zvýrazněna zeleně.

  • Hledání „lasagna"
    • hash("lasagna") -> 5
    • vrátí 14,75
  • $O(1)$
Datové struktury a algoritmy v Pythonu

Kolize

  • Hashovací funkce mohou vrátit stejný výstup pro různé vstupy
  • hash("moussaka") -> 1

Schematické znázornění hashovací tabulky s hodnotami. Hodnota na první pozici je zvýrazněna žlutě.

  • vložit: moussaka -> 21,15
  • Kolize!
    • je třeba ji vyřešit
    • několik technik
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu

  • Prázdný slovník
my_empty_dictionary = {}
  • Slovník s položkami
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – metoda 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
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – items, keys a values

  • Získat položky
print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])
  • Získat klíče
print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])
  • Získat hodnoty
print(my_menu.values())

dict_values([14.75, 21.15, 16.05])
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – vkládání

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – úprava

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – odstraňování

  • Smaže celý slovník
del my_menu
  • Odstraní pár klíč–hodnota
del my_menu["sushi"]
  • Vyprázdní slovník
my_menu.clear()
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – iterace

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
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – iterace

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05
Datové struktury a algoritmy v Pythonu

Slovník v Pythonu – vnořené slovníky

  • Vnořený slovník
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Datové struktury a algoritmy v Pythonu

Let's practice!

Datové struktury a algoritmy v Pythonu

Preparing Video For Download...