SS2011 Aufgabe 3 Streutabelle

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

SS2011 Aufgabe 3 Streutabelle
Hallo,

in SS2011 Aufgabe 3 a) soll in der Methode exists der Klasse Zonegeprüft werden, ob bereits mindestens ein Eintrag für einen gegebenen Streuwert vorhanden ist. Falls h größer ist als die derzeitige Größe der Streutabelle, existiert der Eintrag nicht.


Um die IP 131.188.32.30 des Servers mit der URL www2.cs.fau.de her- auszufinden, wird aus der (in zwei ArrayLists ohne null-Referenzen gespeicherten) Streutabelle einer Zone die zugeho ̈rige IP nachgeschla- gen. Kollisionen innerhalb einer Zone sollen in ArrayLists verwaltet werden (z.B. google.de und www2.cs.fau.de mit Streuwert 47). Der In- dex in der Kollisionsliste der URLs entspricht dem Index des Eintrags in der Kollisionsliste der IPs (z.B. www2.cs.fau.de ⇔ 131.188.32.30 an Index 1).

FSI-Lösungsvorschlag:

class Zone {
    private ArrayList<ArrayList<String>> urls = 
                        new ArrayList<ArrayList<String>>();
    private ArrayList<ArrayList<String>> ips = 
                        new ArrayList<ArrayList<String>>();
    public int hash (String url) {/* tricky, >=0, maybe >= urls.size() */}

    boolean exists(int h) {
	if(h >= urls.size() || urls.get(h).isEmpty())
		return false;
 
	return true;
}

1. Was genau sind Zonen?
2. warum heisst es im if-statement “>=” wobei in der Aufgabenstellung steht "falls h grösser ist als die derzeitige Größe der Streutabelle?

Liebe Grüße,
Speedy

3

1.) Das ist eine Anfgabe die in der Vorlesung vom Herrn Oster vorgestellt wurde.

2.) Aufgabenstellung meint vermutlich >=, denn h ist >=0, weshalb garantiert bei 0 mit der indizierung in der Hashtabelle begonnen wird.
Das heißt, wenn h == Größe der arrayList, dann könnte man auf den Index nicht zugreifen, da der größte Index == Größe der ArrayList-1;

3.) Was eine Zone ist ist irrelevant für die Aufgabe…Meint vermutlich den Zuständigkeitsbereich des Domainservers