mibeon
/ Datenstrukturen

Array Zugriffszeit

Speicheradresse eines Array-Elements aus Basisadresse, Index und Elementgröße: Adresse = Basis + Index · Elementgroesse. Konstante Zeit O(1).

Array Zugriffszeit
01 · Eingabe

Array Zugriffszeit berechnen

Speicheradresse eines Array-Elements aus Basisadresse, Index und Elementgröße: Adresse = Basis + Index · Elementgroesse. Konstante Zeit O(1).

Lösen für
Adresse = Basis + Index · Elementgroesse
Byte
Byte

Worum geht es?

Ein Array liegt als zusammenhängender Speicherblock im RAM. Da alle Elemente die gleiche Größe haben, lässt sich die Adresse eines beliebigen Elements durch eine einzige Multiplikation und Addition berechnen — unabhängig von der Array-Länge.

Das ist der Grund, warum der Zugriff auf arr[1000000] exakt gleich schnell ist wie auf arr[0]. Diese Eigenschaft heißt Random Access in konstanter Zeit O(1) und ist das wichtigste Argument für Arrays gegenüber verketteten Listen.

Die Formel

Formel Array-Adresse 
Adresse = Basis + Index · Elementgröße

Umstellungen:
    Index = (Adresse − Basis) / Elementgröße
    Basis = Adresse − Index · Elementgröße

Die Variablen

SymbolBedeutungEinheitErklärung
BasisBasisadresseByteStartadresse des Arrays im Speicher.
IndexIndex—0-basierter Index des Elements.
ElementgrößeElementgrößeByteGröße eines Elements (z. B. 4 Byte).
AdresseElementadresseByteBerechnete Adresse.

Minimal-Beispiel

Ein int32-Array (4 Byte pro Element) liegt ab Adresse 0x1000. Wo liegt Element 7?

Rechnung Element 7 
Adresse = 0x1000 + 7 · 4
        = 0x1000 + 28
        = 0x101C

Praxis-Beispiele

Beispiel 1 — double-Array

Ein double[] (8 Byte) startet bei 0x4000. Element 50 liegt bei:

Rechnung double[50] 
Adresse = 0x4000 + 50 · 8
        = 0x4000 + 400
        = 0x4190

Beispiel 2 — Struct-Array

Eine Struct Point { float x; float y; } belegt 8 Byte. Bei points[12]:

Rechnung points[12] 
Offset = 12 · 8 = 96 Byte

Beispiel 3 — Index aus Adresse rückrechnen

Ein Profiler meldet Zugriff auf 0x2050 in einem int-Array (4 Byte) ab 0x2000:

Rechnung Index 
Index = (0x2050 − 0x2000) / 4
      = 80 / 4
      = 20