Svarark — Post 5 (facit)

#

Øvelse 1 — Find element

#

Hvor mange personer skulle programmøren spørge for at finde den rigtige?

Svar: 1 — programmøren råber koden og personen træder frem.

Hvad er kompleksiteten? O(1)

Ville det gøre en forskel hvis I var 1.000 personer i gruppen?

Nej — koden identificerer personen direkte. Antallet af personer er ligegyldigt.

Øvelse 2 — Indsæt element

#

Hvor mange personer blev påvirket da programmøren gik ind i gruppen?

Svar: 0 — programmøren går bare ind. Ingen andre påvirkes.

Hvad er kompleksiteten? O(1)

Ville det gøre en forskel hvis I var 1.000 personer i gruppen?

Nej — du beregner din kode og går ind. Gruppens størrelse er ligegyldig.

Øvelse 3 — Slet element

#

Hvor mange personer blev påvirket da personen forlod gruppen?

Svar: 0 — personen forlader gruppen direkte. Ingen andre påvirkes.

Hvad er kompleksiteten? O(1)

Ville det gøre en forskel hvis I var 1.000 personer i gruppen?

Nej — koden identificerer personen direkte. Gruppens størrelse er ligegyldig.

Bonusspørgsmål

#

Hvad ville ske hvis to personer i gruppen havde samme initialer og samme fødselsdato?

De ville have samme hashkode — det kaldes en kollision. Sættet kan ikke skelne dem fra hinanden, og det kan i worst case betyde at operationer ikke længere er O(1). Det er derfor implementationen er vigtig — og det tager vi på tavlen.