Chapter_11_Hash_Tables/exercises_11.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11.4 Open addressing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4-1\n",
    "\n",
    "> Consider inserting the keys $10, 22, 31, 4, 15, 28, 17, 88, 59$ into a hash table of length $m = 11$ using open addressing with the auxiliary hash function $h'(k) = k$. Illustrate the result of inserting these keys using linear probing, using quadratic probing with $c_1 = 1$ and $c_2 = 3$, and using double hashing with $h_1(k) = k$ and $h_2(k) = 1 + (k ~\\text{mod}~ (m - 1))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 11\n",
    "\n",
    "\n",
    "class LinearProbing:\n",
    "    def __init__(self):\n",
    "        global m\n",
    "        self.slots = [None for _ in xrange(m)]\n",
    "\n",
    "    def insert(self, key):\n",
    "        global m\n",
    "        i = 0\n",
    "        while True:\n",
    "            pos = (key + i) % m\n",
    "            if self.slots[pos] is None:\n",
    "                break\n",
    "            i += 1\n",
    "        self.slots[pos] = key\n",
    "\n",
    "\n",
    "class QuadraticProbing:\n",
    "    def __init__(self):\n",
    "        global m\n",
    "        self.slots = [None for _ in xrange(m)]\n",
    "\n",
    "    def insert(self, key):\n",
    "        global m\n",
    "        i = 0\n",
    "        while True:\n",
    "            pos = (key + i + 3 * i * i) % m\n",
    "            if self.slots[pos] is None:\n",
    "                break\n",
    "            i += 1\n",
    "        self.slots[pos] = key\n",
    "\n",
    "\n",
    "class DoubleHashing:\n",
    "    def __init__(self):\n",
    "        global m\n",
    "        self.slots = [None for _ in xrange(m)]\n",
    "\n",
    "    def insert(self, key):\n",
    "        global m\n",
    "        i = 0\n",
    "        h2 = 1 + (key % (m - 1))\n",
    "        while True:\n",
    "            pos = (key + i * h2) % m\n",
    "            if self.slots[pos] is None:\n",
    "                break\n",
    "            i += 1\n",
    "        self.slots[pos] = key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linear: [22, 88, None, None, 4, 15, 28, 17, 59, 31, 10]\n",
    "\n",
    "Quadratic: [22, None, 88, 17, 4, None, 28, 59, 15, 31, 10]\n",
    "\n",
    "Double: [22, None, 59, 17, 4, 15, 28, 88, None, 31, 10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4-2\n",
    "\n",
    "> Write pseudocode for HASH-DELETE as outlined in the text, and modify HASHINSERT to handle the special value DELETED."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 5\n",
    "\n",
    "\n",
    "class LinearProbing:\n",
    "    def __init__(self):\n",
    "        global m\n",
    "        self.slots = [None for _ in xrange(m)]\n",
    "\n",
    "    def insert(self, key):\n",
    "        global m\n",
    "        i = 0\n",
    "        while True:\n",
    "            pos = (key + i) % m\n",
    "            if self.slots[pos] is None or self.slots[pos] == '[Deleted]':\n",
    "                break\n",
    "            i += 1\n",
    "        self.slots[pos] = key\n",
    "\n",
    "    def delete(self, key):\n",
    "        global m\n",
    "        i = 0\n",
    "        while True:\n",
    "            pos = (key + i) % m\n",
    "            if self.slots[pos] is None:\n",
    "                break\n",
    "            if self.slots[pos] == key:\n",
    "                self.slots[pos] = '[Deleted]'\n",
    "                break\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4-3\n",
    "\n",
    "> Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is 3/4 and when it is 7/8."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\alpha=3/4$, unsuccessful: $\\displaystyle\\frac{1}{1-\\frac{3}{4}} = 4$ probes, successful: $\\displaystyle \\frac{1}{\\frac{3}{4}} \\ln \\frac{1}{1-\\frac{3}{4}} \\approx 1.848$ probes.\n",
    "\n",
    "$\\alpha=7/8$, unsuccessful: $\\displaystyle\\frac{1}{1-\\frac{7}{8}} = 8$ probes, successful: $\\displaystyle \\frac{1}{\\frac{7}{8}} \\ln \\frac{1}{1-\\frac{7}{8}} \\approx 2.377$ probes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4-4 $\\star$\n",
    "\n",
    "> Suppose that we use double hashing to resolve collisions—that is, we use the hash function $h(k, i) = (h_1(k) + ih_2(k)) ~\\text{mod}~ m$. Show that if $m$ and $h_2(k)$ have greatest common divisor $d \\ge 1$ for some key $k$, then an unsuccessful search for key $k$ examines $(1/d)$th of the hash table before returning to slot $h_1(k)$. Thus, when $d = 1$, so that $m$ and $h_2(k)$ are relatively prime, the search may examine the entire hash table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $d = \\gcd(m, h_2(k))$, the LCM $l = m \\cdot h_2(k) / d$.\n",
    "\n",
    "Since $d | h_2(k)$, then $m \\cdot h_2(k) / d ~\\text{mod}~ m = 0 \\cdot (h_2(k) / d ~\\text{mod}~ m) = 0$, therefore $(l + ih_2(k)) ~\\text{mod}~ m = ih_2(k) ~\\text{mod}~ m$, which means $ih_2(k) ~\\text{mod}~ m$ has a period of $m/d$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.4-5 $\\star$\n",
    "\n",
    "> Consider an open-address hash table with a load factor $\\alpha$. Find the nonzero value $\\alpha$ for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search. Use the upper bounds given by Theorems 11.6 and 11.8 for these expected numbers of probes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{1}{1 - \\alpha} = 2 \\cdot \\frac{1}{\\alpha} \\ln \\frac{1}{1 - \\alpha}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\alpha = 0.71533\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}