demo_nodict.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "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.7.4"
    },
    "colab": {
      "name": "demo_nodict.ipynb",
      "provenance": [],
      "private_outputs": true,
      "collapsed_sections": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/KenzieAcademy/python-notebooks/blob/master/demo_nodict.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t1CpEpQrJfe1",
        "colab_type": "text"
      },
      "source": [
        "<table border=\"0\" align=\"left\" width=\"700\" height=\"144\">\n",
        "<tbody>\n",
        "<tr>\n",
        "<td width=\"120\"><img width=\"100\" src=\"https://static1.squarespace.com/static/5992c2c7a803bb8283297efe/t/59c803110abd04d34ca9a1f0/1530629279239/\" /></td>\n",
        "<td style=\"width: 600px; height: 67px;\">\n",
        "<h1 style=\"text-align: left;\">Interview Question</h1>\n",
        "<h3 style=\"text-align: left;\">Create your own Dict class without using the 'dict' keyword.</h3>\n",
        "</td>\n",
        "</tr>\n",
        "</tbody>\n",
        "</table>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X3boAo04KT4Y",
        "colab_type": "text"
      },
      "source": [
        "### This coding test question was asked during an actual technical interview of a Kenzie student: \n",
        "\n",
        "> \"Create a class that behaves like a Python `dict`.  However, the class definition cannot use the `dict` keyword or Python dictionary class objects.\"\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "92bwH6P2METU",
        "colab_type": "text"
      },
      "source": [
        "This is difficult problem, but not beyond our comprehension.  If we spend some time to outline and understand the problem first, then coding it becomes easier.\n",
        "\n",
        "- Study the properties of a dictionary:\n",
        "   - Fast lookups (uses hashing instead of indexing)\n",
        "   - What is hashing?\n",
        "   - Uses 'buckets' internally.  What's a bucket?\n",
        "   - How are duplicates handled?\n",
        "   - How to handle square-bracket lookups?\n",
        "- Model a key-value pair as a distinct OOP Thing.\n",
        "- Model our dict as a container of those key-value OOP Thingys."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A9kkDYzVOx-h",
        "colab_type": "text"
      },
      "source": [
        "## `<Derail>` Part I: Hashing\n",
        "Hashing is the process of using an algorithm to map data of any size to a fixed length. This is called a hash value. Hashing is used to create high performance, direct access data structures where large amount of data is to be stored and accessed quickly. Hash values are computed with hash functions.\n",
        "\n",
        "### Let's look at what kinds of types are hashable in Python ..."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aw84NDkOO6gb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# What are some hashable objects in Python?\n",
        "# You may be tempted to simply check for the presence of a __hash__ method ...\n",
        "print(f\"String is hashable? {hasattr(str, '__hash__')}\")\n",
        "print(f\"List is hashable? {hasattr(list, '__hash__')}\")\n",
        "print(f\"Int is hashable? {hasattr(int, '__hash__')}\")\n",
        "print(f\"Set is hashable? {hasattr(set, '__hash__')}\")\n",
        "print(f\"Tuple is hashable? {hasattr(tuple, '__hash__')}\")\n",
        "\n",
        "# But remember: All built-in data types inherit from the generic 'object' class.\n",
        "# 'Object' always carries a __hash__ method, but it's not always implemented.\n",
        "\n",
        "# Use callable instead\n",
        "# print(f\"String is hashable? {callable(str.__hash__)}\")\n",
        "# print(f\"List is hashable? {callable(list.__hash__)}\")\n",
        "# print(f\"Int is hashable? {callable(int.__hash__)}\")\n",
        "# print(f\"Set is hashable? {callable(set.__hash__)}\")\n",
        "# print(f\"Tuple is hashable? {callable(tuple.__hash__)}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "M6Q98Gclfd1v",
        "colab_type": "text"
      },
      "source": [
        "## Python hash() function\n",
        "The hash() function returns the hash value of the object if it has one. Hash values are integers. \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ecyH2d38fUaG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# You can use try/except to detect unhashables. \n",
        "# Let's hash some things.\n",
        "thing = \"Some string\"\n",
        "try:\n",
        "    h = hash(thing)\n",
        "    print(f\"{thing} : hashes into {h}\")\n",
        "except TypeError:\n",
        "    print(f\"{thing} : No hash for you.\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-uKlACHV7acL",
        "colab_type": "text"
      },
      "source": [
        "## What is the hashing algorithm that Python uses?\n",
        "Actually there are several.  Python hashes objects differently, according to their types.  If you would like to review the C source code you can find it at https://github.com/python/cpython/blob/master/Python/pyhash.c"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EFnC0Y2NeqMH",
        "colab_type": "text"
      },
      "source": [
        "## Python immutable builtins are hashable.\n",
        "Hashable types are integers, strings, or tuples."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A1UKd7_TgkRI",
        "colab_type": "text"
      },
      "source": [
        "Python class objects are hashable by default. Their hash is derived from their Id.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bPprAqMOergN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class User:\n",
        "    \"\"\"A generic user\"\"\"\n",
        "    def __init__(self, name, agency):\n",
        "        self.name = name\n",
        "        self.agency = agency\n",
        "\n",
        "u1 = User('John Doe', 'cia')\n",
        "u2 = User('John Doe', 'cia')\n",
        "\n",
        "print(f'u1 hash: {hash(u1)}')\n",
        "print(f'u2 hash: {hash(u2)}')\n",
        "\n",
        "if (u1 == u2):\n",
        "    print('same user')\n",
        "else:\n",
        "    print('different users')\n",
        "\n",
        "# Can they be added to a set?\n",
        "myset = {u1, u2}\n",
        "print(f\"myset = {myset}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2ZVLk8Q8hJH0",
        "colab_type": "text"
      },
      "source": [
        "The user attributes are identical, but they are not identical objects because they occupy two separate memory locations and their IDs are different.  For the comparison to work, we need to implement the `__eq__()` method.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "az9uX0gnhMU1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class User:\n",
        "    \"\"\"A generic user, with __eq__ and __repr__\"\"\"\n",
        "    def __init__(self, name, agency):\n",
        "        self.name = name\n",
        "        self.agency = agency\n",
        "    \n",
        "    def __repr__(self):\n",
        "        \"\"\"Rendering ourself in a more readable way\"\"\"\n",
        "        return f'[{self.name}:{self.agency}]'\n",
        "    \n",
        "    def __eq__(self, other):\n",
        "        \"\"\"Equality comparison func\"\"\"\n",
        "        return self.name == other.name and self.agency == other.agency\n",
        "\n",
        "# Test it\n",
        "u1 = User('Valerie', 'CIA')\n",
        "u2 = User('Valerie', 'CIA')\n",
        "\n",
        "print(f'u1 hash: {hash(u1)}')\n",
        "print(f'u2 hash: {hash(u2)}')\n",
        "\n",
        "print(f\"{u1} and {u2} are {'same' if u1 == u2 else 'different'}\")\n",
        "\n",
        "# Can they be added to a set?\n",
        "myset = {u1, u2}\n",
        "print(f\"myset = {myset}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fHiIwpF0k6_H",
        "colab_type": "text"
      },
      "source": [
        "The attribute comparison now returns the expected result, but the objects are not hashable yet.  We need to add the final piece to the puzzle: The `__hash__` method."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MXugdRW4lH4h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class User:\n",
        "    \"\"\"A generic user, with __eq__, __repr__ and __hash__\"\"\"\n",
        "    def __init__(self, name, agency):\n",
        "        self.name = name\n",
        "        self.agency = agency\n",
        "    \n",
        "    def __repr__(self):\n",
        "        \"\"\"Make output look pretty\"\"\"\n",
        "        return f'[{self.name}:{self.agency}]'\n",
        "    \n",
        "    def __eq__(self, other):\n",
        "        \"\"\"Equality comparison func\"\"\"\n",
        "        return self.name == other.name and self.agency == other.agency\n",
        "\n",
        "    def __hash__(self):\n",
        "        \"\"\"Performs a hash on the attributes. Note the tuplization of hash input\"\"\"\n",
        "        return hash((self.name, self.agency))\n",
        "\n",
        "# Test it\n",
        "u1 = User('Valerie', 'CIA')\n",
        "u2 = User('Valerie', 'CIA')\n",
        "\n",
        "print(f'u1 hash: {hash(u1)}')\n",
        "print(f'u2 hash: {hash(u2)}')\n",
        "\n",
        "print(f\"{u1} and {u2} are {'same' if u1 == u2 else 'different'}\")\n",
        "\n",
        "# Can they be added to a set?\n",
        "myset = {u1, u2}\n",
        "print(f\"myset = {myset}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zat9hhV4oCEr",
        "colab_type": "text"
      },
      "source": [
        "## Hashing `</derail>`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qppS7rnmqFII",
        "colab_type": "text"
      },
      "source": [
        "## Part II : Creating a Node class object\n",
        "Here we'll create an associative object that binds the keys and values together, along with a hash of the key.  This represents a single key/value association in the Dictionary"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IVQ71t9-z3ws",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Node:\n",
        "    \"\"\"A class that binds a key and a value together with a hash\"\"\"\n",
        "    def __init__(self, key, value=None):\n",
        "        self.key = key\n",
        "        self.value = value\n",
        "        # Create a hash value for this node, based on the key.\n",
        "        self.hash = hash(self.key)\n",
        "\n",
        "    def __repr__(self):\n",
        "        \"\"\"How this class renders its own data when asked for a string representation\"\"\"\n",
        "        return f'{self.__class__.__name__}: k={self.key} v={self.value}'\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        \"\"\"This gets called when comparing to other Nodes, using == \"\"\"\n",
        "        return self.key == other.key\n",
        "\n",
        "# Test it\n",
        "n = Node('Mike', 21)\n",
        "print(n)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TT_BLpPS1v74",
        "colab_type": "text"
      },
      "source": [
        "## The NoDict class\n",
        "This class implements a basic dictionary data type.  It is an associative hash map.  The hash of each Node is used to determine which 'bucket' the Node will be stored into.\n",
        "\n",
        "Note that the hash value of each Node starts as a large integer.  Using modulo division, the hash value gets reduced to a range where it will map into one of the bucket indexes.\n",
        "\n",
        "This is what makes the lookups fast."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TZXA0cZc11ln",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Create a dictionary class to manage the key value pairs (Nodes)\n",
        "# The dictionary will be initialized with \"buckets\" aka \"swim lanes\" \n",
        "# We will default to 10 buckets.\n",
        "class NoDict:\n",
        "    def __init__(self, num_buckets=10):\n",
        "        self.size = num_buckets\n",
        "        self.buckets = [ [] for _ in range(self.size) ]\n",
        "\n",
        "    def __repr__(self):\n",
        "        \"\"\"How this dict renders its data when printed\"\"\"\n",
        "        # For this dict, we want to show all the buckets vertically\n",
        "        return '\\n'.join([f'{self.__class__.__name__}.{i}:{bucket}' for i, bucket in enumerate(self.buckets)])\n",
        "\n",
        "    def add(self, key, value):\n",
        "        \"\"\"Inserts a new key-value Node into the NoDict\"\"\"\n",
        "        new_kv = Node(key, value)\n",
        "        index = new_kv.hash % self.size\n",
        "        bucket = self.buckets[index]\n",
        "        # Insert new node, remove duplicates\n",
        "        for node in bucket:\n",
        "            if node == new_kv:\n",
        "                print(\"Hey I'm removing a duplicate\")\n",
        "                bucket.remove(node)\n",
        "                break\n",
        "        bucket.append(new_kv)\n",
        "\n",
        "d = NoDict()\n",
        "d.add('Daniel', 25)\n",
        "d.add('Piero', 99)\n",
        "d.add('Stew', 35)\n",
        "print(d)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rHPfNKkkgwwn",
        "colab_type": "text"
      },
      "source": [
        "### Adding the `get` method\n",
        "After adding the `get` method, we can do lookups as well as insertions!  Also adding two magic methods for `__setitem__` and `__getitem__` because dictionaries should be usable with square-bracket operators"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m-t36i5B3o3W",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Create a dictionary class to manage the key value pairs (Nodes)\n",
        "# The dictionary will be initialized with \"buckets\" aka \"swim lanes\" \n",
        "# We will default to 10 buckets.\n",
        "class NoDict:\n",
        "    def __init__(self, num_buckets=10):\n",
        "        self.size = num_buckets\n",
        "        self.buckets = [ [] for _ in range(self.size) ]\n",
        "\n",
        "    def __repr__(self):\n",
        "        \"\"\"How this dict renders its data when printed\"\"\"\n",
        "        # For this dict, we want to show all the buckets\n",
        "        return '\\n'.join([f'{self.__class__.__name__}.{i}:{bucket}' for i, bucket in enumerate(self.buckets)])\n",
        "\n",
        "    def add(self, key, value):\n",
        "        \"\"\"Inserts a new key-value Node into the NoDict\"\"\"\n",
        "        new_kv = Node(key, value)\n",
        "        index = new_kv.hash % self.size\n",
        "        bucket = self.buckets[index]\n",
        "        # Insert new node, remove duplicates\n",
        "        for node in bucket:\n",
        "            if node == new_kv:\n",
        "                print(\"Hey I'm removing a duplicate\")\n",
        "                bucket.remove(node)\n",
        "                break\n",
        "        bucket.append(new_kv)\n",
        "\n",
        "    def get(self, key):\n",
        "        \"\"\"Lookup the value of a key\"\"\"\n",
        "        to_find = Node(key)\n",
        "        bucket = self.buckets[to_find.hash % self.size]\n",
        "        for node in bucket:\n",
        "            if node == to_find:\n",
        "                return node.value\n",
        "        raise KeyError(f'{key} not found')\n",
        "\n",
        "    def __getitem__(self, key):\n",
        "        \"\"\"Makes our class responsive to [] lookup operators\"\"\"\n",
        "        return self.get(key)\n",
        "\n",
        "    def __setitem__(self, key, value):\n",
        "        \"\"\"Makes our class responsive to [] assignment operators\"\"\"\n",
        "        self.add(key, value)\n",
        "\n",
        "d = NoDict()\n",
        "# Yay now it behaves like a real dict!\n",
        "d['Daniel'] = 25\n",
        "d['Piero'] = 99\n",
        "d['Stew'] =35\n",
        "print(d)\n",
        "print(f\"Stew's age is {d['Stew']}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nD7KsnZ6iQ5s",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# This should raise a KeyError exception\n",
        "print(f\"Janell's age is {d['Janell']}\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zsE_R5ZDihxa",
        "colab_type": "text"
      },
      "source": [
        "### Conclusion\n",
        "It's nice to understand the mechanics of what is going on inside a dictionary.  Hashing is an important topic to understand as well.  \n",
        "\n",
        "Dictionaries in python are already highly optimized containers.  But under the hood, there are always tradeoffs.  By tweaking things like the number of buckets, hashing algorithm, a dictionary can be tuned to perform better in certain situations.\n",
        "\n",
        "Of course there are more methods we could add:  How would you implement a method to remove a key?  What happens if two completely different Nodes produce the same hash value aka \"hash collision\"?\n",
        "\n",
        "### Further Reading\n",
        "[What Happens when you Mess with Hashing in Python](https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pzX-tGUWmxZj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}