Vertel over hash-tabellen en hun belangrijkste…

De hashtabel (hashmap) is een datastructuur die een associatief array implementeert, waarbij sleutels worden gekoppeld aan waarden.

Werking:

Hashing: Voor elke sleutel wordt een hash-code berekend — een vaste numerieke waarde met behulp van een hashfunctie. Een goede hashfunctie verdeelt de hash-codes gelijkmatig over het outputbereik.
Indexering: De berekende hash-code wordt gebruikt om de index (positie) in de array te bepalen waar de bijbehorende waarde wordt opgeslagen. Vaak geeft hash(key) % array_grootte de uiteindelijke index.
Opslag: In de array wordt op de berekende index een paar (sleutel, waarde) opgeslagen.
Zoeken: Om een waarde te vinden op basis van de sleutel, wordt de hash-code van de sleutel opnieuw berekend, wordt de index bepaald, en wordt op die index de waarde opgehaald.
Botsingen: Ontstaan wanneer verschillende sleutels dezelfde hash-code hebben. Er zijn verschillende methoden om botsingen op te lossen:
- Separate Chaining: Op elke index van de array wordt een lijst (of andere datastructuur) gehouden met alle paren (sleutel, waarde) waarvan de hash-codes naar die index leiden.
- Open Addressing: Bij een botsing wordt gezocht naar een ander vrij plaatsje in de array volgens een bepaalde regel (lineair, kwadratisch, dubbele hashing).

Voordelen:

Gemiddeld hebben invoeg-, verwijder- en zoekbewerkingen een complexiteit van O(1), mits de hashfunctie goed is en botsingen zeldzaam.

Nadelen:

In het slechtste geval kan de prestatie O(n) zijn, als alle sleutels op dezelfde index worden gehasht (bijvoorbeeld bij een slechte hashfunctie of veel botsingen).
Extra geheugen is nodig voor de array en mogelijk voor het oplossen van botsingen.

In Swift worden hash-tabellen geïmplementeerd met het type Dictionary.

// Voorbeeld van gebruik van Dictionary in Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Toegang via sleutel
let value = myDictionary["banana"] // Krijgt Optional(2)

// Toevoegen/bijwerken
myDictionary["grape"] = 4 // Voegt een nieuw paar toe
myDictionary["apple"] = 10 // Werk de waarde bij voor de sleutel "apple"

// Verwijderen
myDictionary["orange"] = nil // Verwijdert het paar met sleutel "orange"

Vertel over hash-tabellen en hun belangrijkste werkingsprincipe.