TObjectlst - Index eines Objektes finden

[himitsu]

Zitat:

Function TIntegerDictionary.FindHash(aKey: Cardinal; Out h: Cardinal): Pointer;

Delphi-Quellcode:

Begin
  h := HashFromInt(aKey) Mod fHashMod;
  Result := fHashList[h];
  While PIntHashEntry(Result) <> Nil Do
    With PIntHashEntry(Result)^ Do
      If heKey = aKey Then
        Exit
      Else
        Result := heNext;

End;

Da wird also ein Hash von dem Integer gemacht und dann wird einie Liste durchsucht.

Wenn man den Integer nun direkt sucht, dann könnte man sich das Haschen sparen und müßte ebenfalls eine Liste durchgehn.

OK, hier würde man dann im schlimmsten Fall die komplette Liste durchgehn und bei der Map nur einen Teil.
Bei einer sortierten Liste würde man aber auch nur einen Teil der Liste durchgehn müssen.
(bei 1000 Einträgen in 'ner sortierten Liste wären auch nur maximal 10 Vergleiche nötig ... was etwa 'ner Hashmap mit fHashMod=100 entsprechen würde)

Oder seh ich das falsch?

[edit=mkinzler]Delphi-Tag eingefügt Mfg, mkinzler[/edit]

[Khabarakh]

Das mit O(1) darfst du alzaimar ruhig glauben .
Fakt ist: Eine Hashmap benötigt O(n) zum Aufbau und O(1) zum Lookup, dagegen kann eine sortierte Liste mit O(n log n) und O(log n) nicht anstinken.

[himitsu]

Tut mir Leid, aber da ist eine Schleife drin, also kann das O(1) nicht stimmen.

Gut, die Speicherzugriffe zwischen dem Record (Value=Recordpointer-Offset) und Array+Property (Array-Referenz+Property-Zugriff) mag schneller sein, also würde es im idealfall eher so aussehn

Θarray(n) = Θmap(n / fHashMod) / x
> x wäre jetzt der Unterschied zwischen den beiden Zugriffen

Wenn jetzt fHashList[h] direkt den EINEN gesuchten Wert liefern würde, dann täte vielleicht Θ(1) rauskommen.

[Khabarakh]

Zitat von himitsu:

Tut mir Leid, aber da ist eine Schleife drin, also kann das O(1) nicht stimmen.

Im Worst Case, ja, aber im Durchschnitt interessiert dann doch eher der durchschnittliche Fall . Und da gilt die angegebene Formel, die in der Quellenangabe auch hergeleitet wird (so viel Wahrscheinlichkeitsrechnung, argh ).

Zitat von himitsu:

Θarray(n) = Θmap(n / fHashMod) / x

Wenn du Vorfaktoren vergleichen willst, ist asymptotische Laufzeit definitiv das falsche Werkzeug .