Hash Table/03_collision_Handling_In_hash_table.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hash Table Implementation : Collision Handling In Hash Table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.MAX = 100\n",
    "        self.arr = [None for i in range(self.MAX)]\n",
    "\n",
    "    def get_hash(self, key):\n",
    "        h = 0\n",
    "        for char in key:\n",
    "            h += ord(char)\n",
    "        return h % self.MAX\n",
    "\n",
    "    def __setitem__(self, key, value):\n",
    "        h = self.get_hash(key)\n",
    "        self.arr[h] = value\n",
    "\n",
    "    def __getitem__(self, key):\n",
    "        h = self.get_hash(key)\n",
    "        return self.arr[h]\n",
    "\n",
    "    def __delitem__(self, key):\n",
    "        h = self.get_hash(key)\n",
    "        self.arr[h] = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "82"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj1 = HashTable()\n",
    "obj1.get_hash(\"122-Mar\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "82"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj1.get_hash(\"1-Mar\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [],
   "source": [
    "obj1[\"1-Mar\"] = 550\n",
    "obj1[\"122-Mar\"] = 120"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Here the '09-Mar' and '18-Mar' have same index (38) but value is overriding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj1[\"1-Mar\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hash Table Collision Handling Using Chaining"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashTable:  \n",
    "    def __init__(self):\n",
    "        self.MAX = 10\n",
    "        self.arr = [[] for i in range(self.MAX)]\n",
    "        \n",
    "    def get_hash(self, key):\n",
    "        hash = 0\n",
    "        for char in key:\n",
    "            hash += ord(char)\n",
    "        return hash % self.MAX\n",
    "    \n",
    "    def __getitem__(self, key):\n",
    "        h = self.get_hash(key)\n",
    "        for element in self.arr[h]:\n",
    "            if element[0] == key:\n",
    "                return element[1]\n",
    "            \n",
    "    def __setitem__(self, key, val):\n",
    "        h = self.get_hash(key)\n",
    "        found = False\n",
    "        for idx, element in enumerate(self.arr[h]):\n",
    "            if len(element)==2 and element[0] == key:\n",
    "                self.arr[h][idx] = (key,val)\n",
    "                found = True\n",
    "        if not found:\n",
    "            self.arr[h].append((key,val))\n",
    "        \n",
    "    def __delitem__(self, key):\n",
    "        h = self.get_hash(key)\n",
    "        for index, element in enumerate(self.arr[h]):\n",
    "            if element[0] == key:\n",
    "                print(\"del\",index)\n",
    "                del self.arr[h][index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "obj2 = HashTable()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [],
   "source": [
    "obj2[\"1-Mar\"] = 550\n",
    "obj2[\"122-Mar\"] = 120"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "550"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj2[\"1-Mar\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj2[\"122-Mar\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[], [], [('1-Mar', 550), ('122-Mar', 120)], [], [], [], [], [], [], []]"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj2.arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "del 1\n"
     ]
    }
   ],
   "source": [
    "del obj2['122-Mar']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[], [], [('1-Mar', 550)], [], [], [], [], [], [], []]"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj2.arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "del 0\n"
     ]
    }
   ],
   "source": [
    "del obj2['1-Mar']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[], [], [], [], [], [], [], [], [], []]"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj2.arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.7 64-bit",
   "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.10.7"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "10e9aac84282539994078db1be2f537695a8865e78eb5e3c29f0b2ce90162212"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}