Nederlands
Menu

Datastructuren en algoritmen

Welke beschrijving van een botsing (collision) in een hashtabel is juist?

  1. AUit een hashwaarde kan de oorspronkelijke sleutel worden afgeleid
  2. BVerschillende sleutels leveren dezelfde hashwaarde (opslagpositie) op
  3. CDezelfde sleutel levert bij elke uitvoering een andere hashwaarde op
Antwoord en toelichting tonen

Antwoord: B. Verschillende sleutels leveren dezelfde hashwaarde (opslagpositie) op

Een hashtabel is een datastructuur die met een hashfunctie uit de sleutel een opslagpositie berekent, waardoor zoeken, invoegen en verwijderen gemiddeld O(1) kosten. Er zijn veel meer mogelijke sleutels dan posities in de tabel, dus dat verschillende sleutels op dezelfde positie uitkomen (een botsing), is onvermijdelijk. Botsingen worden daarom afgehandeld met methoden zoals chaining, die de elementen op dezelfde positie tot een lijst koppelt, of open adressering, die een andere vrije positie zoekt. Dezelfde sleutel moet altijd dezelfde hashwaarde opleveren, anders kan er niet worden gezocht. Of de sleutel uit de hashwaarde kan worden afgeleid, is een eigenschap die bij cryptografisch gebruik telt en heeft niets met botsingen te maken.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. De sleutels 10, 17, 24 en 3 worden in deze volgorde opgeslagen in een hashtabel van grootte 7 (posities 0 tot 6) met de hashfunctie h(k) = k mod 7. Botsingen worden opgelost met lineair proberen (linear probing): de positie schuift telkens één plaats op (na 6 komt 0) tot er een vrije plaats is gevonden. Op welke positie wordt sleutel 3 opgeslagen?
  2. Welke vergelijking van chaining (de elementen op dezelfde positie aan elkaar koppelen in een gelinkte lijst) en open adressering (een andere vrije positie in de tabel zoeken) als methoden om botsingen in een hashtabel af te handelen is juist? De bezettingsgraad (load factor) is het aantal opgeslagen elementen gedeeld door de grootte van de tabel.
  3. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?
  4. Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?
  5. Binair zoeken zoekt 38 in de oplopende array a[0] tot a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Het zoekbereik begint met lo = 0 en hi = 9, en de middelste positie is (lo + hi) ÷ 2, naar beneden afgerond. Welke reeks geeft, in volgorde, de waarden van de elementen waarmee 38 wordt vergeleken?