[informatik_lmu] Effiziente 6.2 Programmieraufgabe
- From: Luitpold Gollas <luitpoldgollas@xxxxxx>
- To: "Email Verteiler Phillip, Teja, Andy, Stefan, Margit" <informatik_lmu@xxxxxxxxxxxxx>
- Date: Fri, 03 Jun 2005 17:06:36 +0200
Hallo zusammen!
Hier ist die "Lösung" von Aufgabe 6.2. Ich hoffe, dass es jemandem was
bringt. Getestet hab ich es nicht, weil es ja nur ein Programmausschnitt
ist, aber es müsste so schon stimmen.
Bei der 6.2 a) hab ich für die Formel:
hL (n,k) = k MOD 2^L * (n+1) * N
Schönes und erholsames Wochenende und bis Montag
package blatt6;
import java.util.Vector;
import blatt6.HashSeite;
public class HashTable {
static final int startGroesse = 4; // entspricht 2N
static final int anzahlPE = 2; // entspricht n0
static final double schwellenwert = 0.8; // wird dieser Wert
überschritten,
// muß gesplittet werden
int aktPartielleExpansion; // entspricht n
int expansionsZeiger; // entspricht p
int expansionsLevel; // entspricht L
Vector<HashSeite> primaerSeiten; // Primärseiten der Hashtabelle
// Inititalisierung einer neuen Hashtabelle
void HashTable() {
aktPartielleExpansion = 1;
expansionsZeiger = 0;
expansionsLevel = 0;
primaerSeiten = new Vector<HashSeite>();
}
boolean searchKey(int key) {
int hashFunctionNew = getHashFunction(aktPartielleExpansion,
expansionsLevel);
int hashFunctionOld;
if (aktPartielleExpansion == 1) hashFunctionOld =
getHashFunction(2, expansionsLevel-1);
else hashFunctionOld = getHashFunction(1, expansionsLevel);
int indexOfSearchedPage = key%hashFunctionNew;
int hashFunction;
if (indexOfSearchedPage%Math.pow(2, (expansionsLevel+1)) >
expansionsZeiger)
hashFunction = hashFunctionOld;
else hashFunction = hashFunctionNew;
indexOfSearchedPage = key%hashFunction;
HashSeite searchPage = primaerSeiten.get(indexOfSearchedPage);
return searchPage.durchsuche(key);
}
// Wird aufgerufen, wenn nach dem Einfügen eines Schlüssels der
Belegungsfaktor
// über 0.8 steigt. Dann wird eine neue Seite erstellt und die
Schlüssel der
// betreffenden Seiten neu verteilt
void split(int aktPartielleExp, int level, int expansionsPointer) {
int groupSize = aktPartielleExp + 1;
HashSeite pageNew = new HashSeite();
int indexNewPrimaryPage = expansionsPointer
+ (groupSize * (startGroesse/2) * (int)Math.pow(2,
level));
primaerSeiten.add(indexNewPrimaryPage, pageNew);
// nextPage: expansionsPointer + nextPage ist die im Falle
eines Splits
// als nächstes zu betrachtende Seite, deren Schlüssel
aufgeteilt werden
int nextPage = (int)Math.pow(2, level);
for (int i=0; i<groupSize; i++) {
int indexOfPageToSplit = expansionsPointer +
(i*nextPage) * (startGroesse/2);
HashSeite pageToSplit =
primaerSeiten.get(indexOfPageToSplit);
int[] keysOfPageToSplit = pageToSplit.alleSchluessel();
// Berechnung der Hashfunktion
int hashFunction = getHashFunction(aktPartielleExp,
level);
// Verschieben der Schlüssel
for(int key: keysOfPageToSplit) {
int newIndex = key%hashFunction;
if (newIndex != indexOfPageToSplit) {
pageToSplit.loesche(key);
primaerSeiten.get(newIndex).fuegeEin(key);
}
}
}
expansionsZeiger++;
// wenn alle (2^level * 2)-Seiten gesplittet wurden:
if (expansionsPointer >= Math.pow(2, level)*(startGroesse/2)) {
expansionsZeiger = 0;
if (aktPartielleExpansion == 2) expansionsLevel++;
aktPartielleExpansion = 2-((aktPartielleExp+1)%2);
}
}
// berechnet die Hashfunktion für ein gegebenes Level und einen
gegebenen
// Expansionsgrad
int getHashFunction(int actPartialExpansion, int level) {
int hashFunction;
if (actPartialExpansion == 1) hashFunction = (int)Math.pow(2,
level)*3*(startGroesse/2);
else hashFunction = (int)Math.pow(2,
level+1)*2*(startGroesse/2);
return hashFunction;
}
// liefert den aktuellen Füllungsgrad zurück
double getFuellungsgrad() {
int anzPrimaerSeiten = primaerSeiten.size();
int anzSekundaerSeiten = 0;
for (HashSeite primaerSeite: primaerSeiten)
if (primaerSeite != null)
anzSekundaerSeiten +=
primaerSeite.anzSekundaerSeiten();
int anzSchluessel = 0;
for (HashSeite seite: primaerSeiten)
anzSchluessel += seite.anzahlSchluessel();
double fuellungsGrad = anzSchluessel / (anzPrimaerSeiten * 100
+ anzSekundaerSeiten * 10);
System.out.println("Fuellungsgrad: " + fuellungsGrad);
return fuellungsGrad;
}
}
Other related posts:
