verkette Listen Informatik Schlüsselvergleiche?

Ich verstehe hierbei die Lösung nicht. Meiner Ansicht nach würde man die Suche nach einem gefundenen Schlüssel beenden und könnte deshalb niemals auf diese Anzahl an Vergleichen kommen. Hier die Aufgabe: In eine Hashtabelle (Divisionsmethode, Kollisionsauflösung durch Verkettung) mit m=10 Tabellenplätzen wurden die ersten n=12 Primzahlen eingefügt. Es sind zuerst zwölf Zahlen zu berechnen, nämlich (jeweils) die Anzahl der Schlüsselvergleiche für die Suche nach dem Schlüssel 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37:

• 6 Schlüssel (nämlich 31, 2, 23, 5, 37 und 29) werden mit genau einem Schlüsselvergleich gefunden.
• Unter den zwölf Zahlen für die Durchschnittsbildung kommt die 1 also 6 mal vor.
• 4 Schlüssel (11, 13, 17, 19) werden mit genau zwei Schlüsselvergleichen gefunden.
• Unter den zwölf Zahlen kommt die 2 also 4 mal vor.
• 2 Schlüssel (3, 7) werden mit genau drei Schlüsselvergleichen gefunden.
• Unter den zwölf Zahlen kommt die 3 also 2 mal vor.

Dann muss der Durchschnitt dieser zwölf Zahlen berechnet werden:

Diese Zahl muss auf zwei Nachkommastellen gerundet werden. Also 1,67

Die richtige Antwort ist: 1,67

Answer 1

[iQa1x]

Es wird berechnet, wie viele Vergleiche durchschnittlich für eine Suche nach einer der Zahlen benötigt werden. Wenn du nach der 3 oder 7 suchst, brauchst du eben 3 Vergleiche.

Die Zahlen, bei denen die Einerstelle (weil Divisionsrestmethode modulo 10) nur einmal in der Liste vorkommt, können mit einem Vergleich gefunden werden. Ebenso die letzte der Zahlen, bei denen die Einerstelle mehrfach vorkommt. Bei den anderen Zahlen ist der erste Vergleich false und man muss den nächsten bzw. übernächten Eintrag in der Liste noch vergleichen, weswegen es dann 2 oder 3 Vergleiche gibt.

Hashtbl /  Liste
0:
1: 31 11
2: 2
3: 23 13 3
4:
5: 5
6:
7: 37 17 7
8:
9: 29 19

Beispiel 11: Index 1 (11 mod 10), Vergleich 11 mit 31 -> falsch, Vergleich 11 mit 11 -> wahr

Comments

[markus3r34r3]

Ja danke mein Fehler war dumm. Ich habe vergessen, dass die doppelten Hashwerte ja immer ganz links eingefügt werden und nicht rechts angehängt werden. Danke!