4b. Slow hashing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Slow hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Operations on data structures based on hashing are _usually_ efficient, but it is possible for the operations to be slow due to collisions. We will next see how the Python dictionary becomes slow, when the keys stored there are chosen in a specific way.\n",
    "\n",
    "In order to choose the keys, we need to know the exact implementation of the dictionary. The relevant aspect of the implementation are the hash function, the hash table size and the collision handling.\n",
    "\n",
    "We can find these details in the [Pythonin source code](https://github.com/python/cpython/blob/main/Objects/dictobject.c)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hash function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Python hash function `hash` is implemented differently for different data types. For small enough integers, the hash value is simply the integer itself:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "powershell"
    }
   },
   "outputs": [],
   "source": [
    "> hash(42)\n",
    "42\n",
    "> hash(123)\n",
    "123\n",
    "> hash(1337)\n",
    "1337"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use small integers as keys, so that we can assume the above hash function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hash table size"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The hash table size $N$ of the Python dictionary is initially $8$. The hash table is implemented so that at most $2/3$ of the locations are occupied. If this limit is exceeded, the size of the hash table is doubled.\n",
    "\n",
    "The following code illustrates this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "n = 1000\n",
    "\n",
    "numbers = {}\n",
    "old_size = 0\n",
    "\n",
    "for i in range(n):\n",
    "    new_size = sys.getsizeof(numbers)\n",
    "\n",
    "    if new_size != old_size:\n",
    "        print(len(numbers), sys.getsizeof(numbers))\n",
    "        old_size = new_size\n",
    "\n",
    "    numbers[i] = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code creates a dictionary `numbers` and adds elements to it one at a time. When the memory usage of the hash table changes, the code prints out the number of elements and the memory usage of the hash table. The output of the code is as follows:\n",
    "\n",
    "```\n",
    "0 64\n",
    "1 232\n",
    "6 360\n",
    "11 640\n",
    "22 1176\n",
    "43 2272\n",
    "86 4696\n",
    "171 9312\n",
    "342 18520\n",
    "683 36960\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, the size of the hash table increases when the element count reaches $6$, and then the hash table size increases from $8$ to $16$. The size increases, because the ratio $6/8$ exceeds the limit $2/3$. The size increases again when the element count reaches $11$, because $11/16$ exceeds $2/3$, and then the new size is $32$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Handling collisions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code shows how the Python dictionary chooses the location in the hash table for the pair `(key, value)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "index = hash(key) % N\n",
    "perturb = hash(key)\n",
    "while True:\n",
    "    if not table[index]:\n",
    "        table[index] = (key, value)\n",
    "        break\n",
    "    perturb = perturb >> 5\n",
    "    index = (5 * index + 1 + perturb) % N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that this is not the actual code implementing the dictionary (Python is implemented in the C language), but this code shows the idea.\n",
    "\n",
    "The variable `index` is the location in the hash table and its initial value is computed with the formula `hash(key) % N`. If the location `index` is occupied, the next location to try is computed with the formula `(5 * index + 1 + perturb) % N`. This continues until an unoccupied location is found.\n",
    "\n",
    "The purpose of the variable `perturb` is to make collisions less likely. It affects the location formula for the first few tries. The initial value of `perturb` is the hash value of the key, and in each round its new value is computed as `perturb >> 5`. This bit shift operation corresponds to dividing by $32$ and rounding down."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constructing the input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we know enough about the Python dictionary implementation, and we can design an input that makes the dictionary operations slow. The idea is to use keys that collide with each other and cause the hash table operations slow down. The following code constructs such an input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find(table, key):\n",
    "    N = len(table)\n",
    "    index = hash(key) % N\n",
    "    perturb = hash(key)\n",
    "    count = 0\n",
    "    while True:\n",
    "        count += 1\n",
    "        if not table[index]:\n",
    "            return index, count\n",
    "        perturb = perturb >> 5\n",
    "        index = (5 * index + 1 + perturb) % N\n",
    "\n",
    "n = 100000\n",
    "chain_len = 50000\n",
    "threshold = 5000\n",
    "\n",
    "N = 2**18\n",
    "table = [None] * N\n",
    "keys = []\n",
    "\n",
    "key = 1\n",
    "for i in range(chain_len):\n",
    "    keys.append(key)\n",
    "    key = (5 * key + 1) % N\n",
    "\n",
    "key = chain_len\n",
    "while len(keys) < n:\n",
    "    index, count = find(table, key)\n",
    "    if count > threshold:\n",
    "        table[index] = True\n",
    "        keys.append(key)\n",
    "    key += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code creates an input of `n` keys. The hash table size `N` is chosen accordingly so that the limit of $2/3$ is not exceeded. The list `keys` stores the chosen keys.\n",
    "\n",
    "First, the code adds keys that form a chain of length `chain_len`. The first key in the chain is `1` and the other keys in the chain are computed iteratively with the formula `key = (5 * key + 1) % N`. The chain is designed so that once the sequence of locations tried for a given key gets locked on the chain, it will stay locked on the chain until the end of the chain. Then the code adds the remaining keys so that each key added causes at least `threshold` steps along the chain before an unoccupied location is found. This makes their addition to the dictionary slow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Testing efficiency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code measures how much time it takes to add the keys in the list `keys` to the dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "...\n",
    "\n",
    "start_time = time.time()\n",
    "numbers = {}\n",
    "for key in keys:\n",
    "    numbers[key] = True\n",
    "end_time = time.time()\n",
    "\n",
    "print(round(end_time - start_time, 2), \"s\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us first do a test where the list `keys` contains $10^5$ random numbers in the range $1 \\dots 10^8$. The list can be formed as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "keys = random.sample(range(1, 10**8 + 1), 10**5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This test took 0.02 seconds on the test computer. This is what one would expect when the dictionary operates efficiently.\n",
    "\n",
    "Let us then do the test where the list `keys` is created with the code described above designed to cause a lot of collisions. Now the test time is 10.57 seconds, which is indeed very slow in comparison due to the collisions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Can this happen in practice?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although it is possible to construct an input that makes the dictionary slow, in practice such inputs occur very rarely. In essence, this happens only when the input was specifically designed to do so.\n",
    "\n",
    "However, the existence of such designed inputs can be a problem in web programming, because a malicious attacker could try feeding such data to the site, causing the site to slow down. In python this possibility [has been addressed](https://github.com/python/cpython/issues/57912) by changing the operation of the function `hash` for strings each time Python is started:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "powershell"
    }
   },
   "outputs": [],
   "source": [
    "$ python3\n",
    "> hash(\"apina\")\n",
    "-8847049641918498300\n",
    "> exit()\n",
    "$ python3\n",
    "> hash(\"apina\")\n",
    "5108947336973792736\n",
    "> exit()\n",
    "$ python3\n",
    "> hash(\"apina\")\n",
    "-7637574785741815573\n",
    "> exit()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This makes it impossible to construct a list of string keys that causes the dictionary to slow down."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}