4 Algorithmen Grundlagen/7-Sorting and Searching/3-Implementation of a Hash Table.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of a Hash Table\n",
    "\n",
    "In this lecture we will be implementing our own Hash Table to complete our understanding of Hash Tables and Hash Functions! Make sure to review the video lecture before this to fully understand this implementation!\n",
    "\n",
    "Keep in mind that Python already has a built-in dictionary object that serves as a Hash Table, you would never actually need to implement your own hash table in Python.\n",
    "\n",
    "___\n",
    "## Map\n",
    "The idea of a dictionary used as a hash table to get and retrieve items using **keys** is often referred to as a mapping. In our implementation we will have the following methods:\n",
    "\n",
    "\n",
    "* **HashTable()** Create a new, empty map. It returns an empty map collection.\n",
    "* **put(key,val)** Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.\n",
    "* **get(key)** Given a key, return the value stored in the map or None otherwise.\n",
    "* **del** Delete the key-value pair from the map using a statement of the form del map[key].\n",
    "* **len()** Return the number of key-value pairs stored \n",
    "* **in** the map in Return True for a statement of the form **key in map**, if the given key is in the map, False otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class HashTable(object):\n",
    "    \n",
    "    def __init__(self,size):\n",
    "        \n",
    "        # Set up size and slots and data\n",
    "        self.size = size\n",
    "        self.slots = [None] * self.size\n",
    "        self.data = [None] * self.size\n",
    "        \n",
    "    def put(self,key,data):\n",
    "        #Note, we'll only use integer keys for ease of use with the Hash Function\n",
    "        \n",
    "        # Get the hash value\n",
    "        hashvalue = self.hashfunction(key,len(self.slots))\n",
    "\n",
    "        # If Slot is Empty\n",
    "        if self.slots[hashvalue] == None:\n",
    "            self.slots[hashvalue] = key\n",
    "            self.data[hashvalue] = data\n",
    "        \n",
    "        else:\n",
    "            \n",
    "            # If key already exists, replace old value\n",
    "            if self.slots[hashvalue] == key:\n",
    "                self.data[hashvalue] = data  \n",
    "            \n",
    "            # Otherwise, find the next available slot\n",
    "            else:\n",
    "                \n",
    "                nextslot = self.rehash(hashvalue,len(self.slots))\n",
    "                \n",
    "                # Get to the next slot\n",
    "                while self.slots[nextslot] != None and self.slots[nextslot] != key:\n",
    "                    nextslot = self.rehash(nextslot,len(self.slots))\n",
    "                \n",
    "                # Set new key, if NONE\n",
    "                if self.slots[nextslot] == None:\n",
    "                    self.slots[nextslot]=key\n",
    "                    self.data[nextslot]=data\n",
    "                    \n",
    "                # Otherwise replace old value\n",
    "                else:\n",
    "                    self.data[nextslot] = data \n",
    "\n",
    "    def hashfunction(self,key,size):\n",
    "        # Remainder Method\n",
    "        return key%size\n",
    "\n",
    "    def rehash(self,oldhash,size):\n",
    "        # For finding next possible positions\n",
    "        return (oldhash+1)%size\n",
    "    \n",
    "    \n",
    "    def get(self,key):\n",
    "        \n",
    "        # Getting items given a key\n",
    "        \n",
    "        # Set up variables for our search\n",
    "        startslot = self.hashfunction(key,len(self.slots))\n",
    "        data = None\n",
    "        stop = False\n",
    "        found = False\n",
    "        position = startslot\n",
    "        \n",
    "        # Until we discern that its not empty or found (and haven't stopped yet)\n",
    "        while self.slots[position] != None and not found and not stop:\n",
    "            \n",
    "            if self.slots[position] == key:\n",
    "                found = True\n",
    "                data = self.data[position]\n",
    "                \n",
    "            else:\n",
    "                position=self.rehash(position,len(self.slots))\n",
    "                if position == startslot:\n",
    "                    \n",
    "                    stop = True\n",
    "        return data\n",
    "\n",
    "    # Special Methods for use with Python indexing\n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "\n",
    "    def __setitem__(self,key,data):\n",
    "        self.put(key,data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see it in action!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "h = HashTable(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Put our first key in\n",
    "h[1] = 'one'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "h[2] = 'two'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "h[3] = 'three'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "h[1] = 'new_one'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'new_one'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print h[4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Great Job!\n",
    "\n",
    "That's it for this rudimentary implementation, try implementing a different hash function for practice!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}