chapter_11.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 11 -- Hash tables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from objects import DoublyLinkedList\n",
    "\n",
    "class ChainedHashTable(object):\n",
    "    \n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.node = DoublyLinkedList\n",
    "        self.data = [self.node() for i in range(size)]\n",
    "        \n",
    "    def delete(self, item):\n",
    "        key = self.shorthash(item)\n",
    "        self.data[key].delete(item)\n",
    "        \n",
    "    def insert(self, item):\n",
    "        key = self.shorthash(item)\n",
    "        self.data[key].insert(item)\n",
    "        \n",
    "    def search(self, item):\n",
    "        key = self.shorthash(item)\n",
    "        return self.data[key].search(item)\n",
    "        \n",
    "    def shorthash(self, item):\n",
    "        return hash(item) % self.size\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[0, 'sentinel', 0]], [[0, 'sentinel', 0]], [[1, 'sentinel', 1], [0, 'dillon', 0]], [[0, 'sentinel', 0]], [[2, 'sentinel', 1], [0, 'bob', 2], [1, 'cat', 0]], [[0, 'sentinel', 0]], [[0, 'sentinel', 0]], [[1, 'sentinel', 1], [0, 'alice', 0]], [[0, 'sentinel', 0]], [[0, 'sentinel', 0]]]\n"
     ]
    }
   ],
   "source": [
    "table = ChainedHashTable(10)\n",
    "for name in ['alice', 'bob', 'cat', 'dillon']:\n",
    "    table.insert(name)\n",
    "print(table.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, None, 1)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "table.search('bob'), table.delete('alice'), table.search('bob')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class AddressedHashTable(object):\n",
    "    \n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.data = [None for i in range(self.size)]\n",
    "        \n",
    "    def delete(self, item):\n",
    "        key = self.search(item)\n",
    "        self.data[key] = 'DELETED'\n",
    "        \n",
    "    def insert(self, item):\n",
    "        for key in self.probhash(item):\n",
    "            if self.data[key] in [None, 'DELETED']:\n",
    "                self.data[key] = item\n",
    "                break\n",
    "        \n",
    "    def probhash(self, item):\n",
    "        raise NotImplementedError\n",
    "        \n",
    "    def search(self, item):\n",
    "        for key in self.probhash(item):\n",
    "            if self.data[key] == None:\n",
    "                return None\n",
    "            elif self.data[key] == item:\n",
    "                return key\n",
    "\n",
    "class LinearHashTable(AddressedHashTable):\n",
    "    \n",
    "    def __init__(self, size):\n",
    "        super(LinearHashTable, self).__init__(size)\n",
    "        \n",
    "    def probhash(self, item):\n",
    "        for probe in range(self.size):\n",
    "            yield (hash(item) + probe) % self.size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, None, 'dillon', None, 'bob', 'cat', None, 'alice', None, None]\n"
     ]
    }
   ],
   "source": [
    "table = LinearHashTable(10)\n",
    "for name in ['alice', 'bob', 'cat', 'dillon']:\n",
    "    table.insert(name)\n",
    "print(table.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, None, 4)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "table.search('bob'), table.delete('alice'), table.search('bob')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class DoubleHashTable(AddressedHashTable):\n",
    "    \n",
    "    def __init__(self, size):\n",
    "        super(DoubleHashTable, self).__init__(size)\n",
    "        \n",
    "    def probhash(self, item):\n",
    "        for probe in range(self.size):\n",
    "            yield (hash(item) + probe * hash(item)) % self.size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, None, 'dillon', None, 'bob', None, None, 'alice', 'cat', None]\n"
     ]
    }
   ],
   "source": [
    "table = DoubleHashTable(10)\n",
    "for name in ['alice', 'bob', 'cat', 'dillon']:\n",
    "    table.insert(name)\n",
    "print(table.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, None, 4)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "table.search('bob'), table.delete('alice'), table.search('bob')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}