Słowniki - tablice mieszające

1. Czym jest słownik?

Słownik (dictionary, dict) to struktura danych przechowująca pary klucz-wartość. W innych językach nazywany tablicą asocjacyjną lub mapą.

Kluczowe cechy słownika:

  • Nieuporządkowany (przed Pythonem 3.7) lub uporządkowany (Python 3.7+)
  • Mutowalny – można dodawać, usuwać i modyfikować elementy
  • Klucze unikalne – każdy klucz może wystąpić tylko raz
  • Szybkie wyszukiwanie – O(1) dzięki haszowaniu
  • Klucze hashowalne – klucze muszą być niemutowalne (string, int, tuple)

2. Tworzenie słowników

2.1. Podstawowa składnia

2.2. Konstruktor dict()

2.3. Dictionary comprehension

3. Dostęp do wartości

3.1. Dostęp przez klucz []

Uwaga: Jeśli klucz nie istnieje, wystąpi KeyError.

3.2. Metoda get() (bezpieczniejsza)

Złożoność czasowa: O(1)

4. Modyfikacja słownika

4.1. Dodawanie i aktualizacja elementów

Złożoność czasowa: O(1)

4.2. Metoda update()

5. Usuwanie elementów

5.1. del – usuń przez klucz

Wyjątek: KeyError jeśli klucz nie istnieje.

5.2. pop() – usuń i zwróć wartość

Złożoność czasowa: O(1)

5.3. popitem() – usuń ostatni element (Python 3.7+)

Uwaga: W Pythonie < 3.7 usuwa losowy element.

5.4. clear() – usuń wszystkie elementy

6. Sprawdzanie kluczy

6.1. Operator in

Złożoność czasowa: O(1)

6.2. Metoda keys()

7. Pobieranie kluczy, wartości i par

7.1. keys() – wszystkie klucze

7.2. values() – wszystkie wartości

7.3. items() – pary klucz-wartość

8. Iterowanie po słowniku

8.1. Pętla po kluczach (domyślnie)

8.2. Pętla po wartościach

8.3. Pętla po parach klucz-wartość

9. Metoda setdefault()

Zwraca wartość klucza. Jeśli klucz nie istnieje, dodaje go z wartością domyślną.

Zastosowanie: Liczenie wystąpień

10. defaultdict – słownik z wartością domyślną

Moduł collections oferuje defaultdict, który automatycznie tworzy wartości domyślne.

Inne typy domyślne:

11. Counter – zliczanie elementów

Counter to wyspecjalizowany słownik do zliczania hashable obiektów.

12. Zagnieżdżone słowniki

13. Haszowanie i wydajność

13.1. Jak działa słownik?

Słowniki w Pythonie używają tablic mieszających (hash tables):

  1. Haszowanie klucza: Klucz jest przekształcany na liczbę (hash).
  2. Indeksowanie: Hash określa pozycję w tablicy.
  3. Rozwiązywanie kolizji: Jeśli dwa klucze mają ten sam hash, Python używa dodatkowej logiki.

Uwaga: Tylko hashowalne obiekty mogą być kluczami.

13.2. Hashowalne vs niehashowalne

Hashowalne (mogą być kluczami): - int, float, str, tuple, frozenset, bool, None

Niehashowalne (NIE mogą być kluczami): - list, dict, set

14. Złożoność czasowa operacji na słownikach

Operacja Średnia Najgorszy
slownik[klucz] O(1) O(n)
slownik[klucz] = x O(1) O(n)
del slownik[klucz] O(1) O(n)
klucz in slownik O(1) O(n)
slownik.get(klucz) O(1) O(n)
len(slownik) O(1) O(1)

Uwaga: Najgorszy przypadek O(n) zdarza się bardzo rzadko (kolizje hashów).

15. Praktyczne zastosowania

15.1. Liczenie wystąpień słów

15.2. Grupowanie danych

15.3. Cache (pamięć podręczna)

15.4. Tłumaczenie wartości

16. Słownik vs lista

Kiedy używać słownika?

  • Szybkie wyszukiwanie po kluczu (O(1) vs O(n))
  • Pary klucz-wartość (np. konfiguracja, cache)
  • Unikalne klucze

Kiedy używać listy?

  • Zachowanie kolejności (choć słowniki w Python 3.7+ też są uporządkowane)
  • Dostęp po indeksie numerycznym
  • Dane bez naturalnego klucza

Porównanie wydajności:

17. Najczęstsze błędy

Błąd 1: Niehashowalne klucze

Błąd 2: KeyError przy dostępie

Błąd 3: Modyfikacja słownika podczas iteracji

18. Nowoczesne funkcje (Python 3.9+)

18.1. Operator | do łączenia słowników

18.2. Operator |= do aktualizacji

19. Podsumowanie

Słowniki to jedna z najpotężniejszych struktur danych w Pythonie:

  • Szybkie wyszukiwanie: O(1)
  • Elastyczne klucze (dowolny hashable typ)
  • Idealne do mapowania klucz-wartość
  • Wbudowane optymalizacje (tablice mieszające)

Kluczowe metody:

  • get(), setdefault() – bezpieczny dostęp
  • keys(), values(), items() – iterowanie
  • update(), pop(), popitem() – modyfikacja

Co dalej warto poznać:

  • defaultdict, Counter, OrderedDict (moduł collections)
  • Zbiory (set) – podobne do słowników bez wartości
  • ChainMap – łączenie wielu słowników
  • Wydajność haszowania w praktyce
Wróć do spisu lekcji