INF2220 ukeoppgaver uke 3
=========================



OPPGAVE 1:
----------


I disse oppgavene skal dere ta utgangspunkt i klassen BinaryHashMap. Den
interne strukturen i BinaryHashMap (dvs. liste-arrayen) er kun av lengde
2. Den har ogs? en veldig enkel hash-funksjon, som "hasher" alle n?kler
av oddetalls lengde til 1, og alle n?kler av partalls lengde til 0.



alle kompleksitetssp?rsm?l besvares med big-O funksjonen.


a) Hva er kompleksiteten av ? finne et element i en uordnet liste?

b) Hva er kompleksiteten av ? finne et element i BinaryHashMap dvs.

   //binHash er en BinaryHashMap
      
   Object o = binHash.get("en_n?kkel"); 


   (HINT: elementene er fordelt p? to uordnede lister)


c) Hva er kompleksiteten av ? sette inn et element i BinaryHashMap dvs.

   binHash.put("some_key", some_obj_pointer);


   (HINT: n?kler er unike, vi kan ikke bare legge elementet inn i riktig liste)


d) La M v?re antall listepekere internt i en hash-tabell, anta at hash-funksjon
   gir oss perfekt spredning. (dvs. hvis vi fyller den med M n?kkel-objekt-par
   s? har vi ingen kollisjoner, og alle listene i arrayen inneholder 1 element).
   
   Hva er kompleksiteten av ? finne et element i en slik hash-tabell dersom
   den inneholder N elementer (den har M interne listepekere)? 
   (dvs. big-O uttrykt ved N og M)



OPPGAVE 2:
----------

Her skal en implementere noen funksjoner i klassen BinaryHashMap


a) Implementer funksjonen: boolean remove(String key)

   (returner false dersom elementet ikke fantes i BinaryHashMap,
   true ellers)


b) Implementer funksjonen: String[] keys()

   som returnerer alle n?kler i BinaryHashMap


   (HINT: vi har st?rrelsen p? denne arrayen liggende i this.size)


c) Implementer funksjonen: Object[] toArray()
   

   Denne funksjonen skal returnere alle objekter fra n?kkel-OBJEKT-par