Hashtabellen

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Definitie

Slaat een verzameling items op

Key-valueparen

  lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

Bijna elke programmeertaal heeft een ingebouwde hashtabel:
- hashes, hashmaps, dictionaries, associatieve arrays
- Python: dictionaries

Structuur

Elke positie: slot/bucket

Schematische weergave van een lege hashtabel.

Hashfuncties

Schematische weergave van een lege hashtabel. De prijs van de lasagna is op de vijfde positie ingevoegd.

Hashfuncties

Schematische weergave van een hashtabel met de woorden "Hash function" in het midden van een pijl die het woord "Lasagna" koppelt aan de waarde op de vijfde positie.

Elke keer dat een hashfunctie wordt toegepast
- moet die dezelfde waarde geven voor dezelfde input

Opzoeken

Schematische weergave van een hashtabel met enkele waarden.

Zoek "lasagna"
- hash("lasagna") -> 5

Opzoeken

Schematische weergave van een hashtabel met enkele waarden. De waarde op de vijfde positie is groen gemarkeerd.

Zoek "lasagna"
- hash("lasagna") -> 5
- geef 14,75 terug
$O(1)$

Botsingen

Hashfuncties kunnen dezelfde output geven voor verschillende inputs
hash("moussaka") -> 1

Schematische weergave van een hashtabel met enkele waarden. De waarde op de eerste positie is geel gemarkeerd.

invoegen: moussaka -> 21,15
Botsing!
- moet worden opgelost
- meerdere technieken

Python-dictionary

Leeg woordenboek

my_empty_dictionary = {}

Woordenboek met items

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

Items ophalen

print(my_menu.items())

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

Sleutels ophalen

print(my_menu.keys())

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

Waarden ophalen

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Python-dictionary - invoegen

my_menu['samosas'] = 13

print(my_menu.items())

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

Python-dictionary - wijzigen

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

Python-dictionary - verwijderen

Verwijdert een dictionary volledig

del my_menu

Verwijdert een key-valuepaar

del my_menu["sushi"]

Leegt een dictionary

my_menu.clear()

Python-dictionary - itereren

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 - itereren

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 - geneste dictionaries

Genest woordenboek

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

Laten we oefenen!

Datastructuren en algoritmen in Python