Oppgave 1
Flg. versjon av LenketHashTabell inneholder det som det er bedt om i Oppgave 1:
package hjelpeklasser; import java.util.*; public class LenketHashTabell<T> // implements Beholder<T> { private static class Node<T> // en indre nodeklasse { private final T verdi; // nodens verdi private final int hashverdi; // lagrer hashverdien private Node<T> neste; // peker til neste node private Node(T verdi, int hashverdi, Node<T> neste) // konstruktør { this.verdi = verdi; this.hashverdi = hashverdi; this.neste = neste; } } // class Node private Node<T>[] hash; // en nodetabell private final float tetthet; // eng: loadfactor private int grense; // eng: threshold (norsk: terskel) private int antall; // antall verdier @SuppressWarnings({"rawtypes","unchecked"}) // en annotasjon public LenketHashTabell(int dimensjon) // konstruktør { if (dimensjon < 0) throw new IllegalArgumentException("Negativ dimensjon!"); hash = new Node[dimensjon]; // bruker raw type tetthet = 0.75f; // maksimalt 75% full grense = (int)(tetthet * hash.length); // gjør om til int antall = 0; // foreløpig ingen verdier } public LenketHashTabell() // standardkonstruktør { this(13); // velger 13 som startdimensjon inntil videre } public int antall() { return antall; } public boolean tom() { return antall == 0; } public boolean leggInn(T verdi) { Objects.requireNonNull(verdi, "verdi er null!"); if (antall >= grense) { // her skal metoden utvid() kalles, men det tas opp senere } int hashverdi = verdi.hashCode() & 0x7fffffff; // fjerner fortegn int indeks = hashverdi % hash.length; // finner indeksen // legger inn først i listen som hører til indeks hash[indeks] = new Node<>(verdi, hashverdi, hash[indeks]); // lagrer hashverdi antall++; // en ny verdi return true; // vellykket innlegging } @Override public String toString() { StringJoiner s = new StringJoiner(", ", "[", "]"); for (Node<T> p : hash) // går gjennom tabellen { for (; p != null; p = p.neste) // går gjennom listen { s.add(p.verdi.toString()); } } return s.toString(); } } // class LenketHashTabell
Oppgave 2
Flg. versjon av LenketHashTabell inneholder det som det er bedt om i Oppgave 2:
package hjelpeklasser; import java.util.*; public class LenketHashTabell<T> implements Beholder<T> { private static class Node<T> // en indre nodeklasse { private final T verdi; // nodens verdi private final int hashverdi; // lagrer hashverdien private Node<T> neste; // peker til neste node private Node(T verdi, int hashverdi, Node<T> neste) // konstruktør { this.verdi = verdi; this.hashverdi = hashverdi; this.neste = neste; } } // class Node private Node<T>[] hash; // en nodetabell private final float tetthet; // eng: loadfactor private int grense; // eng: threshold (norsk: terskel) private int antall; // antall verdier @SuppressWarnings({"rawtypes","unchecked"}) // en annotasjon public LenketHashTabell(int dimensjon) // konstruktør { if (dimensjon < 0) throw new IllegalArgumentException("Negativ dimensjon!"); hash = new Node[dimensjon]; // bruker raw type tetthet = 0.75f; // maksimalt 75% full grense = (int)(tetthet * hash.length); // gjør om til int antall = 0; // foreløpig ingen verdier } public LenketHashTabell() // standardkonstruktør { this(13); // velger 13 som startdimensjon inntil videre } @Override public int antall() { return antall; } @Override public boolean tom() { return antall == 0; } @Override public boolean leggInn(T verdi) { Objects.requireNonNull(verdi, "verdi er null!"); if (antall >= grense) { // her skal metoden utvid() kalles, men det tas opp senere } int hashverdi = verdi.hashCode() & 0x7fffffff; // fjerner fortegn int indeks = hashverdi % hash.length; // finner indeksen // legger inn først i listen som hører til indeks hash[indeks] = new Node<>(verdi, hashverdi, hash[indeks]); // lagrer hashverdi antall++; // en ny verdi return true; // vellykket innlegging } @Override public String toString() { StringJoiner s = new StringJoiner(", ", "[", "]"); for (Node<T> p : hash) // går gjennom tabellen { for (; p != null; p = p.neste) // går gjennom listen { s.add(p.verdi.toString()); } } return s.toString(); } @Override public boolean inneholder(T verdi) { throw new UnsupportedOperationException(); } @Override public boolean fjern(T verdi) { throw new UnsupportedOperationException(); } @Override public void nullstill() { throw new UnsupportedOperationException(); } @Override public Iterator<T> iterator() { throw new UnsupportedOperationException(); } } // class LenketHashTabell
Oppgave 3
Flg. versjon av LenketHashTabell inneholder det som det er bedt om i Oppgave 3:
package hjelpeklasser; import java.util.*; public class LenketHashTabell<T> implements Beholder<T> { private static final class Node<T> // en indre nodeklasse { private final T verdi; // nodens verdi private final int hashverdi; // lagrer hashverdien private Node<T> neste; // peker til neste node private Node(T verdi, int hashverdi, Node<T> neste) // konstruktør { this.verdi = verdi; this.hashverdi = hashverdi; this.neste = neste; } } // class Node private Node<T>[] hash; // en nodetabell private final float tetthet; // eng: loadfactor private int grense; // eng: threshold (norsk: terskel) private int antall; // antall verdier @SuppressWarnings({"rawtypes","unchecked"}) public LenketHashTabell(int dimensjon) // konstruktør { hash = new Node[dimensjon]; antall = 0; tetthet = 0.75f; grense = (int)(tetthet * hash.length); } public LenketHashTabell() // standardkonstruktør { this(13); // velger 13 som startdimensjon inntil videre } private void utvid() { @SuppressWarnings({"rawtypes","unchecked"}) // bruker raw type Node<T>[] nyhash = new Node[2*hash.length + 1]; // dobling + 1 for (int i = 0; i < hash.length; i++) // den gamle tabellen { Node<T> p = hash[i]; // listen til hash[i] while (p != null) // går nedover { Node<T> q = p.neste; // hjelpevariabel int nyindeks = p.hashverdi % nyhash.length; // indeks i ny tabell p.neste = nyhash[nyindeks]; // p skal legges først nyhash[nyindeks] = p; p = q; // flytter p til den neste } hash[i] = null; // nuller i den gamle } hash = nyhash; // bytter tabell grense = (int)(tetthet * hash.length); // ny grense } @Override public boolean leggInn(T verdi) { Objects.requireNonNull(verdi, "verdi er null!"); if (antall >= grense) utvid(); int hashverdi = verdi.hashCode(); int indeks = hashverdi % hash.length; hash[indeks] = new Node<>(verdi, hashverdi, hash[indeks]); antall++; return true; } @Override public int antall() { return antall; } @Override public boolean tom() { return antall == 0; } @Override public String toString() { StringJoiner sj = new StringJoiner(", ", "[", "]"); for (Node<T> p : hash) { while (p != null) { sj.add(p.verdi.toString()); p = p.neste; } } return sj.toString(); } @Override public boolean inneholder(T verdi) { throw new UnsupportedOperationException("Not supported yet."); } @Override public boolean fjern(T verdi) { throw new UnsupportedOperationException("Not supported yet."); } @Override public void nullstill() { throw new UnsupportedOperationException("Not supported yet."); } @Override public Iterator<T> iterator() { throw new UnsupportedOperationException("Not supported yet."); } } // class LenketHashTabell
Flg.kode skriver ut hashverdi % 11 og hashverdi % 23 for navnene i
Programkode 6.1.4 g)
for (String s : navn) System.out.printf("%6s",s); System.out.printf("\n"); for (String s : navn) System.out.printf("%6d",s.hashCode() % 11); System.out.printf("\n"); for (String s : navn) System.out.printf("%6d",s.hashCode() % 23); System.out.printf("\n"); // Olga Basir Ali Per Elin Siri Ole Mette Anne Åse Leif Mona Lise // 10 6 6 1 0 7 3 9 10 10 7 2 2 // 4 12 0 16 19 1 18 13 16 13 19 10 9
I flg. versjon av Programkode 6.1.4 g)
brukes 11 som startdimensjon. Videre skrives innholdet ut etter hver innlegging:
String[] navn = {"Olga","Basir","Ali","Per","Elin","Siri",
"Ole","Mette","Anne","Åse","Leif","Mona","Lise"};
LenketHashTabell<String> hashtabell = new LenketHashTabell<>(11);
for (String n : navn)
{
hashtabell.leggInn(n);
System.out.println(hashtabell);
}
// [Olga]
// [Basir, Olga]
// [Ali, Basir, Olga]
// [Per, Ali, Basir, Olga]
// [Elin, Per, Ali, Basir, Olga]
// [Elin, Per, Ali, Basir, Siri, Olga]
// [Elin, Per, Ole, Ali, Basir, Siri, Olga]
// [Elin, Per, Ole, Ali, Basir, Siri, Mette, Olga]
// [Ali, Siri, Olga, Basir, Mette, Anne, Per, Ole, Elin]
// [Ali, Siri, Olga, Basir, Åse, Mette, Anne, Per, Ole, Elin]
// [Ali, Siri, Olga, Basir, Åse, Mette, Anne, Per, Ole, Leif, Elin]
// [Ali, Siri, Olga, Mona, Basir, Åse, Mette, Anne, Per, Ole, Leif, Elin]
// [Ali, Siri, Olga, Lise, Mona, Basir, Åse, Mette, Anne, Per, Ole, Leif, Elin]
Med 11 som startdimensjon blir grense = (int)(tetthet * hash.length) = (int)(0.75 * 11) = (int)8.25 = 8.
Dermed «utvides» tabellen med ny dimensjon lik 2*11 + 1 = 23 når det niende navnet skal legges inn.
Vi ser i utskriften at da skifter det første navnet fra Elin til Ali siden Elin % 11 = 0 og Ali % 23 = 0.
Oppgave 4
public boolean inneholder(T verdi) { if (verdi == null) return false; // ingen nuller i tabellen int hashverdi = verdi.hashCode() & 0x7fffffff; // "fjerner" fortegn Node<T> p = hash[hashverdi % hash.length]; // går til rett indeks while (p != null) { if (verdi.equals(p.verdi)) return true; p = p.neste; } return false; }
Oppgave 5
public boolean fjern(T verdi) { if (verdi == null) return false; // ingen nuller i tabellen int hashverdi = verdi.hashCode() & 0x7fffffff; // "fjerner" fortegn int indeks = hashverdi % hash.length; // finner indeksen Node<T> p = hash[indeks], q = null; // går til indeks while (p != null) // går nedover { if (verdi.equals(p.verdi)) break; // verdi ligger i p p = (q = p).neste; // flytter p og q } if (p == null) return false; // fant ikke verdi else if (p == hash[indeks]) hash[indeks] = p.neste; // verdi ligger først else q.neste = p.neste; // p blir borte antall--; // en mindre return true; // vellykket fjerning }
Oppgave 6
Det normale når en «nullstiller» en liste, er å traversere og «nulle» alle pekere og verdier. Men her vil normalt de fleste listene inneholde kun én node. Derfor kan en her nøye seg med å «nulle» listens hode. Det er også normalt å sjekke om det er null eller ikke før noe «nulles», men her vil normalt flertallet av elementene ikke være null. Dermed er det mindre kostbart å «nulle» alt enn det er å sjekke om det er null på forhånd.
public void nullstill() { if (antall > 0) { antall = 0; for (int i = 0; i < hash.length; i++) hash[i] = null; } }
Oppgave 7 og 8
En fullstendig versjon av klassen ligger på LenketHashTabell.
Oppgave 9