Hash Functions

hash_functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hash Functions\n",
    "\n",
    "A hash table is a data structure that implements an dictionary abstract data type, and is used to map keys to values.\n",
    "\n",
    "```\n",
    "                         array (key)\n",
    "                           ┌───┐\n",
    "                         0 │ ⊙─┼─► value\n",
    "                           ├───┤\n",
    "                         1 │ ⊙─┼─► value\n",
    "                           ├───┤\n",
    "                         2 │   │  A Hash table is implemented by using a large array.\n",
    "                           ├───┤  This is usually called the table's \"backing array\n",
    "                         3 │   │  because it backs the hash table.\n",
    "                           ├───┤\n",
    "To place an item A       4 │   │  \n",
    "into the backing array,    ├───┤\n",
    "calculate a hash value.  5 │   │\n",
    "                           ├───┤\n",
    "                         6 │   │\n",
    "                           ├╶╶╶│ \n",
    "               ┌──────┐    │   │\n",
    "     \"cab\" ──► │ hash    │   │\n",
    "               │ func │    │   │\n",
    "               └───┼──┘    │   │   Multiple items might have the same hash value. \n",
    "                   │       │   │   This is called a collision. There are 2 ways\n",
    "                   │       │   │   to handle collisions: chaining and linear probing.\n",
    "                   │       ├╶╶╶│\n",
    "                   │       │   │     linked-list\n",
    "                   │       ├───┤    ┌───────┬───┐  ┌─────────┬───┐\n",
    "                   └──► 98 │ ⊙─┼──►│ \"cab\" │ ⊙─┼──┼─► \"cat\" │ ⊙─┼────►\n",
    " the hash value is         ├───┤    └───────┴───┘  └─────────┴───┘\n",
    " then mod(%) with       99 │   │\n",
    " the array size.           └───┘\n",
    "\n",
    "```\n",
    "### Additional Notes:\n",
    "- Load Factor is the Number of Entries in the Hash Table divided by the size of the backing array. The higher the load factor, the greater the probability of collisions.\n",
    "- A Load factor of 0.75 is generally considered a good point to double the size of the backing array.\n",
    "- When you resize the backing array, you have to remap all the entries in the table.\n",
    "\n",
    "### Requirements:\n",
    "1. Deterministic\n",
    "2. Evenly distributed\n",
    "3. Should use all values of the input\n",
    "\n",
    "### Hash Codes:\n",
    "To generate hash codes, we use polynomials. We set ``x`` to a prime number, (e.g, 31, 53 or 101)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}