Hash-Funktion < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:11 Di 05.06.2012 | | Autor: | bandchef |
| Aufgabe | Implementieren Sie Hashing mit offener Adressierung in C,C++, C# oder Java anhand der
Hashfunktion h(s) = s unter Verwendung folgender Varianten zur Kollisionsauflösung:
1. Lineares Probieren
2. Quadratisches Probieren mit c1 = 1 und c2 = 3
3. Doppeltes Hashing mit h1(s) = s und h2(s) = 1 + (s mod (m - 1))
Geben Sie jeweils die Hashtabelle der Größe m = 11 aus, die nach Einfügen der Werte
10; 22; 31; 4; 15; 28; 17; 88; 59 in allen drei Varianten entsteht. |
Hi Leute!
Ich möchte diese Aufgabe in C implementieren. Ich verstehe aber nicht so ganz was hier gemeint ist!
Ich hab also ein array mit Werten gegeben. Das sind diese Zahlen: 10; 22; 31; 4; 15; 28; 17; 88; 59.
Diese Zahlen soll also durch lineares probieren in die Hashtabelle mit der Hasfunktion h(s) = s eingefügt werden. Lineares probieren geht ja von Anfang bis Ende einfach durch. Da die Hashfunktion ja nur de Wert selber wieder rausgibt ist das grad irgendwie ein bisschen komisch...
Was bringt mir das dann? In der Vorlesung haben wir immer so eine Funktion gehabt: h(s) = s mod 6, bspw.
Muss ich also nun das array mit den Werten an eine Funktion übergeben die mir der Reihe nach die Werte in ein neues Array (die Hastabelle an sich) einfügt? Mehr ist das doch im linearen Fall nicht, oder? Wie groß muss ich beim deklarieren der Hashtabelle die Größe wählen? Ist das das m? Gibt m die größe der Hashtabelle an? Gilt m auch für Fall 2 und 3?
Könnt ihr mir weiterhelfen?
Hier mal mein bisheriger code:
[code]
#include<iostream>
using namespace std;
void linearProbing(int* werte, int n)
{
int tabelle[11];
for(int i=0; i<n; i++)
{
tabelle[i] = werte[i];
}
}
int main()
{
int werte[9] = {10,22,31,4,15,28,17,88,59};
int anzahl = 9;
linearProbing(werte, anzahl);
return 0;
}
[code]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:50 Mi 06.06.2012 | | Autor: | Stoecki |
> Implementieren Sie Hashing mit offener Adressierung in
> C,C++, C# oder Java anhand der
> Hashfunktion h(s) = s unter Verwendung folgender
> Varianten zur Kollisionsauflösung:
>
> 1. Lineares Probieren
> 2. Quadratisches Probieren mit c1 = 1 und c2 = 3
> 3. Doppeltes Hashing mit h1(s) = s und h2(s) = 1 + (s mod
> (m - 1))
>
> Geben Sie jeweils die Hashtabelle der Größe m = 11 aus,
> die nach Einfügen der Werte
> 10; 22; 31; 4; 15; 28; 17; 88; 59 in allen drei Varianten
> entsteht.
>
> Hi Leute!
>
> Ich möchte diese Aufgabe in C implementieren. Ich verstehe
> aber nicht so ganz was hier gemeint ist!
>
> Ich hab also ein array mit Werten gegeben. Das sind diese
> Zahlen: 10; 22; 31; 4; 15; 28; 17; 88; 59.
>
> Diese Zahlen soll also durch lineares probieren in die
> Hashtabelle mit der Hasfunktion h(s) = s eingefügt
> werden. Lineares probieren geht ja von Anfang bis Ende
> einfach durch. Da die Hashfunktion ja nur de Wert selber
> wieder rausgibt ist das grad irgendwie ein bisschen
> komisch...
>
> Was bringt mir das dann? In der Vorlesung haben wir immer
> so eine Funktion gehabt: h(s) = s mod 6, bspw.
hast du hier auch mit mod 11, sonst macht das keinen sinn. die 22 würde ja an die stelle 22 gesetzt werden und die ist nicht definiert
>
> Muss ich also nun das array mit den Werten an eine Funktion
> übergeben die mir der Reihe nach die Werte in ein neues
> Array (die Hastabelle an sich) einfügt? Mehr ist das doch
> im linearen Fall nicht, oder?
nein, mehr ist das nicht. werte nehmen und so lange versuchen einzufügen, bis es eine freie stelle gibt.
>Wie groß muss ich beim
> deklarieren der Hashtabelle die Größe wählen? Ist das
> das m? Gibt m die größe der Hashtabelle an? Gilt m auch
> für Fall 2 und 3?
jeb
>
>
> Könnt ihr mir weiterhelfen?
>
> Hier mal mein bisheriger code:
>
>
> [code]
> #include<iostream>
> using namespace std;
>
>
>
> void linearProbing(int* werte, int n)
> {
> int tabelle[11];
>
> for(int i=0; i<n; i++)
> {
> tabelle = werte;
hier wirst du eine out of bound bekommen. es fehlt %11
> }
> }
>
>
>
> int main()
> {
> int werte[9] = {10,22,31,4,15,28,17,88,59};
> int anzahl = 9;
>
> linearProbing(werte, anzahl);
>
>
>
> return 0;
> }
> [code]
was auch noch fehlt sind dann die funktionen für die kolisionsbehebung. die solltest du direkt bei der zuweisung tabelle[i] =... mit implementieren
Gruß Bernhard
|
|
|
|
