Lösungsvorschläge Blatt Nr. 1
Praktische Informatik 2 im SS 2005

Aufgabe 1-1

Daten mit einer festen Länge von 120KB sollen in Dateien mit einer Blockgröße von 256KB gespeichert werden. Berechnen Sie die Blocknummer (page) und den Byte-Offset innerhalb des Blocks (offset) des sechsten abgespeicherten Datensatzes

a) bei blockbezogener Datenorganisation
b) bei blocküergreifender Datenorganisation.

Hinweis: Die Nummerierung der Blöcke und Datensätze beginne bei 0.
Gegeben: Datensatzlänge $r=120KB$, Blocksatzgröße $p=256KB$
Gesucht: Blocknummer und Byte-Offset des sechsten Datensatzes ($d=5$)

a) blockbezogene Datenorganisation

Es gilt

$\textrm{page}(d) = d \textrm{ div trunc}(\frac{p}{r}) = \textrm{page}(5) = 5 \... ...rac{256KB}{120KB}) = 5 \textrm{ div trunc}(2,1\bar{3}) = 5 \textrm{ div } 2 = 2$

und

$\textrm{offset}(d) = (d \textrm{ mod trunc}(\frac{p}{r})) * r = (5 \textrm{ mod } 2) * 120KB = 1 * 120KB = 120KB$

b) blockübergreifende Datenorganisation

Es gilt

$\textrm{page}(d) = \textrm{trunc}(\frac{d * r}{p}) = \textrm{trunc}(\frac{5*120KB}{256KB}) = \textrm{trunc}(2,34375) = 2$

und

$\textrm{offset}(d) = (d * r) \textrm{ mod } p = (5 * 120KB) \textrm{ mod } 256KB = 600KB \textrm{ mod } 256 KB = 88KB$

Aufgabe 1-2

a) In eine Hashtabelle sollen ca. 5000 Datensätze eingefügt werden. Die Größe der Hashtabelle wurde so gewählt, dass sie 5100 Datensätze aufnehmen kann. Wie beurteilen Sie unter den genannten Voraussetzungen die Größe der Hashtabelle? Was sollte man grundsätzlich bei der Verwendung einer Hashtabelle beachten?
b) Als Hashfunktion fürdie Hashtabelle aus Teilaufgabe a) wurde die Primzahl 5197 gewählt. Ist die Wahl dieser Primzahl günstig? Begründen Sie Ihre Antwort.
c) Gegeben sei nun eine Hashtabelle mit den Satznummern 0; : : : ; 4. Jeder Tabellenplatz kann genau einen Datensatz aufnehmen. Sei $pk$ der Primärschlüssel eines Datensatzes. Die Hashfunktion, die eine lineare Sondierfolge bei Kollision verwendet, sei wie folgt vorgegeben:

$hash(pk) = (pk + i) mod 5 (i = 0; 1; :::)$

Geben Sie die Belegung einer zu Anfang leeren Hashtabelle nach dem Einfügen der Datensätze mit den Primärschlüsseln 40, 31, 56, 77, 41 an. Zeichnen Sie auch die Verkettungen, die zum Auffinden der Datensätze nötig sind, in die Hashtabelle ein.

a)

Größe: 5100, Datensätze: 5000 $\Rightarrow$ Auslastung: 98% $\Rightarrow$ es kommt zu einer sehr großen Anzahl von Kollisionen, d.h. Suchaufwand extrem hoch, im Worst-Case entartet die Hash-Tabelle also zu einer linearen Liste $\Rightarrow$ lieber größere Tabelle wählen (z.B. 10000 Datensätze), dadurch zwar mehr Speicherverbrauch aber sehr viel effizienter.

b)

$\textrm{hash}(pk) := (pk + i) \textrm{ mod } 5197\quad (i=0,1,\ldots)$
Dann gilt
$\forall pk \in \{k * 5197 + n \vert k,n \in \mathbb{N}, 5101 \leq n \leq 5196 \}: \textrm{hash}(pk) > 5100$
womit die Hashfunktion nicht für alle Primärschlüssel eine gültige Stelle findet.

c)

$\textrm{hash}(pk) := (pk + i) \textrm{ mod } 5\quad (i=0,1,\ldots)$

$\textrm{hash}(40) = (40 + i) \textrm{ mod } 5 = 0,\: i=0$
$\textrm{hash}(31) = (31 + i) \textrm{ mod } 5 = 1,\: i=0$
$\textrm{hash}(56) = (56 + i) \textrm{ mod } 5 = 1,\: i=0$
$\textrm{hash}(56) = (56 + i) \textrm{ mod } 5 = 2,\: i=1$
$\textrm{hash}(77) = (77 + i) \textrm{ mod } 5 = 2,\: i=0$
$\textrm{hash}(77) = (77 + i) \textrm{ mod } 5 = 3,\: i=1$
$\textrm{hash}(41) = (41 + i) \textrm{ mod } 5 = 1,\: i=0$
$\textrm{hash}(41) = (41 + i) \textrm{ mod } 5 = 2,\: i=1$
$\textrm{hash}(41) = (41 + i) \textrm{ mod } 5 = 3,\: i=2$
$\textrm{hash}(41) = (41 + i) \textrm{ mod } 5 = 4,\: i=3$

$\Rightarrow$

0	1	2	3	4
40	31	56	77	41

Aufgabe 1-3

Beim doppelten Hashing wird bei Kollisionen durch eine zweite Hashfunktion ein Offset bestimmt, mit dem eine freie Stelle gesucht wird. Dies hat den Vorteil, dass Kollisionen besser verteilt werden.
Folgende Hashfunktion realisiert doppeltes Hashing:

$\textrm{hash}(pk)=(h_1(pk) + i * h_2(pk))\textrm{ mod } 7\quad (i=0,1,\ldots)$
$h_1(pk)=pk \textrm{ mod } 7$
$h_2(pk)=1 + (pk \textrm{ mod } 5)$

Geben Sie die Belegung einer zu Anfang leeren Hashtabelle nach dem Einfügen der Datensätze mit den Primärschlüsseln 36, 20, 57, 10, 43, 14 an. Zeichnen Sie auch die benötigten Verkettungen zum Auffinden der Datensätze in Ihre Hashtabelle ein.

$pk$	$\textrm{hash}(pk),\:i=0$	$\textrm{hash}(pk),\:i=1$
36	1 + 0*2 = 1
20	6 + 0*1 = 6
57	1 + 0*3 = 1	1 + 1*3 = 4
10	3 + 0*1 = 3
43	1 + 0*4 = 1	1 + 1*4 = 5
14	0 + 0*5 = 0

$\Rightarrow$

0	1	2	3	4	5	6
14	36		10	57	43	20