TList en hash?

Der vil (i teorien) være allokeret 9999 tomme pladser. En TList allokere hukommelse til et \"array\" hvori der kan være X-antal pointere som hver især peger på sit object.

I teorien vil den hukommelse som en TList allokere fylde 4 x antal-poster (eftersom en pointer er 4 bytes), men den måde hvorpå en TList fungere så kan du ikke helt regne med dette, da den allokere hukommelse i blokke (således at den ikke skal afsætte plads hver eneste gang man tilføjer et objekt). Her har du den \"Grow-methode\":
<SNIP>
procedure TList.Grow;
var
  Delta: Integer;
begin
  if FCapacity > 64 then
    Delta := FCapacity div 4
  else
    if FCapacity > 8 then
      Delta := 16
    else
      Delta := 4;
  SetCapacity(FCapacity + Delta);
end;
</SNIP>

Hvis du på forhånd ved at din liste skal indeholde 10000 elementer, så start med at sætte din Capacity (TListXX.Capacity := 10000;) dette vil spare den for at kalde Grow mens du indsætter poster.

Hvis min list nu kun skal indholde 2 elementer. En på plads 0 og en på plads 10000. I et array vil der allokeres 10001 * 4 bytes, mens en hashtabel kun allokerer til de 2 * 4 bytes. Jeg vil gerne vide: Hvormeget allokerer TList. Hvordan er den implementeret?? Som en wrapper om et array? Som et array med tilhørende hash-funktion?? Som kædet liste???
Spørgsmålet er ikke så vigtigt for mig da jeg netop har lavet min egen hash, men pointene går stadig til den der kan svare på om TList er:

1) En hash-tabel, eller...

2) wrapper om et array a\'la Vector i C++

MVH Ugge

Jeg prøver igen:

En TList indeholder IKKE en hashtabel. Den indeholder derimod en pointer til et array af pointere (se nedenstående). Den plads der allokeres til dette array afhænger af hvor mange pointere der skal være i arrayet. I dit tilfælde hvis du vil insætte de to som henholds element nr. 0 og 10000 så skal der mindst allokeres 10001 * 4 bytes.

<SNIP>
const
  MaxListSize = Maxint div 16;
type
  PPointerList = ^TPointerList;
  TPointerList = array[0..MaxListSize - 1] of Pointer;
</SNIP>

Dog er der ingen der forhindre dig i at gøre det på en anden måde:
<SNIP>
type
  ElmClass=Class
  FElementNummer : Integer;
  end;
var
  List : TList;
  Element : ElmClass;
begin
  List := TList.Create;
  Element := ElmClass.Create;
  Element.FElementNummer := 0;
  List.Ass(Element);
  Element := ElmClass.Create;
  Element.FElementNummer := 10000;
  List.Ass(Element);
<SNIP>

På denne måde har du kun indsat 2 elementer, så teoretisk har TList kun afsat 8 bytes. Men hvorvidt dette kan bruges eller ej, komme helt an på hvad du skal bruge din liste til (alt-andet-lige ville jeg aldrig bruge en TList til at gemme kun element nr, 0 og 10000).

<LOL> Øhh prøv at erstatte \"Ass\" med \"Add\" så bliver det nok nemmere både at læse og at oversætte  :-)

Tak for svaret pellelil. Jeg skal bruge en container til at indeholde et par hundrede elementer med index der går fra nul til ca. 1 mio., så en hash ville være perfekt. Nu har jeg selv lavet en og mit problem er løst. TList er åbentbart ikke way to go :).

Du kunne have valgt at bruge en TStringList. Denne kan både indeholde en string liste, men samtidig en \"Object liste\". Du kunne således bruge \"streng-delen\" til at styre sorteringen. Du kan selvfølgelig ikke bare tage fat i element nummer 45, men skal først finde ud af hvor denne er. Dette gøres vha. TStringListen\'s \"find\" som alt-andet-lige er (jeg gætter her) implementeret som en binær-søge-metode hvorfor dit overhead er minimal.

Jeg har aldig selv være forelsket i hashtabel\'er da de teoretisk kan ende op med 2 elementer på samme plads (dog er der også råd for det). Jeg ville personligt nok vælge at bruge ovenstående (men vi har da heldivis flere muligheder at vælge imellem så hvis du fortrækker hashtables - by all means).

Hash tabeller er MEGET hurtigere end lineær søgning. Det er rigtigt at et antal elementer vil ligge på samme plads, dette kan løses f.eks. med en kædet liste. Det er lidt besværligt, men jeg kan meget godt lide resultatet.