Hashtabellen

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Definition

Speichert eine Sammlung von Einträgen

Schlüssel-Wert-Paare

  lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

Fast jede Programmiersprache hat eine eingebaute Hashtabelle:
- hashes, Hash-Maps, Dictionaries, assoziative Arrays
- Python: Dictionaries

Struktur

Jede Position: Slot/Bucket

Schematische Darstellung einer leeren Hashtabelle.

Hashfunktionen

Schematische Darstellung einer leeren Hashtabelle. Der Preis der Lasagna wurde an der fünften Position eingefügt.

Hashfunktionen

Schematische Darstellung einer Hashtabelle mit den Wörtern „Hash function“ in der Mitte eines Pfeils, der „Lasagna“ dem Wert an der fünften Position zuordnet.

Jedes Mal, wenn eine Hashfunktion angewendet wird
- muss sie für dieselbe Eingabe denselben Wert liefern

Nachschlagen

Schematische Darstellung einer Hashtabelle mit einigen Werten.

Finde „lasagna“
- hash("lasagna") -> 5

Nachschlagen

Schematische Darstellung einer Hashtabelle mit einigen Werten. Der Wert an der fünften Position ist grün markiert.

Finde „lasagna“
- hash("lasagna") -> 5
- gibt 14,75 zurück
$O(1)$

Kollisionen

Hashfunktionen können für verschiedene Eingaben dieselbe Ausgabe liefern
hash("moussaka") -> 1

Schematische Darstellung einer Hashtabelle mit einigen Werten. Der Wert an der ersten Position ist gelb markiert.

einfügen: moussaka -> 21,15
Kollision!
- muss gelöst werden
- mehrere Techniken

Python-Dictionary

Leeres Dictionary

my_empty_dictionary = {}

Dictionary mit Einträgen

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

Python-Dictionary – 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

Python-Dictionary – items, keys & values

Einträge abrufen

print(my_menu.items())

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

Schlüssel abrufen

print(my_menu.keys())

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

Werte abrufen

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Python-Dictionary – einfügen

my_menu['samosas'] = 13

print(my_menu.items())

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

Python-Dictionary – ändern

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

Python-Dictionary – entfernen

Löscht ein Dictionary komplett

del my_menu

Entfernt ein Schlüssel-Wert-Paar

del my_menu["sushi"]

Leert ein Dictionary

my_menu.clear()

Python-Dictionary – iterieren

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

Python-Dictionary – iterieren

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05

Python-Dictionary – verschachtelte Dictionaries

Verschachteltes Dictionary

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

Lass uns üben!

Datenstrukturen und Algorithmen in Python