Hashtabeller

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Definition

  • Lagrar en samling objekt

  • Nyckel-värde-par

      lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

  • Nästan alla programmeringsspråk har en inbyggd hashtabell:

    • hashes, hash maps, dictionaries, associativa arrayer
    • Python: dictionaries
Datastrukturer och algoritmer i Python

Struktur

  • Varje position: slot/bucket

Schematisk bild av en tom hashtabell.

Datastrukturer och algoritmer i Python

Hashfunktioner

Schematisk bild av en tom hashtabell. Priset på lasagnen har lagts in på den femte positionen.

Datastrukturer och algoritmer i Python

Hashfunktioner

Schematisk bild av en hashtabell med texten "Hash function" i mitten av en pil som mappar ordet "Lasagna" till värdet på den femte positionen.

  • Varje gång en hashfunktion tillämpas
    • måste returnera samma värde för samma indata
Datastrukturer och algoritmer i Python

Uppslagningar

Schematisk bild av en hashtabell med några värden.

  • Hitta "lasagna"
    • hash("lasagna") -> 5
Datastrukturer och algoritmer i Python

Uppslagningar

Schematisk bild av en hashtabell med några värden. Värdet på den femte positionen är markerat i grönt.

  • Hitta "lasagna"
    • hash("lasagna") -> 5
    • returnera 14,75
  • $O(1)$
Datastrukturer och algoritmer i Python

Kollisioner

  • Hashfunktioner kan returnera samma utdata för olika indata
  • hash("moussaka") -> 1

Schematisk bild av en hashtabell med några värden. Värdet på den första positionen är markerat i gult.

  • infoga: moussaka -> 21,15
  • Kollision!
    • måste lösas
    • flera tekniker
Datastrukturer och algoritmer i Python

Python dictionary

  • Tom dictionary
my_empty_dictionary = {}
  • Dictionary med objekt
my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}
Datastrukturer och algoritmer i Python

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
Datastrukturer och algoritmer i Python

Python dictionary - items, keys & values

  • Hämta objekt
print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])
  • Hämta nycklar
print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])
  • Hämta värden
print(my_menu.values())

dict_values([14.75, 21.15, 16.05])
Datastrukturer och algoritmer i Python

Python dictionary - infoga

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])
Datastrukturer och algoritmer i Python

Python dictionary - ändra

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

20
Datastrukturer och algoritmer i Python

Python dictionary - ta bort

  • Tar bort en hel dictionary
del my_menu
  • Tar bort ett nyckel-värde-par
del my_menu["sushi"]
  • Tömmer en dictionary
my_menu.clear()
Datastrukturer och algoritmer i Python

Python dictionary - iterera

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
Datastrukturer och algoritmer i Python

Python dictionary - iterera

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

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

14.75
21.15
16.05
Datastrukturer och algoritmer i Python

Python dictionary - nästlade dictionaries

  • Nästlad dictionary
my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}
Datastrukturer och algoritmer i Python

Nu kör vi en övning!

Datastrukturer och algoritmer i Python

Preparing Video For Download...