Hoofdstuk 6 Flashcards
Wat is het grootste probleem met hashtables? Hoe wordt dat verholpen?
Chaining
- Seperate chaining
- coalesced chaining
Open adressing:
- linear probing
- quadratic probing
- double hashing
Wat is linear probing? Wat probleem komt er voor bij linear probing?
Linear probing is een manier om met het principe van open addressing collisions op te vangen.
Bij linear probing ga je bij het geval van een collision gewoon het volgende slot kiezen in de hashtabel om het element te storen. als die vol zit gebeurt hetzelfde.
Dit kan ervoor zorgen dat er een lange keten aan elementen ontstaat die de performantie niet ten goede gaat zijn. (primaire clustering)
Wat is coalesced chaining?
In plaats van een linked list op te slaan in elke slot zoals bij seperate chaining, slaagt elke slot een pointer op naar een ander slot in de hashtable. Dit heeft net zoals bij open adressing het voordeel dat er geen nodes meer dynamisch moeten worden aangemaakt.
Er is ook nog een variant op coalesced chaining waarbij de tabel in een address region en berging wordt verdeeld. De collisions worden dan altijd in de berging gestoken.
