Hashfunktion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | m = Größe der Hashtabelle
a) Sei m = 9 und
$h(u)=(6*u+1) mod 9$
Zeigen Sie, daß bei dieser Wahl von h nicht alle Plätze der Hashtabelle ausgeschöpft werden können. |
Hallo erstmal :D
Mein Problem ist das ich nicht weiß wie ich das korrekt zeige...
Durch einsetzen seh ich jetzt, dass die Funktion periodisch verläuft...
$h(0)=1$
$h(1)=7$
$h(2)=4$
$h(3)=1$
$h(4)=7$
$h(5)=4$
$h(6)=1$
$h(7)=7$
$h(8)=4$
.
.
.
usw...
wie zeig ich das für alle???
So werden ja ersichtlich nicht alle Plätze der Hashtabelle in Anspruch genommen...
Gruß Benjamin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:09 Sa 07.01.2006 | | Autor: | piet.t |
Hallo Benjamin,
zeige doch einfach, dass h(u+3) = h(u) (das sollte ja nicht weiter schwer sein). Damit kannst Du dann ja schon sagen, dass höchstens 3 Plätze der Hashtabelle belegt werden (durch einsetzen von 0,1,2 kann man dann ja noch zeigen, welche das sein können).
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:35 Sa 07.01.2006 | | Autor: | fisch.auge |
ja ok dann werd ichs so machen.... danke :D
|
|
|
| |
|
| Aufgabe | b) Geben Sie eine unendlich große Menge M an, sodaß
$h(u)=4$ [mm] $\forall [/mm] u [mm] \in [/mm] M.$ |
Hallo nochmal,
mein Problem ist jetzt, dass ich nicht weiß, ob die Aufgabe sich auf a) bezieht?!?! Und ansonsten steh ich auch gerade etwas aufm Schlauch...
Nunja sollte die Menge evtl so aussehen:
[mm] $M=\{2,5,8,...\}$
[/mm]
Ich hab grade wirklich keinen blassen Schimmer :/
Danke schonmal!
Gruß Benni
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:54 So 08.01.2006 | | Autor: | piet.t |
Hallo,
wenn da keine neue Hashfunktion gegeben ist kann sich die Frage eigentlich nur auf a) beziehen.
Die Menge passt so auch, evtl. kann man sie noch etwas formaler hinschreiben, etwa:
[mm] M = \{2+3k | k\in \IN\} [/mm]
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:47 So 08.01.2006 | | Autor: | fisch.auge |
ja ok alles klar...
Danke!
|
|
|
| |
|
| Aufgabe | geben sie ausgehend von teil a) eine bedingung für a,b und m an, für die eine Hashfunktion
h(u) = a * u + b mod m
nicht alle Plätze der Hashtabelle ausschöpft.... |
hallo ich nochmal... diese aufgabe bereit mir nun so seine probleme und ich komm einfach auf nix.... vielleicht könnt mir ja jemand weiterhelfen....
mein ansatz wär...
also wenn man nur mal a und m betrachtet... wenn man z.b. 4 und 6 einsetzt sind die wiederum nach 3 malen periodisch
Das teilverhältnis is 3/2...
das bringt mich aber auch irgendwie zu nix...
wär um jede hilfe dankbar!!!
gruß fisch
EDIT: sooo habs jetzt so geschrieben:
Besitzen a und m einen gemeinsamen Teiler so wird die Tabelle nie komplett ausgefüllt. dies ist unabhängig von b!
ist das so i.O.?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:36 Mi 11.01.2006 | | Autor: | piet.t |
Hallo,
die Idee ist schon richtig, jetzt müsste man das ganze nur noch passend begründen.....
Mein Vorschlag:
Die Hashfunktion ist ja auf alle Fälle periodisch, die Periodenlänge sei x.
Es gilt also:
[mm]au + b \equiv a(u+x) + b \quad \mod m [/mm]
Die Äquivalenz kann man jetzt ja nach den allgemein bekannten Rechenregeln umformen, nur dividieren darf man im allgemeinen nicht (dazu müsste m eine Primzahl sein).
Nun Vereinfacht man den Ausdruck so weit wie möglich und stellt sich die Frage, unter welcher Bedingung x = m gelten muss (in diesem Fall wird ja gerade die komplette Hashtabelle ausgenutzt).
Hilft das?
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:45 Do 12.01.2006 | | Autor: | fisch.auge |
ok danke für die hilfe hab die übung mittlerweile schon abgegeben... bin darauf gekommen das bei
a*u + b mod m
kgV(a,m) / a die Anzahl der Wiederholen wiedergibt, somit lässt sich überprüfen, ob eine tabelle gefüllt wird oder nicht...
naja mal sehen was die korrektur sagt ^^
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:45 Do 12.01.2006 | | Autor: | fisch.auge |
ok, danke für die hilfe!!! hab die übung mittlerweile schon abgegeben... bin darauf gekommen das bei
a*u + b mod m
kgV(a,m) / a die Anzahl der Wiederholen wiedergibt, somit lässt sich überprüfen, ob eine tabelle gefüllt wird oder nicht...
naja mal sehen was die korrektur sagt ^^
gruß benjamin
|
|
|
|
