Veröffentlicht · wird verbessert
Algorithm
Wie Arrays, verkettete Listen, Stacks, Queues und Hashtabellen funktionieren, was jede Operation kostet und wie man die passende Struktur wählt.
Eine Datenstruktur legt fest, wie Daten im Speicher angeordnet sind und welche Operationen auf dieser Anordnung günstig sind. Dieses Thema behandelt die fünf Strukturen, auf die fast jedes Programm zurückgreift: Arrays und dynamische Arrays, verkettete Listen, Stacks, Queues und Deques sowie Hashtabellen. Dabei geht es auch um zusammenhängenden gegenüber verkettetem Speicher, Hashfunktionen, Kollisionen und den Belegungsfaktor.
Die Wahl der Struktur entscheidet, ob eine Operation O(1) oder O(n) kostet. Wer eine Queue baut, indem er vorn aus einer Liste entfernt, oder Mitgliedschaft in einer Liste prüft, macht sein Programm bei wachsenden Daten drastisch langsamer. Wer weiß, was hinter list, deque, dict und set in Python, vector, deque und unordered_map in C++, ArrayList, ArrayDeque und HashMap in Java sowie Array, Map und Set in TypeScript steckt, vermeidet solche Fallen. Genau das fragen auch Coding-Interviews zuerst ab.
Am besten verfolgt man jede Struktur zunächst von Hand an einem kleinen Beispiel und sieht, was sich im Speicher bewegt. Danach implementiert man einen Stack, eine Queue als Ringpuffer und eine Hashmap mit Verkettung, fasst die Kosten in einer Tabelle zusammen und misst sie mit einem Timer. Zum Schluss folgen Übungsaufgaben, bei denen es vor allem darum geht, die passende Struktur zu wählen.
Arrays bieten O(1)-Zugriff über den Index und gute Cache-Nutzung; verkettete Listen erlauben O(1)-Einfügen und -Löschen neben einem bekannten Knoten.
Ein dynamisches Array wächst um einen konstanten Faktor und kopiert seine Elemente, sodass gelegentlich teure Anhängevorgänge im Mittel O(1) bleiben.
Ein Stack entnimmt das neueste, eine Queue das älteste Element. Deques und Ringpuffer machen Operationen an beiden Enden O(1).
Eine Hashtabelle ordnet Schlüssel Buckets zu und findet sie im Mittel in O(1). Kollisionen löst sie etwa durch Verkettung und wächst, sobald der Belegungsfaktor eine Grenze überschreitet.
Eine Hashmap mit Verkettung: Der Hash des Schlüssels modulo Bucket-Anzahl bestimmt den Bucket, bei vorhandenem Schlüssel wird nur der Wert ersetzt, und ab einem Belegungsfaktor über 0,75 verdoppeln sich die Buckets und alle Paare werden neu eingefügt. Das Skript zeigt außerdem eine Liste als Stack und eine deque als Queue.
data_structures.py
from collections import deque
class HashMap:
"""Separate chaining: each bucket is a list of (key, value) pairs."""
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size > 0.75 * len(self.buckets): # load factor limit
old = self.buckets
self.buckets = [[] for _ in range(2 * len(old))]
for pairs in old:
for k, v in pairs:
self._bucket(k).append((k, v))
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
stack = [1, 2, 3]
stack.append(4)
print("stack pop:", stack.pop()) # 4 (LIFO)
queue = deque([1, 2, 3])
queue.append(4)
print("queue popleft:", queue.popleft()) # 1 (FIFO)
ages = HashMap()
for name, age in [("ada", 36), ("alan", 41), ("grace", 85)]:
ages.put(name, age)
ages.put("ada", 37)
print("ada:", ages.get("ada"), "size:", ages.size) # ada: 37 size: 3
python data_structures.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Grundlegende Datenstrukturen.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Grundlegende Datenstrukturen aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.