notebook/Unit6-4-Hash_Table.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hash Tables\n",
    "\n",
    "\n",
    "\n",
    "## 1 Building Energy  Management System \n",
    "\n",
    "### 1.1 Building Energy Management System\n",
    "\n",
    "**A building energy management system(BEMS)** is a computer-based system that monitors and controls a building’s electrical and mechanical equipment such as lighting,power systems, heating, ventilation, and air conditioning(HVAC),security measures and so on. \n",
    "\n",
    "![](./img/ds/bems.jpg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 1.2  The Simple Example: Measurement Tags of VCR\n",
    "\n",
    "The table store the Measurement Tags of VCR Example 11-2,every the Tag recored has the uniqe tagID\n",
    "\n",
    "Refrigerant-134a enters the compressor of a refrigerator as superheated vapor at 0.14 MPa and -10°C at a rate of 0.05kg/s and leaves at 0.8 MPa and 50°C.\n",
    "\n",
    "The refrigerant is cooled in the condenser to 26°C and 0.72MPa and is throttled to 0.15 MPa.\n",
    "\n",
    "Disregarding any heat transfer and pressure drops in the connecting lines between the components, \n",
    "\n",
    "**Determine：** the power input to the compressor,\n",
    "\n",
    "![](./img/vcr/vcr-11-2.jpg)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./data/vcr-11-2.csv\n",
    "TagID,Tag,Desc,Unit,Value\n",
    "600,CompressorIPortM,压缩机入口流量,kg/s,0.05\n",
    "616,CompressorOPortP,压缩机出口压力,MPa,0.8\n",
    "613,CompressorOPortT,压缩机出口温度,°C,50\n",
    "714,CondenserOPortP,冷凝器出口压力,MPa,0.72\n",
    "708,CondenserOPortT,冷凝器出口温度,°C,26.0\n",
    "814,ExpansionValveOPortP,膨胀阀出口压力,MPa,0.15\n",
    "914,EvaporatorValveOPortP,蒸发器出口压力,MPa,0.14\n",
    "908,EvaporatorValveOPortT,蒸发器出口温度,°C,-10.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Data Stucture of Tags**\n",
    "\n",
    "```python\n",
    "\n",
    "tag=(id,(tag,desc,value)) # tuple \n",
    "\n",
    "VCC1_TagTable=[]  # list\n",
    "\n",
    "VCC1_TagTable=[(id,(tag,desc,unit,value)),...]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "vcc_table=[]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID']) # convert to int\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=c=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    vcc_table.append((id,(tag,desc,unit,value)))\n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for item in  vcc_table:\n",
    "    print(item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get the tags of Compressor through tagID by the Linear Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tagid=616\n",
    "for item in vcc_table:\n",
    "    if tagid==item[0]:\n",
    "        print(tagid,item[1])       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Linear Search will perform  $𝑂(N)$  \n",
    "\n",
    "Here are the data structures, the complexities of their key lookup operations:\n",
    "\n",
    "| Data structure   |  lookup  |\n",
    "| ----------------- |:--------:|\n",
    "| Array         |  O(N)    |\n",
    "| Sorted array    |   O(logN) |\n",
    " \n",
    "If there is a data structure that can do better. And it turns out that there is: **the hash table**, one of the best and most useful data structures \n",
    "\n",
    "In Python, the type <font color=\"blue\">dict</font> dictionaries use <b>hashing</b> to do <b>the lookup in time</b> \n",
    "\n",
    "* that is nearly `independent` of the `size` of the dictionary\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic idea behind hashing is\n",
    "\n",
    "* **convert the key to an integer, and then use that integer to index into a list**\n",
    "\n",
    "which can be done in `constant` time. \n",
    "\n",
    "**Hash functions** : any function that can be used to map data of `arbitrary` size to `fixed-size` values.\n",
    "\n",
    "* `CurTagID%ListSize`(除留余数法 k mod m - 关键字k除以表长度m的余数)\n",
    "![](./img/ds/hash1.png)\n",
    "\n",
    "**Hash value** : The values returned by a hash function are called \n",
    "    \n",
    "* `Index_TagID=CurTagID%ListSize`\n",
    "\n",
    "**Hash table**: the data structure that maps keys to values with hashing\n",
    "\n",
    "* `vcc_table=[None for i in range(ListSize)]`\n",
    "\n",
    ">散列表通过把`关键码`值映射到表中`一个位置`来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表 \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example we use the remainder `key%ListSize` as the index into the list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=30;\n",
    "# the store table \n",
    "vcc_table=[None for i in range(ListSize)]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    # convert the key to an integer:  address in the list\n",
    "    address= id%ListSize\n",
    "    # put the record in the address of the list\n",
    "    vcc_table[address]=(id,(tag,desc,unit,value))\n",
    "    print(id,address)\n",
    "csvfile.close() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for  i,item in  enumerate(vcc_table):\n",
    "    print(i,item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Search one tag from TagID with the `unique` tagid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tagid=616\n",
    "address=tagid%ListSize\n",
    "print(tagid,vcc_table[address])   \n",
    "print(tagid,vcc_table[address][1])   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is done in **constant** time that is `independent` of the `size` of VCC1_TagList\n",
    "\n",
    "* The search time complexity is $O(1)$\n",
    "\n",
    "每个关键字对应一个列表中的一个存储位置，就可以**直接寻址**，查询的时间复杂度是O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Collision \n",
    "\n",
    "### 2.1 Collision \n",
    "\n",
    "If the space of possible `outputs` is **smaller** than the space of possible `inputs`, \n",
    "\n",
    "* a hash function is a `many`-to-`one` mapping. \n",
    "\n",
    "the different keys are mapped to the same hash value,it is called a <b>collision</b>. \n",
    "\n",
    ">散列冲突：在散列表中，不同的关键字值对应到同一个存储位置的现象\n",
    "\n",
    "\n",
    "**For exmple**\n",
    "\n",
    "* the input sizes of key is :9\n",
    "\n",
    "* the output sizes of hash value:ListSize is 5\n",
    "\n",
    "The hash function : `id%ListSize`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=5;\n",
    "# the store table \n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    # convert the key to an integer: address of the list\n",
    "    address= id%ListSize\n",
    "    print(id,address)\n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Many Collision!**\n",
    "```\n",
    "613 3\n",
    "708 3\n",
    "808 3\n",
    "908 3\n",
    "```\n",
    "```\n",
    "714 4\n",
    "814 4\n",
    "914 4\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**If Collision**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=5;\n",
    "# the store table \n",
    "vcc_table=[None for i in range(ListSize)]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    # convert the key to an integer:address of the list\n",
    "    address= id%ListSize\n",
    "    # put the record in the index of the list\n",
    "    vcc_table[address]=(id,(tag,desc,unit,value))\n",
    "csvfile.close() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CompressorTagIDList=[600,616,613,914,908]\n",
    "for tagid in CompressorTagIDList:\n",
    "    address=tagid%ListSize\n",
    "    print(vcc_table[address]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "you will see \n",
    "```\n",
    "(908, ('EvaporatorValveOPortT', '蒸发器出口温度', '°C', -10.0))\n",
    "(908, ('EvaporatorValveOPortT', '蒸发器出口温度', '°C', -10.0))\n",
    "```\n",
    "because the Collision \n",
    "```\n",
    "613 3\n",
    "908 3\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the space of possible outputs is bigger than the space of possible inputs\n",
    "\n",
    "* **no collisions**?\n",
    "\n",
    "For example: `ListSize=20`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "\n",
    "# set the size of the store list\n",
    "ListSize=20;\n",
    "# the store table \n",
    "vcc_table=[None for i in range(ListSize)]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    # convert the key to an integer: address of the list\n",
    "    address= id%ListSize\n",
    "    # put the record in the index of the list\n",
    "    vcc_table[address]=(id,(tag,desc,unit,value))\n",
    "    print(id, address)\n",
    "csvfile.close() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**collisions**\n",
    "\n",
    "```\n",
    "714 14\n",
    "814 14\n",
    "914 14\n",
    "\n",
    "708 8\n",
    "908 8\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Handle the collision \n",
    "\n",
    "The paths to handle the collision in Hash Table\n",
    "\n",
    "1. **minimizes collisions**: \n",
    "\n",
    "   * the `good` hash function： produces : **uniform distribution** every output in the range is equally probable, which `minimizes` the probability of `collisions`(散列函数设计要点:均匀性好,减少元素冲突次数)\n",
    "    \n",
    "  *  the `sweet spot` size of hash table\n",
    "\n",
    "\n",
    "2. **collision resolution**: Separate Chainingg(分离链接法), Open Addressing(开放地址法） \n",
    "\n",
    "\n",
    "### 2.3 Choice of hash table size\n",
    "\n",
    "Assuming you have a good hash function, by making the hash table large enough,\n",
    "\n",
    "Let’s think about the extremes:\n",
    "\n",
    "* You create a hash table with 1,000,000 buckets and you add 1,000 items to it. The chances of a collision are extremely low, and this will perform amazingly.\n",
    "\n",
    "we can **reduce** the number of collisions sufficiently to allow us to treat the complexity as O(1).\n",
    "\n",
    "* 一个足够大的数组，**可以**为每个关键字保留一个位置，就可以**直接寻址**，时间复杂度是O(1)。\n",
    "\n",
    "It will **waste a lot of space**. Therefore, you need to find the `“sweet spot”` for the size of the hash table vs. the number of items you plan to put into it. \n",
    "\n",
    "Choice of hash table size depends in part on choice of hash function, and collision resolution strategy\n",
    "\n",
    "But a good general **rule of thumb** is:\n",
    "\n",
    "* The hash table should be an array with length about **1.3** times the maximum number of keys that will actually be in the table, and\n",
    "Size of hash table array should be a **prime** number\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Separate Chaining\n",
    "\n",
    "### 3.1 Separate Chaining(分离链接法)\n",
    "There are different ways through which a collision can be resolved. We will look at a method called **Separate Chaining(分离链接法)**, \n",
    "\n",
    "**Chain hashing** avoids collision. The idea is to make each cell of hash table point to a linked list of records(`bucket`) that have same hash function value.\n",
    "\n",
    "* 将散列到同一个值的所有元素保留到一个`链表`中\n",
    "\n",
    "**bucket(桶)**:  a linked list of records with same hash function value\n",
    "\n",
    "The hash table is a list of `hash buckets`. \n",
    "\n",
    "For Example:\n",
    "```\n",
    "keys :   [36,18,72,43,6,10,5,15]\n",
    "tab size : 8\n",
    "hash function : key % tab size\n",
    "```\n",
    "![](./img/ds/hashtable_separatechaining.gif)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 3.2 Hash Table in Python\n",
    "\n",
    "The basic idea is to represent the hash table by a list where **each item** is a list of **key/value** pairs that have the `same` hash index\n",
    "\n",
    "```python\n",
    "[\n",
    "\n",
    "    [bucket of the same hash value1],\n",
    "\n",
    "    [bucket of the same hash value2]\n",
    ",...\n",
    "]\n",
    "```\n",
    "\n",
    "the every key/value pair in bucket is the tuple:\n",
    "```python\n",
    "(key, value)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "keyvalues = [(36, \"赵\"), (18, \"钱\"), (72, \"孙\"), (43, \"李\"), (6, \"周\"), (10, \"吴\"), (5, \"郑\"), (15, \"王\")]\n",
    "num_buckets=8\n",
    "\n",
    "buckets=[[] for i in range(num_buckets)]\n",
    "\n",
    "print(\"Key\",\"The address in buckets\",\"\\n\"+20*\"-\")\n",
    "for item in keyvalues:\n",
    "    #hash function: key % num_buckets\n",
    "    address= item[0] % num_buckets\n",
    "    buckets[address].append(item)\n",
    "    print(item[0],address)\n",
    "\n",
    "print(\"\\nNo.\",\"Bucket\",\"\\n\"+20*\"-\")   \n",
    "for  i,bucket in  enumerate(buckets):\n",
    "    print(i,bucket)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "key=10\n",
    "hashvalue=key % num_buckets\n",
    "for item in buckets[hashvalue]:\n",
    "    if item[0]==key:\n",
    "        print(key,item[1])  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 The Class of Separate Chaining\n",
    "\n",
    "* **key** is integer or string\n",
    "\n",
    "* **hash function**: Key % numBuckets and djb2 \n",
    "\n",
    "> Hash function for string\n",
    ">\n",
    ">* http://www.cse.yorku.ca/~oz/hash.html\n",
    ">\n",
    ">**djb2**\n",
    ">\n",
    ">This algorithm (k=33) was first reported by `Dan Bernstein` many years ago in comp.lang.c.\n",
    ">\n",
    ">The magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.\n",
    ">```python\n",
    "> hash = 5381\n",
    "> for c in dictKey:\n",
    ">     hash = ((hash *33) + hash) + ord(c)\n",
    "> hash % numBuckets\n",
    ">```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class hashTable:\n",
    "    \"\"\"A dictionary with integer and string keys\"\"\"\n",
    "    \n",
    "    def __init__(self, numBuckets):\n",
    "        \"\"\"Create an empty dictionary\n",
    "           buckets is initialized to a list of numBuckets empty lists.\n",
    "        \"\"\"\n",
    "        self.numBuckets=numBuckets\n",
    "        self.buckets=[[] for i in range(self.numBuckets)] \n",
    "            \n",
    "    def getHashValue(self, dictKey):\n",
    "        if isinstance(dictKey, int):\n",
    "            return dictKey % self.numBuckets\n",
    "        if isinstance(dictKey,str):\n",
    "            # djb2 hash algorithm by Dan Bernstein\n",
    "            hash = 5381\n",
    "            for c in dictKey:\n",
    "                hash = ((hash *33) + hash) + ord(c)\n",
    "            return hash % self.numBuckets\n",
    "\n",
    "    \n",
    "    def addEntry(self, dictKey, dictVal):\n",
    "        \"\"\"Assumes dictKey an int.  Adds an entry.\"\"\"\n",
    "        address=self.getHashValue(dictKey)\n",
    "        hashBucket = self.buckets[address]\n",
    "        for i in range(len(hashBucket)):\n",
    "            if hashBucket[i][0] == dictKey:\n",
    "                hashBucket[i] = (dictKey, dictVal) #if one was found,replace\n",
    "                return\n",
    "        hashBucket.append((dictKey, dictVal)) # append a new entry (dictKey, dictVal) to the bucket if none was found.\n",
    "        \n",
    "    def getValue(self, dictKey):\n",
    "        \"\"\"Returns entry associated with the key dictKey\"\"\"\n",
    "        hashBucket = self.buckets[self.getHashValue(dictKey)]\n",
    "        for e in hashBucket:\n",
    "            if e[0] == dictKey: # key\n",
    "                return e[1]     # the tuple of value \n",
    "        return None\n",
    "    \n",
    "    def __str__(self):\n",
    "        result = '{'\n",
    "        for b in self.buckets:\n",
    "            for e in b:\n",
    "                result = result + str(e[0]) + ':' + str(e[1]) + ','\n",
    "        return result[:-1] + '}' #result[:-1] omits the last comma"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 4.1  Init the hash table\n",
    "\n",
    "```python\n",
    "def __init__(self, numBuckets):\n",
    "   \"\"\"\n",
    "   The instance variable buckets is initialized to a list of numBuckets empty lists\n",
    "   \"\"\"\n",
    "        self.numBuckets = numBuckets\n",
    "        self.buckets=[[] for i in range(self.numBuckets)] \n",
    "```\n",
    "\n",
    "### 4.2  hash function\n",
    "\n",
    "```python\n",
    "def getHashValue(self, dictKey):\n",
    "        if isinstance(dictKey, int):\n",
    "            return dictKey % self.numBuckets\n",
    "        if isinstance(dictKey,str):\n",
    "            # djb2 hash algorithm by Dan Bernstein\n",
    "            hash = 5381\n",
    "            for c in dictKey:\n",
    "                hash = ((hash *33) + hash) + ord(c)\n",
    "            return hash % self.numBuckets\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 4.3 addEntry\n",
    "\n",
    "By making each bucket a list, we handle collisions by storing all of the values that hash to the same bucket in the list</b>. \n",
    "\n",
    "```python\n",
    "def addEntry(self, dictKey, dictVal):\n",
    "    \"\"\"\n",
    "     To store or look up an entry with key **dictKey\n",
    "    \"\"\" \n",
    "    hashBucket = self.buckets[self.getHashValue(dictKey)] # hashing the location `hashBucket` list in  the list of self.buckets \n",
    "    for i in range(len(hashBucket)):\n",
    "        if hashBucket[i][0] == dictKey:# the item in each bucket is tuple: (dictKey, dictVal)\n",
    "            hashBucket[i] = (dictKey, dictVal) #if one was found,replace\n",
    "            return\n",
    "         hashBucket.append((dictKey, dictVal)) # append a new entry (dictKey, dictVal) to the bucket if none was found.\n",
    "```      \n",
    "   \n",
    "we use the hash function  to convert dictKey into an integer, \n",
    "```python  \n",
    " hashBucket = self.buckets[self.getHashValue(dictKey)] # hashing the location `hashBucket` list in  the list of self.buckets \n",
    "```    \n",
    "and use that integer to index into buckets \n",
    "```python\n",
    "   hashBucket[i]\n",
    "```\n",
    "to find the hash bucket associated with **dictKey**: if <b>a value is to be stored</b>,then  \n",
    "\n",
    "* if one was found:  <b>replace</b> the value in the existing entry,  \n",
    "\n",
    "* if none was found: <b>append</b> a new entry to the bucket\n",
    "\n",
    "\n",
    "### 4.4 getValue\n",
    "\n",
    "```python \n",
    "\n",
    "def getValue(self, dictKey)\n",
    "```\n",
    "We then search that bucket (which is a list) linearly to see if there is an entry with the key dictKey.\n",
    "\n",
    "```python \n",
    " for e in hashBucket:\n",
    "            if e[0] == dictKey: // key\n",
    "                return e[1]     // value\n",
    "```\n",
    "\n",
    "If we are doing <b>a lookup</b> and there is an entry with the key, we simply return the value stored with that key. \n",
    "\n",
    "If there is no entry with that key, we return None. \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.5 Measurement Tags of VCC\n",
    "\n",
    "#### 4.5.1 Integer keys\n",
    "The hash table for Measurement Tags of VCC\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "Entrys=[]\n",
    "for line in csvdata:\n",
    "    id = int(line['TagID'])\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    Entrys.append((id,(tag,desc,unit,value))) \n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**hash table smaller sise ,collisions**\n",
    "\n",
    "* numBucket=5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numBuckets=5\n",
    "# numBuckets 5 <entries \n",
    "D = hashTable(numBuckets)\n",
    "for item in Entrys:\n",
    "    D.addEntry(item[0],item[1])\n",
    "\n",
    "print('The hashTable(integer key) is:')\n",
    "print(D)\n",
    "\n",
    "print('\\n', 'The hase buckets are:')\n",
    "for i,hashBucket in enumerate(D.buckets):\n",
    "    print('BucketID',i,'  ', hashBucket)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**one, two, or three tuples** depending upon <b>the number of collisions</b> that occurred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CompressorTagIDList=[600,616,613,914,908]\n",
    "for tagid in CompressorTagIDList:\n",
    "    thebucket=D.getValue(tagid)   \n",
    "    print(tagid,thebucket)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tagid=808\n",
    "thebucket=D.getValue(tagid)  \n",
    "print(tagid,thebucket)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.5.2 String keys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import  csv\n",
    "filename=\"./data/vcr-11-2.csv\"\n",
    "csvfile = open(filename, 'r',encoding=\"utf-8\")\n",
    "csvdata = csv.DictReader(csvfile)\n",
    "Entrys=[]\n",
    "for line in csvdata:\n",
    "    tag=line['Tag']\n",
    "    desc=line['Desc']\n",
    "    unit=line['Unit']\n",
    "    value=float(line['Value'])\n",
    "    Entrys.append((tag,(desc,unit,value))) \n",
    "csvfile.close()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numBuckets=5\n",
    "# numBuckets 5 <entries 10\n",
    "D = hashTable(numBuckets)\n",
    "for item in Entrys:\n",
    "    D.addEntry(item[0],item[1])\n",
    "\n",
    "print('The hashTable(String key) is:')\n",
    "print(D)\n",
    "\n",
    "print('\\n', 'The hase buckets are:')\n",
    "for i,hashBucket in enumerate(D.buckets):\n",
    "    print('\\tBucketID',i,'  ', hashBucket)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tagid='CompressorOPortP'\n",
    "thebucket=D.getValue(tagid)  \n",
    "print(tagid,thebucket)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Further Reading\n",
    "\n",
    "* 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版），人民邮电出版社（第2版）,2015年2月  \n",
    "\n",
    "* Mark Allen Weiss. Data Structures and Algorithm Analysis in C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "2db524e06e9f5f4ffedc911c917cb75e12dbc923643829bf417064a77eb14d37"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}