Hallo ich hab da mal ein paar fragen, wir hatten in den letzten stunden verschiedene sortieralgorithmen und jetzt haben die uns iwas zu hashfunktionen erzählt.
Eine hashfunktion wir in folgenden beispiel, sagt ja eigtl nur wie man eine bestimmte zahl findet oder? und die offene verkettung, kann ich mir wie eine art behälter vorstellen, wo alle gleichen zahlen gespeichert werden?
hier ist die aufgabe:
Gegeben sei ein Hashfeld der Länge n und eine Hash-Funktion h(x) = (x*x/2) % n. Beim Auftreten einer
Kollision wird die offene Verkettung angewendet.
a) Geben Sie die Belegung des Feldes für n = 7 nach Eintragen der Werte 10, 3, -4, 5, 1 und 11 an.
b) Wieviele Schritte sind bei der entstandenen Belegung höchstens nötig, um festzustellen, dass ein
beliebiger Wert nicht in der Tabelle enthalten ist?
c) Auf welche Größe n muss das Feld mindestens vergrößert werden, damit mit den obigen Werten
beim Eintragen keine Kollision auftritt?
d) Geben Sie für dieses n ebenfalls die dann entstehende Belegung an.
e) Wieviele Schritte benötigt eine Suche in diesem Fall maximal, um das Fehlen eines Elementes
festzustellen?
Meine Ansätze:
a) wäre ja einfach nur einzusetzen:
für h(10)=(10*10/2)%7=1
für 3 = 4,5
für -4 = 1
für 5 = 5,5
für 1 = 1
für 11 = 4
die belegung von n wäre dann:
1(3mal) , 4.5 , 5.5 , 4
b) da es ja nur eigtl 4 zahlen (1,4, 4.5 , 5.5) sind. 4 schritte? oder wie darf man schritte verstehen?
c)hm.. ok? wie keine kollision? dass dann sozusagen die zahl(1 ja in dem fall) sozusagen an die nächste freie stelle kommt? wäre ja dann n=6 weil wir ja 6 werte eintragen. ähm oder?
d)hier wäre die belegung von n dann:
1 , 4.5 , 1 , 5.5 , 1 , 4
e)hm was meine die denn da schon wieder für eine suche? linear oder? wären in dem fall dann ja auch wieder 6
hoffe ihr könnt mir ein bisschen helfen
Eine hashfunktion wir in folgenden beispiel, sagt ja eigtl nur wie man eine bestimmte zahl findet oder? und die offene verkettung, kann ich mir wie eine art behälter vorstellen, wo alle gleichen zahlen gespeichert werden?
hier ist die aufgabe:
Gegeben sei ein Hashfeld der Länge n und eine Hash-Funktion h(x) = (x*x/2) % n. Beim Auftreten einer
Kollision wird die offene Verkettung angewendet.
a) Geben Sie die Belegung des Feldes für n = 7 nach Eintragen der Werte 10, 3, -4, 5, 1 und 11 an.
b) Wieviele Schritte sind bei der entstandenen Belegung höchstens nötig, um festzustellen, dass ein
beliebiger Wert nicht in der Tabelle enthalten ist?
c) Auf welche Größe n muss das Feld mindestens vergrößert werden, damit mit den obigen Werten
beim Eintragen keine Kollision auftritt?
d) Geben Sie für dieses n ebenfalls die dann entstehende Belegung an.
e) Wieviele Schritte benötigt eine Suche in diesem Fall maximal, um das Fehlen eines Elementes
festzustellen?
Meine Ansätze:
a) wäre ja einfach nur einzusetzen:
für h(10)=(10*10/2)%7=1
für 3 = 4,5
für -4 = 1
für 5 = 5,5
für 1 = 1
für 11 = 4
die belegung von n wäre dann:
1(3mal) , 4.5 , 5.5 , 4
b) da es ja nur eigtl 4 zahlen (1,4, 4.5 , 5.5) sind. 4 schritte? oder wie darf man schritte verstehen?
c)hm.. ok? wie keine kollision? dass dann sozusagen die zahl(1 ja in dem fall) sozusagen an die nächste freie stelle kommt? wäre ja dann n=6 weil wir ja 6 werte eintragen. ähm oder?
d)hier wäre die belegung von n dann:
1 , 4.5 , 1 , 5.5 , 1 , 4
e)hm was meine die denn da schon wieder für eine suche? linear oder? wären in dem fall dann ja auch wieder 6
hoffe ihr könnt mir ein bisschen helfen
