{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3d8e2fd4-0b32-43f7-9a27-a240ecbc73e4",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/usr/bin/python3\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "print(sys.executable)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf3bcaf1-d1c3-4994-8f86-e945ebdfe0a3",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# Table de hachage\n",
    "\n",
    "Pour implémenter un dictionnaire, on crée une liste de taille fixe $N$ puis, à chaque clé, on associe un indice \n",
    "$i$ compris entre $0$ et $N-1$. On stocke le tuple (clé,valeur) à l'indice $i$.\n",
    "\n",
    "On appelle **fonction de hachage**, la fonction qui, à chaque clé, fait correspondre l'indice de la clé.\n",
    "\n",
    "Une fonction de hachage n'est pas injective en général. Autrement dit, un même indice peut très bien correspondre à plusieurs clés. On dit alors qu'il y a collision.\n",
    "\n",
    "Prenons l'exemple où les clés sont des chaînes de caractères. La fonction qui renvoie la longueur est une fonction de hachage. Dans ce cas, des clés de même longueur provoquent des collisions.\n",
    "\n",
    "Les collisions sont toujours possibles mais doivent être le plus possible évitées. Pour cela, on doit choisir une valeur de $N$ assez grande (en tout cas nettement plus grande que la longueur du dictionnaire) et une \"bonne\" fonction de hachage.\n",
    "\n",
    "Lorsqu'il y a collision, on peut par exemple choisir la première case du tableau disponible après l'indice obtenu par la fonction de hachage. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4595934e-673f-4f4f-8ea2-325444d31439",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "**Exercice 1**\n",
    "\n",
    "On considère la fonction de hachage suivante. Pour chaque clé de longueur $n$, on note $a_0, \\ldots, a_{n-1}$ le code ASCII de ses lettres de droite à gauche et on considère\n",
    "le polynôme\n",
    "$$\\displaystyle P(X)= \\sum_{k=0}^{n-1} a_k X^k$$\n",
    "\n",
    "Ecrire la fonction de hachage `hachage` qui calcule $P(256)$ modulo $N$. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b541b89-69f3-43d5-b879-1d981be43ebb",
   "metadata": {},
   "source": [
    "**Rappels**\n",
    "\n",
    "- le reste et le quotient de la division euclidienne de $a$ par $b$ sont donnés par les opérations `%` et `//`.\n",
    "- la fonction `ord()` convertit tout caractère alphanumérique en son code ASCII qui est un nombre compris entre $0$ et $255$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "78e99087-9f54-457e-be3d-552db27bf139",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "reste= 5\n",
      "quotient= 2\n",
      "A: 65 ;  B: 66 ;  a: 97\n"
     ]
    }
   ],
   "source": [
    "print('reste=',19%7)\n",
    "print('quotient=',19//7)\n",
    "print('A:',ord('A'),';  B:',ord('B'),';  a:',ord('a'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a4ff647e-4fdf-48ac-89ab-c04c6f879b13",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hachage(cle,N):\n",
    "    s=0\n",
    "    ...\n",
    "    return s      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67948a8e-e342-4ab0-8fa8-5998094d487f",
   "metadata": {},
   "outputs": [],
   "source": [
    "hachage('mot',300)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfdbca43-4c23-44af-bff9-12626a6126cb",
   "metadata": {},
   "source": [
    "**Exercice 2**\n",
    "\n",
    "1. Ecrire une foncion `implementation1` qui stocke un dictionnaire dans une liste de taille $N$ en utilisant la fonction hachage de l'exercice 1. La fonction renvoie `False` s'il y a une collision, elle renvoie la liste s'il n'y en a pas. La fonction prend en entrée l'entier $N$ et les listes `Cles`, `Valeurs`.\n",
    "2. On veut implementer le dictionnaire dont les clés sont les mois en anglais et les valeurs les mois correspondant en français. Trouver le plus petit $N$ qui convient.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "14e00364-fdb3-42f3-ba6c-e8f268f8ae3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def implementation1(N, Cles, Valeurs):\n",
    "    ...\n",
    "    return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3edb8b2-c1a4-4aaa-9d1b-c115a021b8c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "mois=['janvier','février','mars','avril','mai','juin','juillet',\n",
    "      'août','septembre','octobre','novembre','décembre']\n",
    "months=['january','february','march','april','mai','june',\n",
    "        'july','august','september','october','november','december']\n",
    "N=12\n",
    "...\n",
    "print(N)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "838c93c9-0bde-4907-be6f-3eef180ecdeb",
   "metadata": {},
   "source": [
    "**Exercice 3**\n",
    "\n",
    "Ecrire une fonction `recherche1` dont les paramètres sont une chaîne de caractère `mot`  et une liste $L$ obtenue par la fonction `implementation1`. \n",
    "\n",
    "Cette fonction calcule la valeur hachage de `mot`, vérifie qu'il se trouve bien dans la liste $L$. La fonction renvoie dans ce cas le mot associé sinon elle renvoie `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "ada11d0e-b7f9-4da5-b2ab-03d26a94a2d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherche1(mot,L):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5e7c6d1-813c-4bc7-851e-f955dce25023",
   "metadata": {},
   "outputs": [],
   "source": [
    "L=implementation1(27,months,mois)\n",
    "recherche1('march',L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7703577c-e87c-48ac-a6f3-d443b95e0765",
   "metadata": {},
   "source": [
    "**Exercice 4**\n",
    "\n",
    "1. Implémenter un dictionnaire, sans utiliser de table de hachage, à l'aide d'une liste dont les éléments sont les tuples `(clé,valeur)`. La fonction prend en entrée les listes *Cles* et *Valeurs*.\n",
    "2. Ecrire une fonction qui renvoie la valeur d'une clé d'un dictionnaire. La fonction prend en entrée une liste $L$ (contenant le dictionnaire) et une chaîne de caractères `mot`. Si la clé n'est pas dans le dictionnaire, la fonction renvoie `False`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "b086d9a2-345a-4fbf-b505-b27e4200cd89",
   "metadata": {},
   "outputs": [],
   "source": [
    "def implementation2(Cles,Valeurs):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "1b64a3f7-c303-4d7c-b633-d5b4e389c848",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherche2(L,mot):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "afc7c34c-b82d-4e02-bd4a-0145b4fc3770",
   "metadata": {},
   "outputs": [],
   "source": [
    "L=implementation2(months,mois)\n",
    "recherche2(L,'february')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b0ecd53-d453-4d53-9361-3a9a4c71ddea",
   "metadata": {},
   "source": [
    "**Exercice 5**\n",
    "\n",
    "Calculer la complexité des deux fonctions de recherche.\n",
    "Comparer les deux implémentations (avantages et inconvénients de chaque méthode). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f47954fb-1022-4c02-a06a-38db29242511",
   "metadata": {},
   "source": [
    "**Exercice 6**\n",
    "\n",
    "1. Ecrire une fonction `implementation3` qui améliore la fonction `implementation1`: en cas de collision, la fonction cherche la première place libre après la valeur de hachage (on revient à $0$ si on arrive au bout de la liste).\n",
    "2. Ecrire la fonction de recherche associée à cette implémentation.\n",
    "3. Tester en prenant $N=50$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "588b922e-98f0-45a0-8f10-3d7493046245",
   "metadata": {},
   "outputs": [],
   "source": [
    "def implementation3(N,Cles,Valeurs):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19fe8441-0518-4551-a0e3-601880d97c48",
   "metadata": {},
   "outputs": [],
   "source": [
    "L=implementation3(50,months,mois)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "1fe17c2b-e88b-48a4-9141-e2455b3d81b8",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def recherche3(mot,L):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6627e38-e892-4e6b-b7b6-e225d826a4fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "recherche3('december',L)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}