Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:daten:processing:dictionaries_tutorial [2024-01-22 14:05] – hof
+++ gf_informatik:daten:processing:dictionaries_tutorial [2026-05-25 10:14] (aktuell) – [Aufgabe 3 - HashMap] hof
@@ Zeile 64: / Zeile 64: @@
 print(map['one'])
 </code>
 #### Laufzeit-Messung
@@ Zeile 158: / Zeile 157: @@
 Können wir noch schneller sein als Binärsuche?
-Binärsuche ist sehr viel schneller als lineare Suche: jedes Mal, wenn wir die Anzahl Einträge verdoppeln, vergrössert sich die Zeit um einen konstanten Faktor. Alternative Betrachtung: werden die Anzahl Einträge quadriert, verdoppelt sich die Zeit. Mann kann auch sagen, dass die Zeit pro Lookup mit dem Logarithmus der Anzahl Einträge wächst, oder dass Lookup die Komplexität $\mathcal{O}(log(n))$ hat.
+Binärsuche ist sehr viel schneller als lineare Suche: jedes Mal, wenn wir die Anzahl Einträge verdoppeln, vergrössert sich die Zeit um einen konstanten Faktor. Alternative Betrachtung: werden die Anzahl Einträge quadriert, verdoppelt sich die Zeit. Mann kann auch sagen, dass die Zeit pro Lookup mit dem Logarithmus der Anzahl Einträge wächst, oder dass Lookup die [[wpde>Landau-Symbole|Komplexität]] $\mathcal{O}(log(n))$ hat.
 #### Hashing
@@ Zeile 178: / Zeile 176: @@
 Um die Anzahl Kollisionen tief zu halten ist es wichtig, dass die Liste nie ganz gefüllt ist - die Tupel-Liste wird also bewusst grösser gewählt als nötig und bei Bedarf ein _rehash_ ausgeführt: alle Einträge werden in eine neue, grössere Liste umgefüllt, wobei die Indices dann neu berechnet werden müssen. Je nach gewähltem Faktor für die tolerierbare Kollisionszahl benötigt die Hashmap also mehr Speicher, um damit eine bessere Laufzeit zu erreichen.
 #### Aufgabe 3 - HashMap
 Implementiere eine `class HashMap`.
@@ Zeile 187: / Zeile 183: @@
 <nodisp 1>
-++++Mit linear Probing:|
+++++Mit Linear Probing:|
 <code python>
 class HashMap(TupleList):
@@ Zeile 308: / Zeile 304: @@
     def __delitem__(self, key):
-        return self._finditem(key).__delitem__(key)
+        item = self._finditem(key).__delitem__(key)
+        self._len -= 1
+        return item
     def __setitem__(self, key, value):
@@ Zeile 330: / Zeile 328: @@
                 if entry:
                     for key in entry:
-                        self._finditem(key, raise_on_notfound=False)[key] = entry[key]
+                        self._finditem(key, False)[key] = entry[key]
 </code>
 ++++
 </nodisp>