77.1.137.138: in der -> in dem

2024-01-28T00:32:08Z

in der -> in dem

Neue Seite

{{Belege fehlen}}

Eine [[Datenstruktur]] wird als '''entartet''' bezeichnet, wenn sie final einen Zustand angenommen hat, in dem sie anders als vor der Entartung nachteilig wirkt. Dies kann aufgrund ungünstiger Eingabedaten geschehen.

== Beispiel ==

Eine grundlegende Datenstruktur sind sortierte [[Binärbaum|Binärbäume]]. Diese bestehen aus Knoten mit jeweils zwei Nachfolgerknoten, wobei alle Knoten des linken Teilbaumes (= linker Nachfolgerknoten und dessen Nachfolger, auch die indirekten) kleiner und alle Knoten des rechten Teilbaumes größer als dieser sind:

[7]
/ \
[3] [12]
/ \ / \
[1] [4] [9] [15]

Was solche binären Bäume auszeichnet, ist, dass der Baum stets sortiert ist. Das Einfügen neuer Knoten hat die [[Komplexitätstheorie|Komplexität]] O(log(N)), im Gegensatz zu O(N) bei einer sortierten [[Liste (Datenstruktur)|Liste]].

Kommen die Knoten beim Erstellen des Baumes jedoch in ungünstiger Reihenfolge, so kann eine Entartung des Baumes die Folge sein:

[1]
\
[3]
\
[4]
\
[7]
\
[9]
\
[12]
\
[15]

Jetzt ist der Baum zwar immer noch sortiert, der Aufwand des Einfügens neuer Knoten ist jedoch O(N), da er praktisch eine sortierte Liste ist.

== Anfälligkeit ==

Viele gebräuchliche Datenstrukturen sind für Entartung anfällig, Beispiele hierfür sind der oben erwähnte sortierte binäre Baum und viele Implementierungen von [[Hash-Tabelle]]n ohne Feedback.

Je nach Datenstruktur ist die Anfälligkeit gegen Entartung verschieden. Bei obigem binären Baum reicht es aus, dass die Eingabedaten sortiert sind; bei determiniert oder stochastisch konfigurierten Hashtabellen und ''vernünftigen'' Hashfunktionen ist eine Entartung aber sehr unwahrscheinlich und wird deshalb meist vernachlässigt.

Es gibt aber auch Datenstrukturen, die durch spezielle Maßnahmen gegen Entartung immun sind, z. B. [[Rot-Schwarz-Baum|Rot-Schwarz-Bäume]]. Die Absicherung kostet in der Regel etwas Effizienz, erhöht dafür aber die [[Worst-Case]]-Effizienz erheblich.

== Sicherheitsaspekte ==

Der Einsatz von Datenstrukturen, die entarten können, macht das betreffende Programm anfällig für [[Denial of Service|Denial-of-Service]]-Attacken. Dazu kann ein Angreifer das Programm so mit Eingabedaten füttern, dass die internen Datenstrukturen des Programms entarten und das Programm dadurch erheblich mehr Rechenzeit als üblich benötigt – im Extremfall so viel, dass das Programm seinen Zweck nicht mehr erfüllen kann.

Als Gegenmaßnahmen wurde in die Hashtabellen der auf vielen Webservern verwendeten Programmiersprache [[Perl (Programmiersprache)|Perl]] eine Zufallskomponente eingebaut, die bei jedem Programmstart für eine neue interne Verteilung zu speichernder Werte in die Hashtabelle sorgt und einen DoS-Angriff durch absichtliche Entartung damit erheblich erschwert.

[[Kategorie:Datenstruktur]]

Entartung (Informatik) - Versionsgeschichte

77.1.137.138: in der -> in dem