seminar11.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\n",
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
    "\n",
    "Die Python-Standardbibliothek bietet viele Module, die die Arbeit erleichtern. Beispielsweise ermöglicht das Modul [json](https://docs.python.org/3/library/json.html) das Lesen und Schreiben von [JSON](https://en.wikipedia.org/wiki/JSON)-Dateien:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json                                  # Modul für JSON-Dateien\n",
    "from collections import Counter              # wir wollen wieder etwas zählen\n",
    "\n",
    "def count_words(counter, lines):             # eine Funktion zum Wörterzählen\n",
    "    \"\"\"Zählt die Vorkommen der Wörter in lines.\n",
    "       counter: ein Zählobjekt (collections.Counter)\n",
    "       lines: eine Liste von Zeichenketten\n",
    "    \"\"\"\n",
    "    for line in lines:                       # alle Zeilen durchlaufen\n",
    "        for word in line.split():            # Zeichenketten in Wörter aufteilen\n",
    "            counter[word] += 1               # Vorkommen des Wortes zählen\n",
    "\n",
    "\n",
    "nb = json.load(open(\"seminar11.ipynb\", \"r\")) # Jupyter-Notebooks sind JSON-Dateien!\n",
    "counter = Counter()                          # zählt Vorkommen von Wörtern\n",
    "\n",
    "for c in nb[\"cells\"]:                        # über alle Zellen iterieren\n",
    "    if c[\"cell_type\"] == \"markdown\":         # für jede Markdown-Zelle ...\n",
    "        count_words(counter, c[\"source\"])    # Wörter im Text zählen\n",
    "\n",
    "for word, freq in counter.most_common(10):   # die zehn häufigsten Wörter finden ...\n",
    "    print(word, freq, sep='\\t')              # und ausgeben"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11 Assoziative Datenfelder \n",
    "\n",
    "Dieses Kapitel behandelt einen weiteren eingebauten Datentyp, die sogenannten *assoziativen Datenfelder* (im Englischen *map, dictionary* oder *associative array* genannt). Assoziative Datenfelder sind eines der besten Feature von Python; sie sind die Bausteine vieler effizienter und eleganter Algorithmen. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.1 Ein assoziatives Datenfeld ist eine Abbildung\n",
    "\n",
    "Ein **assoziatives Datenfeld** ist wie eine Liste aber allgemeiner. In einer Liste müsse die Indexe ganze Zalen sein, in einem assoziativen Datenfeld können sie von (fast) jedem Typ sein.\n",
    "\n",
    "Ein assoziatives Datenfeld enthält eine Sammlung von Indexen, die **Schlüssel** (*keys*) genannt werden und eine Sammlung von **Werten** (*values*). Jeder Schlüssel ist mit genau einem Wert assoziiert. Diese Verknüpfung zwischen Schlüssel und Wert wird **Schlüssel-Wert-Paar** (*key-value pair*) oder manchmal auch **Eintrag** (*item*) genannt.\n",
    "\n",
    "Mathematisch ausgedrückt repräsentiert ein assoziatives Datenfeld eine **Abbildung** (*mapping*) der Schlüssel auf die Werte. Wir können also sagen, dass jeder Schlüssel auf genau einen Wert \"abgebildet\" wird. Als Beispiel bauen wir ein assoziatives Datenfeld, welches deutsche auf spanische Wörter abbildet; sowohl die Schlüssel als auch die Werte sind also Zeichenketten.\n",
    "\n",
    "Die Funktion `dict` erzeugt ein neues assoziatives Datenfeld ohne Einträge. Da `dict` der Name einer eingebauten Funktion ist, sollten wir vermeiden, sie als Variablenname zu verwenden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa = dict()\n",
    "deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die geschweiften Klammern, {}, repräsentieren ein leeres assoziatives Datenfeld. Mit Hilfe von eckigen Klammern können wir Einträge hinzufügen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa['eins'] = 'uno'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Zeile erzeugt einen Eintrag, der den Schlüssel `'eins'` auf den Wert `'uno'` abbildet. Wenn wir das assoziative Datenfeld nochmal ausgeben, sehen wir ein Schlüssel-Wert-Paar mit einem Doppelpunkt zwischen Schlüssel und Wert: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieses Ausgabe-Format ist auch ein Eingabe-Format! Wir können beispielsweise ein neues assoziatives Datenfeld mit drei Einträgen folgendermaßen erzeugen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa = {'eins' : 'uno', 'zwei' : 'dos', 'drei' : 'tres'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir `deu2spa` ausgeben, sind wir aber eventuell etwas überascht:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Reihenfolge der Schlüssel-Wert-Paare ist nicht unbedingt die gleiche geblieben und auf unterschiedlichen Computern könnten wir unterschiedliche Reihenfolgen erhalten. Im allgemeinen ist die Reihenfolge der Einträge in einem assoziativen Datenfeld nicht vorhersagbar. (Die technischen Hintergründen werden später erklärt.)\n",
    "\n",
    "Das ist jedoch kein Problem, denn die Elemente eines assoziativen Datenfeldes werden nicht mit ganzen Zahlen indexiert. Stattdessen verwenden wir die Schlüssel, um die entsprechenden Werte abzurufen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa['zwei']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Schlüssel `'eins'` wird also stets auf den Wert `'dos'` abgebildet, so dass die Reihenfolge der Einträge keine Rolle spielt.\n",
    "\n",
    "Wenn ein Schlüssel nicht im assoziativen Datenfeld enthalten ist, erhalten wir eine Ausnahmemeldung (*exception*):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa['vier']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Funktion `len` funktioniert auch mit assoziativen Datenfeldern; sie gibt die Anzahl der Schlüssel-Wert-Paare zurück:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(deu2spa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Operator `in` funktioniert ebenfalls mit assoziativen Datenfeldern; er sagt uns, ob etwas als *Schlüssel* in einem assoziativen Datenfeld enthalten ist (es reicht nicht, als *Wert* enthalten zu sein!):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'eins' in deu2spa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'uno' in deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um zu sehen, ob etwas als Wert in einem assoziativen Datenfeld enthalten ist, können wir die Methode `values` verwenden, die uns eine Sammlung der Werte zurückgibt, und dann den Operator `in` verwenden: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vals = deu2spa.values()\n",
    "'uno' in vals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Operator `in` nutzt unterschiedliche Algorithmen für Listen und assoziative Datenfelder. In Listen durchsucht er die Elemente der Liste der Reihenfolge nach, wie in [Abschnitt 8.6](seminar08.ipynb#8.6-Suche) beschrieben. Wenn die Liste größer wird, dauert die Suche entsprechend länger. \n",
    "\n",
    "Für assoziative Datenfelder nutzt Python eine Datenstruktur, die **Hash-Tabelle** genannt wird. Diese hat eine bemerkenswerte Eigenschaft: der Operator `in` benötigt ungefähr die gleiche Zeit, egal wie viele Einträge das assoziative Datenfeld enthält. In [Abschnitt B.4](seminarb.ipynb#B.4-Hash-Tabellen) wird erklärt, wie das möglich ist, aber die Erklärung ergibt für Sie vermutlich erst Sinn, nachdem Sie ein paar mehr Kapitel durchgearbeitet haben."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.2 Assoziative Datenfelder als Sammlung von Zählern\n",
    "\n",
    "Angenommen wir wollen zählen, wie oft jeder Buchstabe in einer Zeichenkette enthalten ist. Es gibt mehrere Möglichkeiten, wie wir das erledigen könnten:\n",
    "\n",
    "1. Wir könnten für jeden Buchstaben des Alphabets eine Variable erzeugen - also 30 Variablen. Dann könnten wir die Zeichenkette durchlaufen und für jeden Buchstaben den Wert der entsprechenden Variable um eins erhöhen. Dafür würden wir vermutlich (viele!) verkettete Bedingungen benötigen.\n",
    "2. Wir könnten auch eine Liste mit 30 Einträgen erzeugen und jeden Buchstaben in eine Zahl umwandeln (beispielsweise mit der eingebauten Funktion `ord`). Die Zahl entspräche dann dem Index eines Eintrages in der Liste und wir könnten den entsprechenden Wert erhöhen.\n",
    "3. Wir könnten ein assoziatives Datenfeld erzeugen mit den Buchstaben als Schlüsseln und den Zählern als zugehörigen Werten. Wenn wir einen Buchstaben zum ersten Mal sehen, dann würden wir einen Eintrag zum assoziativen Datenfeld hinzufügen. Ansonsten würden wir den Wert des bestehenden Eintrages erhöhen.\n",
    "\n",
    "Jede dieser Varianten erledigt die gleiche Berechnung, aber jede implementiert sie auf eine unterschiedliche Weise.\n",
    "\n",
    "Eine **Implementierung** (*implementation*) ist eine Weise, eine Berechnung durchzuführen; manche Implementierungen sind besser als andere. Beispielsweise ist ein Vorteil einer Implementierung durch ein assoziatives Datenfeld, dass wir vorab wissen müssen, welche Buchstaben in der Zeichenkette enthalten sind und wir nur Platz für diejenigen Zeichen machen müssen, die tatsächlich enthalten sind.\n",
    "\n",
    "So könnte der Code für diese Implementierung aussehen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def histogramm(s):\n",
    "    d = dict()\n",
    "    for c in s:\n",
    "        if c not in d:\n",
    "            d[c] = 1\n",
    "        else:\n",
    "            d[c] += 1\n",
    "    return d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Name der Funktion ist `histogramm`, das ist ein Begriff aus der Statistik, der eine Sammlung von Zählern (oder Häufigkeiten) bezeichnet.\n",
    "\n",
    "Die erste Zeile der Funktion erzeugt ein leerzes assoziatives Datenfeld. Die `for`-Schleife durchläuft die Zeichenkette `s`. Bei jedem Schleifendurchlauf wird geprüft, ob das aktuelle Zeichen `c` im assoziativen Datenfeld `d` enthalten ist. Falls nicht, erzeugen wir einen neuen Eintrag mit dem Schlüssel `c` und dem Anfangswert 1 (da wir den Buchstaben bisher einmal gesehen haben). Falls `c` bereits enthalten ist, erhöhen wir den Wert `d[c]` um 1.\n",
    "\n",
    "So funktioniert das ganze dann:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramm(\"Brontosaurier\")\n",
    "h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Histogramm sehen wir, dass die Buchstaben `'B'`, `'a'`, usw. einmal enthalten sind; der Buchstabe `'o'` zweimal, `'r'` dreimal.\n",
    "\n",
    "Assoziative Datenfelder haben eine Methode `get`, die einen Schlüssel sowie einen Vorgabewert erwartet. Falls der Schlüssel im assoziativen Datenfeld enthalten ist, liefert `get` den zugehörigen Wert zurück, ansonsten gibt es den Vorgabewert zurück. Beispielsweise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramm('a')\n",
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h.get('a', 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h.get('b', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nutzen Sie die Methode `get`, um die Funktion `histogramm` etwas prägnanter zu (re-)implementieren. Sie sollten es dabei schaffen, die `if`-Verzweigung zu entfernen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihre Funktion histogramm\n",
    "def histogramm(s):\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3 Schleifen und assoziative Datenfelder\n",
    "\n",
    "Wenn Sie ein assoziatives Datenfeld in einer `for`-Schleife nutzen, durchlaufen Sie alle Schlüssel des assoziativen Datenfeldes. Beispielsweise gibt `print_hist` alle Schlüsselund die zugehörigen Werte aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_hist(h):\n",
    "    for c in h:\n",
    "        print(c, h[c])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So sieht die Ausgabe dann au:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramm(\"Papagei\")\n",
    "print_hist(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wieder sind die Schlüssel ungeordnet. Um die Schlüssel geordnet zu durchlaufen, können wir die eingebaute Funktion `sorted` verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in sorted(h):\n",
    "    print(key, h[key])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4 Rückwärtsauflösung\n",
    "\n",
    "Wenn ein assoziatives Datenfeld `d` und ein Schlüssel `k` gegeben sind, ist es einfach, den zugehörigen Wert `v = d[k]` zu ermitteln. Diese Operation wird mit **Auflösung** (*lookup*) bezeichnet.\n",
    "\n",
    "Was aber tun, wenn `v` gegeben ist und wir `k` finden müssen? Dann haben wir zwei Probleme: erstens könnte es mehr als einen Schlüssel geben, der  auf `v` abgebildet wird. Abhängig von der Anwendung ist es uns vielleicht möglich, einen der Schlüssel auszuwählen oder wir müssen eine Liste aller möglichen Schlüssel erstellen. Zweitens gibt es keine einfache Syntax für die **Rückwärtsauflösung** (*reverse lookup*); wir müssen suchen.\n",
    "\n",
    "Dies ist eine Funktion, die ein assoziatives Datenfeld und einen Wert erwartet und den ersten Schlüssel zurückgibt, der auf den Wert abgebildet wird:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_lookup(d, v):\n",
    "    for k in d:\n",
    "        if d[k] == v:\n",
    "            return k\n",
    "    raise LookupError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Funktion ist ein weiteres Beispiel eines Such-Musters, aber sie nutzt eine Fähigkeit, die wir bisher noch nicht gesehen haben: `raise`. Die **raise-Anweisung** erzeugt eine Ausnahme (*exception*), in diesem Fall erzeugt sie einen `LookupError`, was eine eingebaute Ausnahme ist, die anzeigt, dass eine Auflösungs-Operation fehlgeschlagen ist.\n",
    "\n",
    "Wenn wir das Ende der Schleife erreichen heißt das, dass `v` nicht als Wert im assoziativen Datenfeld enthalten ist, daher erzeugen wir die Ausnahme.\n",
    "\n",
    "Hier ist ein Beispiel für eine erfolgreiche Rückwärtsauflösung:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramm(\"Papagei\")\n",
    "key = reverse_lookup(h, 2)\n",
    "key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Und ein Beispiel für eine nicht erfolgreiche:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "key = reverse_lookup(h, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Wirkung, wenn wir eine Ausnahme erzeugen, ist die gleiche, wie wenn Python eine erzeugt: es wird ein Stacktrace und eine Fehlermeldung ausgegeben.\n",
    "\n",
    "Der `raise`-Anweisung kann eine detaillierte Fehlermeldung als optionales Argument übergeben werden. Beispielsweise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "raise LookupError(\"Der Wert ist nicht im assoziativen Datenfeld enthalten.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine Rückwärtsauflösung ist deutlich langsamer als eine (Vorwärts)Auflösung; wenn wir sie häufig durchführen müssen oder wenn das assoziative Datenfeld groß wird, wird die Performanz unseres Programms leiden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.5 Assoziative Datenfelder und Listen\n",
    "\n",
    "Listen können als Werte in einem assoziativen Datenfeld verwendet werden! Wenn wir beispielsweise ein assoziatives Datenfeld erhalten, welches Buchstaben auf Häufigkeiten abbildet, möchten wir es vielleicht invertieren, das heißt, ein assoziatives Datenfeld erzeugen, welches Häufigkeiten auf Buchstaben abbildet. Da es mehrere Buchstaben mit der\n",
    "gleichen Häufigkeit geben kann, sollte jeder Wert im des assoziativen Datenfeldes eine Liste von Buchstaben sein.\n",
    "\n",
    "Hier ist eine Funktion, die ein assoziatives Datenfeld invertiert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def invert_dict(d):\n",
    "    inverse = dict()\n",
    "    for key in d:\n",
    "        val = d[key]\n",
    "        if val not in inverse:\n",
    "            inverse[val] = [key]\n",
    "        else:\n",
    "            inverse[val].append(key)\n",
    "    return inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei jedem Schleifendurchlauf wird `key` ein Schlüssel von `d` zugewiesen und `val` der entsprechende Wert. Falls `val` nicht in `inverse` enthalten ist (wir es also noch nicht gesehen haben), wird ein neuer Eintrag erzeugt und mit einem **Singleton** (einer Liste mit genau einem Element) initialisiert. Ansonsten haben wir den Wert bereits gesehen, so dass wir den zugehörigen Schlüssel mittels `append` einfach zur Liste hinzufügen können. \n",
    "\n",
    "Hier ist ein Beispiel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hist = histogramm(\"Papagei\")\n",
    "hist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inverse = invert_dict(hist)\n",
    "inverse "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Zustandsdiagramm für assoziatives Datenfeld](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/zustandsdiagramm_dict.svg)\n",
    "\n",
    "Die Abbildung ist ein Zustandsdiagramm welches `hist` und `inverse` zeigt. Ein assoziatives Datenfeld wird durch eine Kiste mit dem Typ `dict` darüber und den Schlüssel-Wert-Paaren innen repräsentiert. Wenn die Werte ganze Zahlen, Gleitkommazahlen oder Zeichenketten sind, dann zeichnen wir sie innerhalb der Kiste. Listen als Werte zeichnen wir üblicherweise außerhalb der Liste, um das Diagramm einfach zu halten.\n",
    "\n",
    "Wie das Beispiel zeigt, können Listen Werte in einem assoziativen Datenfeld sein, aber sie können keine Schlüssel sein. Schauen wir, was passiert, wenn wir es trotzdem versuchen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = [1, 2, 3]\n",
    "d = dict()\n",
    "d[t] = 'oops'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie bereits erwähnt, werden assoziative Datenfelder mittels Hash-Tabellen implementiert und das bedeutet, dass die Schlüssel **hashbar** (*hashable*) sein müssen.\n",
    "\n",
    "Ein **Hash** ist eine Funktion, die einen Wert (jedweder Art) erwartet und eine ganze Zahl zurückliefert. Assoziative Datenfelder verwenden diese ganzen Zahlen, genannt Hashwerte, um Schlüssel-Wert-Paare zu speichern und aufzulösen. \n",
    "\n",
    "Dieses System funktioniert gut, wenn die Schlüssel unveränderbar (*immutable*) sind. Wenn die Schlüssel jedoch veränderbar sind, wie bei Listen, dann können schlimme Dinge passieren. Wenn wir ein Schlüssel-Wert-Paar erzeuen, dann hasht Python den Schlüssel und speichert den Wert an der entsprechenden Stelle. Wenn wir den Schlüssel verändern und ihn dann noch einmal hashen, dann erhalten wir einen anderen Wert und würden dementsprechend an einer anderen Stelle landen. In diesem Fall könnten wir zwei Einträge für den gleichen Schlüssel haben oder wir finden den Schlüssel nicht. In beiden Fällen würde das assoziative Datenfeld nicht richtig funktionieren. \n",
    "\n",
    "Aus diesem Grund müssen Schlüssel hashbar sein und veränderbare Typen wie Listen sind es nicht. Die einfachste Möglichkeit, diese Einschränkung zu umgehen liegt darin, Tupel zu verwenden, die wir im nächsten Kapitel kennenlernen werden. \n",
    "\n",
    "Da assoziative Datenfelder veränderbar sind, können sie nicht als Schlüssel verwendet werden, aber sie *können* als Werte verwendet werden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.6 Memos\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/3/3e/Cool-smiley.svg)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 5. Kapitel geschafft. Weiter geht es in [6: Ergebnisreiche Funktionen](seminar06.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}