Løsningsforslag - oppgaver i Avsnitt 6.1.6


Oppgave 1, 2 og 3

En fullstendig klasse ligger på KvadratiskHashTabell.

Oppgave 4

Dette kan gjøres på en enkel måte ved at metoden leggInn() starter med et kall på inneholder(). Det fører imidlertid til en del dobbeltarbeid i de (meste vanlige) tilfellene at det det ikke er et duplikat. Det å lage en bedre versjon overlates til leseren.

  // enkel versjon
  public boolean leggInn(T verdi)
  {
    Objects.requireNonNull(verdi, "verdi er null!");    // sjekker verdi
    if (inneholder(verdi)) return false;                // duplikat

    if (antall >= grense) utvid();                      // utvider

    int hverdi = verdi.hashCode() & 0x7fffffff;         // fjerner fortegn
    int dim = hash.length;                              // tabellens dimensjon
    int h = hverdi % hash.length;                       // hashindeks

    HashObjekt<T> o = new HashObjekt<>(verdi, hverdi);  // nytt objekt
    leggInn(o, h);                                      // legger inn

    antall++;                                           // øker antallet
    endringer++;                                        // en endring
    return true;                                        // vellykket innlegging
  }

Oppgave 5

Se LenketKvadratiskHashTabell.