INF2220 ukeoppgaver uke 3 (10/9-14/9)
=====================================


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

Fra l?reboka (Mark Allen Weiss): 5.1, 5.2



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

Hashtabeller er nyttige som dynamiske strukturer
og det er ikke rettferdig ? sammenligne deres 
hastighet med arrays, men heller med andre 
dynamiske strukturer som feks. lister.

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.

Kildekoden til BinaryHashMap og dens
hjelpe/test-klasser ligger i filen Main.java. 
Dette er ikke veldig langt unna en standard 
HashMap/HashTable implementasjon, og kan 
forh?pentligvis v?re til hjelp f?r Oblig1.





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 3:
----------

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