Hallo zusammen!
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; } }