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
Liste