Tablice haszujące

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Definicja

Przechowuje kolekcję elementów

Pary klucz-wartość

  lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

Niemal każdy język programowania ma wbudowaną tablicę haszującą:
- hashe, mapy haszujące, słowniki, tablice asocjacyjne
- Python: słowniki

Struktura

Każda pozycja: slot/bucket

Schematyczna reprezentacja pustej tablicy haszującej.

Funkcje haszujące

Schematyczna reprezentacja pustej tablicy haszującej. Cena lasagne została wstawiona na piątej pozycji.

Funkcje haszujące

Schematyczna reprezentacja tablicy haszującej ze słowami "Funkcja haszująca" na środku strzałki mapującej słowo "Lasagna" na wartość na piątej pozycji.

Za każdym razem, gdy stosowana jest funkcja haszująca
- musi zwracać tę samą wartość dla tych samych danych wejściowych

Wyszukiwanie

Schematyczna reprezentacja tablicy haszującej z kilkoma wartościami.

Znajdź "lasagna"
- hash("lasagna") -> 5

Wyszukiwanie

Schematyczna reprezentacja tablicy haszującej z kilkoma wartościami. Wartość na piątej pozycji jest zaznaczona na zielono.

Znajdź "lasagna"
- hash("lasagna") -> 5
- zwróć 14,75
$O(1)$

Kolizje

Funkcje haszujące mogą zwracać ten sam wynik dla różnych danych wejściowych
hash("moussaka") -> 1

Schematyczna reprezentacja tablicy haszującej z kilkoma wartościami. Wartość na pierwszej pozycji jest zaznaczona na żółto.

wstaw: moussaka -> 21,15
Kolizja!
- wymaga rozwiązania
- kilka technik

Słownik Pythona

Pusty słownik

my_empty_dictionary = {}

Słownik z elementami

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

Słownik Pythona – 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

Słownik Pythona – items, keys i values

Pobierz elementy

print(my_menu.items())

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

Pobierz klucze

print(my_menu.keys())

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

Pobierz wartości

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Słownik Pythona – dodawanie

my_menu['samosas'] = 13

print(my_menu.items())

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

Słownik Pythona – modyfikowanie

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

Słownik Pythona – usuwanie

Usuwa cały słownik

del my_menu

Usuwa parę klucz-wartość

del my_menu["sushi"]

Czyści słownik

my_menu.clear()

Słownik Pythona – iteracja

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

Słownik Pythona – iteracja

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05

Słownik Pythona – słowniki zagnieżdżone

Zagnieżdżony słownik

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

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie