Aufgabe 8 – Algorithmik Praktikum

In diesem Teil des Praktikums war es Aufgabe das Dreieckszahlen-Hashing mit der Sondierungsfolge 0, 1, 3, 6, 10,… zu implementieren. Dazu sollte das Programm eine Ausgabe mit dem momentanen Füllgrad und der Anzahl an Clustern enthalten, sowie einen Performancetest.

Die Ausgabe auf der Konsole sieht mit dem fertigem Programm folgendermaßen aus:

Hier der Programmcode dazu:

import java.util.Random;

public class Three_hashing{

public static int hash(int zahl, int groesse){
  int temp;
temp = zahl%groesse;
return temp;
}

public static int hash2(int zahl, int cnt, int groesse){
  int temp;
temp = (int) ((zahl+0.5*cnt+0.5*(cnt*cnt))%groesse);
return temp;
}

public static void hashInsert(int groesse, int array[], int arrayZuf[], int fillState, int fillStatePrev){
Random r = new Random();
int z=groesse*4;

for(int i=fillStatePrev; i<fillState; i++){
int zahl=0;
boolean tempend = true;

//Generierung von Zufallszahlen und Überprüfung, dass keine doppelt vorkommt
while(tempend){
zahl = r.nextInt(z);
if(zahl!=0 ){
for(int x=0; x<arrayZuf.length; x++){
if(arrayZuf[x]!=zahl){
arrayZuf[x]=zahl;
tempend=false;
x=arrayZuf.length;
}
}
}
}

//Berechnung der Speicherstelle im Array => Hashing
boolean end = true;
int cnt=0;
int hashKey = hash(zahl, groesse);

if(array[hashKey]==0){
array[hashKey]=zahl;
}
else{
while(end){
cnt++;
int hashKey2=hash2(hashKey, cnt, groesse);
if(array[hashKey2]==0){
array[hashKey2]=zahl;
end = false;
}
}
}
}
}

public static int hashSearch(int groesse, int array[], int fillState){
  Random r = new Random();
int zaehler=0;
int temparray[] = new int[fillState];
int z=groesse*4;

for(int i=0; i<fillState; i++){
int zahl=0;
boolean tempend = true;

//Generierung von Zufallszahlen und Überprüfung, dass keine doppelt vorkommt
while(tempend){
zahl = r.nextInt(z);
if(zahl!=0 ){
for(int x=0; x<temparray.length; x++){
if(temparray[x]!=zahl){
temparray[x]=zahl;
tempend=false;
}
}
}
}

//Berechnung der Speicherstelle im Array => Hashing
boolean end = true;
int cnt=0;
int cnt2=0;
int hashKey = hash(zahl, groesse);

if(array[hashKey]==0 || array[hashKey]==zahl){
zaehler++;
}
else{
while(end){
if(cnt2>groesse){
end = false;
}
cnt++;
int hashKey2=hash2(hashKey, cnt, groesse);
if(array[hashKey2]==0 || array[hashKey2]==zahl){
zaehler++;
end = false;
}
else{
zaehler++;
}
cnt2++;
}
}
}
return zaehler;
}

public static void main(String[] args){
  double groesse=128;
int counter=10;
int counterC=0;
double Cn=0;
double Cn1=0;
double a=0;
int Hash_array[] = new int[(int) groesse];
int Zuf_array[] = new int[(int) groesse];
int fillStatePrevTemp=0;

while(counter<=99){
int counter2=0;

int fillStateTemp=(int) Math.round((groesse/100)*counter);
hashInsert((int) groesse, Hash_array, Zuf_array, fillStateTemp, fillStatePrevTemp);
fillStatePrevTemp=fillStateTemp;

//Performancetest
counterC=hashSearch((int) groesse, Hash_array, 64);
counterC=(counterC/64);

//Anzeige Konsole
System.out.print(counter+”% “);

//Anzeige von befüllten Arrayfeldern!
for(int j=0; j<Hash_array.length; j++){
if(Hash_array[j]!=0){
System.out.print(“|”);
}
else{
System.out.print(” “);
}
}

//Zählen der vorhandenen Cluster
int j=0;
while(j<Hash_array.length){
if(Hash_array[j]!=0){
while(j<Hash_array.length && Hash_array[j]!=0){
j++;
}
counter2++;
}
else{
while(j<Hash_array.length && Hash_array[j]==0){
j++;
}
}
}

if(Hash_array[0]!=0 && Hash_array[(int) (groesse-1)]!=0){
counter2- -;
}

//Cn und Cn’ Berechnung
a=counter/100.00;
Cn=1+Math.log(1/(1-a))-(a/2);
Cn1=(1/(1-a))-a+Math.log(1/(1-a));

System.out.print(” “+counter2);
System.out.print(” — C=”+counterC);
System.out.print(” Cn: “+Cn);
System.out.print(” Cn’: “+Cn1);
System.out.println(” “);
if(counter!=90){
counter=counter+10;
}
else{
counter=counter+9;
}
}
}
}