DSA_Notebooks/Dictionaries_HashTables.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Hash Tables and Python Dictionaries</h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating Dictionaries\n",
    "\n",
    "---\n",
    "\n",
    "Let's suppose we create a dictionary to store Name and Phone number "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "phone_book = {\n",
    "    'vivek': '9049872675',\n",
    "    'madhu': '8736484938',\n",
    "    'alpana': '9376449374',\n",
    "    'anu' : 74\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Printing a dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'vivek': '9049872675', 'madhu': '8736484938', 'alpana': '9376449374', 'anu': '7473874389'}\n"
     ]
    }
   ],
   "source": [
    "print(phone_book)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Getting the value from the key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'9049872675'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phone_book['vivek']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can store new phone numbers, or update existing ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'vivek': '9049872675',\n",
       " 'madhu': '8736484938',\n",
       " 'alpana': '9376449374',\n",
       " 'anu': 75,\n",
       " 'himanshu': '9373762649'}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phone_book['himanshu'] = '9373762649'\n",
    "phone_book['anu'] = phone_book['anu'] + 1\n",
    "phone_book"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Names and phone numbers stored in `phone_book` can be accessed using a `for` loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vivek's Phone Number is 9049872675\n",
      "madhu's Phone Number is 8736484938\n",
      "alpana's Phone Number is 9376449374\n",
      "anu's Phone Number is 8888888888\n",
      "himanshu's Phone Number is 9373762649\n"
     ]
    }
   ],
   "source": [
    "for name in phone_book:\n",
    "    print(f\"{name}'s Phone Number is {phone_book[name]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counter from dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vivek 9049872675\n",
      "madhu 8736484938\n",
      "alpana 9376449374\n",
      "anu 74\n"
     ]
    }
   ],
   "source": [
    "# items return both key and value\n",
    "phone_book = {\n",
    "    'vivek': '9049872675',\n",
    "    'madhu': '8736484938',\n",
    "    'alpana': '9376449374',\n",
    "    'anu' : 74\n",
    "}\n",
    "\n",
    "for key, value in phone_book.items():\n",
    "    print( key, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "anu 0\n",
      "anu 0\n",
      "alp 0\n",
      "alp 0\n",
      "alp 0\n",
      "viv 0\n",
      "viv 0\n"
     ]
    }
   ],
   "source": [
    "# elements return both key\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "z = [\"anu\", \"anu\", \"alp\",\"alp\", \"alp\", \"viv\", \"viv\"]\n",
    "phone_book = Counter(z)\n",
    "\n",
    "for key in phone_book.elements():\n",
    "    print( key, phone_book['keys'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating a hash table in python "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "    def insert(self, key, value):\n",
    "        pass\n",
    "\n",
    "    def find(self, key):\n",
    "        pass\n",
    "\n",
    "    def update(self, key, value):\n",
    "        pass\n",
    "\n",
    "    def list_all(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a Python list which will hold all the key-value pairs. We'll start by creating a list of a fixed size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAX_HASH_TABLE_SIZE = 4096"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**QUESTION 1: Create a Python list of size `MAX_HASH_TABLE_SIZE`, with all the values set to `None`.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_list = [None] * MAX_HASH_TABLE_SIZE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4096"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(data_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "for item in data_list:\n",
    "    assert item == None, \"Not all items are None\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hashing Function\n",
    "\n",
    "A _hashing function_ is used to convert strings and other non-numeric data types into numbers, which can then be used as list indices. For instance, if a hashing function converts the string `\"Aakash\"` into the number `4`, then the key-value pair `('Aakash', '7878787878')` will be stored at the position `4` within the data list.\n",
    "\n",
    "Here's a simple algorithm for hashing, which can convert strings into numeric list indices.\n",
    "\n",
    "1. Iterate over the string, character by character\n",
    "2. Convert each character to a number using Python's built-in `ord` function.\n",
    "3. Add the numbers for each character to obtain the hash for the entire string \n",
    "4. Take the remainder of the result with the size of the data list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_index(data_list, a_string):\n",
    "    result = 0\n",
    "    for a_character in a_string:\n",
    "        a_number = ord(a_character)\n",
    "        result +=a_number\n",
    "    list_index = result % MAX_HASH_TABLE_SIZE\n",
    "    return list_index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "585"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_index(data_list, \"Aakash\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Insert\n",
    "\n",
    "To insert a key-value pair into a hash table, we can simply get the hash of the key, and store the pair at that index in the data list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "key, value = 'Aakash', '7878787878'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "585"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "idx = get_index(data_list, key)\n",
    "idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_list[idx] = (key, value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the same operation expressed in a single line of code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_list[get_index(data_list, 'Hemanth')] = ('Hemanth', '9595949494')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Find\n",
    "\n",
    "The retrieve the value associated with a pair, we can get the hash of the key and look up that index in the data list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "585"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "idx = get_index(data_list, 'Aakash')\n",
    "idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Aakash', '7878787878')"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "key, value = data_list[idx]\n",
    "key, value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### List\n",
    "\n",
    "To get the list of keys, we can use a simple [list comprehension](https://www.w3schools.com/python/python_lists_comprehension.asp)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Listing all Keys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "keys = [kv[0] for kv in data_list if kv is not None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Aakash', 'Hemanth']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Listing all Values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "values = [kv[1] for kv in data_list if kv is not None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['7878787878', '9595949494']"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic Hash Table Implementation\n",
    "\n",
    "We can now use the hashing function defined above to implement a basic hash table in Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BasicHashTable:\n",
    "    def __init__(self, max_size = MAX_HASH_TABLE_SIZE):\n",
    "        self.data_list = [None] * max_size\n",
    "    \n",
    "    def insert(self, key, value):\n",
    "        idx = get_index(self.data_list, key)\n",
    "        self.data_list[idx] = key, value\n",
    "    \n",
    "    def find(self, key):\n",
    "        idx = get_index(self.data_list, key)\n",
    "        kv = self.data_list[idx]\n",
    "        \n",
    "        if kv is None:\n",
    "            return None\n",
    "        else:\n",
    "            key, value = kv\n",
    "            return value\n",
    "\n",
    "    def update(self, key, value):\n",
    "        idx = get_index(self.data_list, key)\n",
    "        self.data_list[idx] = key,value\n",
    "\n",
    "    def list_all(self):\n",
    "        return [(kv[0], kv[1]) for kv in self.data_list if kv is not None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "basic_table = BasicHashTable(max_size = 1024)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(basic_table.data_list) == 1024"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insert Values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "basic_table.insert('viv', 8755667986)\n",
    "basic_table.insert('vivek', 9998887776)\n",
    "basic_table.insert('vivka', 9991111555)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find Value using key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8755667986"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basic_table.find(\"viv\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Update Value of a key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "basic_table.update(\"viv\", \"9999333666\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "List All key value pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('viv', '9999333666'), ('vivka', 9991111555), ('vivek', 9998887776)]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basic_table.list_all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Handling Collisions with Linear Probing\n",
    "\n",
    "As multiple keys can have the same hash. For instance, the keys `\"listen\"` and `\"silent\"` have the same hash. This is referred to as _collision_. Data stored against one key may override the data stored against another, if they have the same hash.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "basic_table.insert('listen', 99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "basic_table.insert('silent', 200)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "200"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basic_table.find('listen')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To handle collisions we'll use a technique called linear probing. Here's how it works: \n",
    "\n",
    "1. While inserting a new key-value pair if the target index for a key is occupied by another key, then we try the next index, followed by the next and so on till we the closest empty location.\n",
    "\n",
    "2. While finding a key-value pair, we apply the same strategy, but instead of searching for an empty location, we look for a location which contains a key-value pair with the matching key.\n",
    "\n",
    "3. While updating a key-value pair, we apply the same strategy, but instead of searching for an empty location, we look for a location which contains a key-value pair with the matching key, and update its value.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_valid_index(data_list, key):\n",
    "    # Start with the index returned by get_index\n",
    "    idx = get_index(data_list, key)\n",
    "    \n",
    "    while True:\n",
    "        # Get the key-value pair stored at idx\n",
    "        kv = data_list[idx]\n",
    "        \n",
    "        # If it is None, return the index\n",
    "        if kv == None:\n",
    "            return idx\n",
    "        \n",
    "        # If the stored key matches the given key, return the index\n",
    "        k, v = kv\n",
    "        if key == k:\n",
    "            return idx\n",
    "        \n",
    "        # Move to the next index\n",
    "        idx += 1\n",
    "        \n",
    "        # Go back to the start if you have reached the end of the array\n",
    "        if idx == len(data_list):\n",
    "            idx = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hash Table with Linear Probing\n",
    "\n",
    "We can now implement a hash table with linear probing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ProbingHashTable:\n",
    "    def __init__(self, max_size=MAX_HASH_TABLE_SIZE):\n",
    "        # 1. Create a list of size `max_size` with all values None\n",
    "        self.data_list = [None] * max_size\n",
    "     \n",
    "    \n",
    "    def insert(self, key, value):\n",
    "        # 1. Find the index for the key using get_valid_index\n",
    "        idx = get_valid_index(self.data_list, key)\n",
    "        \n",
    "        # 2. Store the key-value pair at the right index\n",
    "        self.data_list[idx] = key, value\n",
    "    \n",
    "    \n",
    "    def find(self, key):\n",
    "        # 1. Find the index for the key using get_valid_index\n",
    "        idx = get_valid_index(self.data_list, key)\n",
    "        \n",
    "        # 2. Retrieve the data stored at the index\n",
    "        kv = self.data_list[idx]\n",
    "        \n",
    "        # 3. Return the value if found, else return None\n",
    "        return None if kv is None else kv[1]\n",
    "    \n",
    "    \n",
    "    def update(self, key, value):\n",
    "        # 1. Find the index for the key using get_valid_index\n",
    "        idx = get_valid_index(self.data_list, key)\n",
    "        \n",
    "        # 2. Store the new key-value pair at the right index\n",
    "        self.data_list[idx] = key, value\n",
    "\n",
    "    \n",
    "    def list_all(self):\n",
    "        # 1. Extract the key from each key-value pair \n",
    "        return [kv[0] for kv in self.data_list if kv is not None]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the `ProbingHashTable` class was defined correctly, the following cells should output `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Create a new hash table\n",
    "probing_table = ProbingHashTable()\n",
    "\n",
    "# Insert a value\n",
    "probing_table.insert('listen', 99)\n",
    "\n",
    "# Check the value\n",
    "probing_table.find('listen') == 99"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Insert a colliding key\n",
    "probing_table.insert('silent', 200)\n",
    "\n",
    "# Check the new and old keys\n",
    "probing_table.find('listen') == 99 and probing_table.find('silent') == 200"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Update a key\n",
    "probing_table.insert('listen', 101)\n",
    "\n",
    "# Check the value\n",
    "probing_table.find('listen') == 101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "probing_table.list_all() == ['listen', 'silent']"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 64-bit (windows store)",
   "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.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a184b04f7e4cfe8ad73578cf659e38bf16860da1fe2b411d933321707ccf3233"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}