Talk finished and debugged

Samo Penic

2019-10-23 21577824dbea88b590dd8b61b5a72c18f9697708

 hashtables.html

@@ -74,7 +74,8 @@
         
   memory[hashval]=data_index;
   insert_idx++;
   if(insert_idx==8){
   if(insert_idx==13){
      document.getElementById("currll").innerHTML="DONE!";
      alert("Completed!");
   }
   else {
@@ -89,11 +90,11 @@
   if(data_index==-1) data_index=insert_idx;
   hashval=hash(names[data_index]);
   console.log("f"+hashval);
   oldhashval=hashval;
   while(backupmemory[hashval]!=-1) hashval=(hashval+1)%13;
   backupmemory[hashval]=data_index;
   insert_idx++;
   insert_index_without_collision++;
   //else {
      console.log(names[data_index] + "==> REMAPPED ==>" + hashval); 

      el1=document.getElementById("o"+hashval);
@@ -101,9 +102,13 @@

      el1.innerHTML=names[data_index];
      el2.innerHTML=phones[data_index];
   if(insert_idx==8){
      alert("Completed!");
      if(oldhashval!=hashval){
         el1.style.color="red";	
         el2.style.color="red";	
      }
   if(insert_idx==13){
      document.getElementById("open1current").innerHTML="DONE!";
      alert("Completed!");
   } else{
      currentInner(document.getElementById("open1current"), insert_idx);
   }
@@ -138,7 +143,7 @@
      memory[hashval]=data_index;
      backupmemory[hashval]=data_index;
      insert_idx++;
      if(insert_idx==8){
      if(insert_idx==13){
         alert("Completed!");
      }
      else {
@@ -159,10 +164,15 @@
      document.getElementById("name5").value,
      document.getElementById("name6").value,
      document.getElementById("name7").value,
      document.getElementById("name8").value
      document.getElementById("name8").value,
      document.getElementById("name9").value,
      document.getElementById("name10").value,
      document.getElementById("name11").value,
      document.getElementById("name12").value,
      document.getElementById("name13").value
   ];
   phones=[1,2,3,4,5,6,7,8]
   for(i=0;i<8;i++){
   phones=[1,2,3,4,5,6,7,8,9,10,11,12,13]
   for(i=0;i<13;i++){
      phones[i]="(01)"+Math.floor((Math.random() * 9000) + 1000)+"-"+Math.floor((Math.random() * 900) + 100);
   }
   memory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];
@@ -181,7 +191,6 @@
document.getElementById("n3").innerHTML=phones[3];
//
document.getElementById("intro0").innerHTML=names[0];
document.getElementById("intro1").innerHTML=names[0];
document.getElementById("s0result").innerHTML=document.getElementById("s0").innerHTML;
document.getElementById("s3value").innerHTML=document.getElementById("s3").innerHTML;
document.getElementById("s0number").innerHTML=document.getElementById("n0").innerHTML;
@@ -190,7 +199,6 @@
/*Filling the values into array demo until collision occurs */

currentInner(document.getElementById("s1current"), 0);
/*end demo until collision*/

}

@@ -199,12 +207,13 @@

 
    <div id="naslovnica" class="step slide" data-x="-1000" data-y="-1500">
   <h1>Hardware Meetup - Sputnik, 24. october 2019</h1>
   <h1>Hardware Meetup - Sputnik, 24. October 2019</h1>
        <q>Hash tables</q><br />

   <p class="center"> ... the background of their implementations.</p><br />
   <p class="center"> ... the basic background of their implementations.</p><br />

   <p class="footnote">Samo Penič</p>
   <img src="images/hashtag.png" style="width:500px" />
    </div>

    <!--
@@ -235,28 +244,13 @@
   
    </div>

<div class="step slide vsebina" data-x="-250" data-y="-500" data-z="750" data-rotate-x="90">
   <h1 class="naslov">Let's fill in the data...</h1>
   <form>
   <ol>
   </li> Name: <input id="name1"></input><br />
   </li> Name: <input id="name2"></input><br />
   </li> Name: <input id="name3"></input><br />
   </li> Name: <input id="name4"></input><br />
   </li> Name: <input id="name5"></input><br />
   </li> Name: <input id="name6"></input><br />
   </li> Name: <input id="name7"></input><br />
   </li> Name: <input id="name8"></input><br />
   </ol><br /><br />
   <button onClick="loadNames()">Save data</button>
   </form>
</div>

<div class="step slide vsebina" data-x="0" data-y="-1500" data-z="0">
        <h1 class="naslov">What is a hash table</h1>
   <p>Sometimes also called associative array or dictionary. <b>It is a data structure used to map key into values</b></p>
   <br /><br />
   <p class="center" style="font-size:18pt">data["<span id='intro0'>Yoda</span>"] gives us all the information stored for <span id="intro1">Yoda</span>.</p>
   <p class="center">phone_number["<span id='intro0'>Yoda</span>"]</p><br />
   <p  class="center" style="font-size:18pt">  stores and returns us the information stored for varible, object, ...</p>
   <br /><br />
   <p style="font-size:18pt">It is widely used to build things such us dictionaries, telephone books, book indexes, ...</p><br />
   <p>Hash table provide <b>Insertion, Deletion and Retreival</b> in <b>constant time</b>!</p>
@@ -267,13 +261,13 @@
    <div class="step slide vsebina" data-x="1000" data-y="-1500" data-z="0">
        <h1 class="naslov">However...</h1>

   <p class="" style="margin-bottom:30px">The memory is accessible by addressing the data numerically.</p>
   <p class="" style="margin-bottom:30px">The computer memory is accessible by addressing the data numerically.</p>
   
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[0]</div><div id="s0">Yoda</div><div id="n0" style="font-size:15pt">(01)123-1234</div></span>
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[1]</div><div id="s1">Obi</div><div id="n1" style="font-size:15pt">(01)222-2222</div></span>
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[2]</div><div id="s2">Luke</div><div id="n2" style="font-size:15pt">(01)123-1234</div></span>
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[3]</div><div id="s3">Darth</div><div id="n3" style="font-size:15pt">(01)111-1111</div></span>
   <p style="margin-top:30px;font-size:15pt">e.g.: Accessing the item at memory location data[0] yields name of the person <b><span id="s0result">Yoda</span></b> and person's phone number: <span id="s0number">(01)123-1234</span></p><br />
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[0]</div><div id="s0">Yoda</div><div id="n0" style="font-size:15pt">(01)321-4321</div></span>
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[1]</div><div id="s1">Obi</div><div id="n1" style="font-size:15pt">(01)222-2222</div></span>
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[2]</div><div id="s2">Luke</div><div id="n2" style="font-size:15pt">(01)123-1234</div></span>
      <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[3]</div><div id="s3">Darth</div><div id="n3" style="font-size:15pt">(01)111-1111</div></span>
   <p style="margin-top:30px;font-size:15pt">e.g.: Accessing the item at memory location phone[0] yields name <b><span id="s0result">Yoda</span></b> and his phone number: <span id="s0number">(01)321-4321 (order reversed it is)</span></p><br />

   <p>Finding phone number of <span id="s3value">Darth</span> requires linear search through the array, which is not efficient.</p>

@@ -282,6 +276,38 @@
 <!--   <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
    </div>
-->

<div class="step slide vsebina" data-x="1000" data-y="-500" data-z="750" data-rotate-x="90">
   <h1 class="naslov">Builing a phonebook...</h1>
   <form>
   <table style="width:100%;">
<col width="70%">
  <col width="30%">
   <tr>
   <td>
   <ol style="font-size:16pt;">
   </li> Name: <input id="name1"></input><br />
   </li> Name: <input id="name2"></input><br />
   </li> Name: <input id="name3"></input><br />
   </li> Name: <input id="name4"></input><br />
   </li> Name: <input id="name5"></input><br />
   </li> Name: <input id="name6"></input><br />
   </li> Name: <input id="name7"></input><br />
   </li> Name: <input id="name8"></input><br />
   </li> Name: <input id="name9"></input><br />
   </li> Name: <input id="name10"></input><br />
   </li> Name: <input id="name11"></input><br />
   </li> Name: <input id="name12"></input><br />
   </li> Name: <input id="name13"></input><br />
   </ol>
   </td>
   <td>
   <button onClick="loadNames()">Save data</button><br />
   </td>
   </tr>
   </table>
   </form>
</div>


   <div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="0">
@@ -294,19 +320,19 @@
      <button onclick="insertIntoMemory(-1);">Insert</button>
      <br /><br />

      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[0]</div><div id="f0" style="font-size:18px">&nbsp;</div><div id="nf0" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[1]</div><div id="f1" style="font-size:18px">&nbsp;</div><div id="nf1" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[2]</div><div id="f2" style="font-size:18px">&nbsp;</div><div id="nf2" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[3]</div><div id="f3" style="font-size:18px">&nbsp;</div><div id="nf3" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[4]</div><div id="f4" style="font-size:18px">&nbsp;</div><div id="nf4" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[5]</div><div id="f5" style="font-size:18px">&nbsp;</div><div id="nf5" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[6]</div><div id="f6" style="font-size:18px">&nbsp;</div><div id="nf6" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[7]</div><div id="f7" style="font-size:18px">&nbsp;</div><div id="nf7" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[8]</div><div id="f8" style="font-size:18px">&nbsp;</div><div id="nf8" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[9]</div><div id="f9" style="font-size:18px">&nbsp;</div><div id="nf9" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[10]</div><div id="f10" style="font-size:18px">&nbsp;</div><div id="nf10" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[11]</div><div id="f11" style="font-size:18px">&nbsp;</div><div id="nf11" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[12]</div><div id="f12" style="font-size:18px">&nbsp;</div><div id="nf12" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[0]</div><div id="f0" style="font-size:18px">&nbsp;</div><div id="nf0" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[1]</div><div id="f1" style="font-size:18px">&nbsp;</div><div id="nf1" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[2]</div><div id="f2" style="font-size:18px">&nbsp;</div><div id="nf2" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[3]</div><div id="f3" style="font-size:18px">&nbsp;</div><div id="nf3" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[4]</div><div id="f4" style="font-size:18px">&nbsp;</div><div id="nf4" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[5]</div><div id="f5" style="font-size:18px">&nbsp;</div><div id="nf5" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[6]</div><div id="f6" style="font-size:18px">&nbsp;</div><div id="nf6" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[7]</div><div id="f7" style="font-size:18px">&nbsp;</div><div id="nf7" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[8]</div><div id="f8" style="font-size:18px">&nbsp;</div><div id="nf8" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[9]</div><div id="f9" style="font-size:18px">&nbsp;</div><div id="nf9" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[10]</div><div id="f10" style="font-size:18px">&nbsp;</div><div id="nf10" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[11]</div><div id="f11" style="font-size:18px">&nbsp;</div><div id="nf11" style="font-size:11pt">&nbsp;</div></span>
      <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[12]</div><div id="f12" style="font-size:18px">&nbsp;</div><div id="nf12" style="font-size:11pt">&nbsp;</div></span>

   </div>

@@ -314,14 +340,14 @@
   <div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="-1500">
   <h1 class="naslov">Collisions!</h1>
   
   <p>They will occur. The probability depends on Load factor (LF=number_of_items/array_size)</p>
   <p>They will occur. The probability depends on Load factor (LF=number_of_items/array_size)</p><br />
   
   <p>We can cope with collisions in multitude of ways:</p>
   <p>We can cope with collisions in different of ways:</p><br />
   <ul>
   <li>Closed addressing (chaining)
   <li>Open addressing (linear probing) (million ways how to do it)
   <li>using alternate hash functions (million ways how to do it)
   <li>Resize array ;) (not a scientific way to do it)
   <li>Open addressing (linear probing)
   <li>using alternate hash functions
   <li>Resize the array ;)
   </ul>
   </div>

@@ -385,21 +411,45 @@


   <div class="step slide vsebina" data-x="3000" data-y="-1500" data-z="0">
   <h1 class="naslov">Hash function properties</h1>
   <h1 class="naslov">Hash function has to...</h1>
   <ul>
   <li>Hash function should minimize collisions
   <li>Uniformly distribute hash values
   <li>Are easy to calculate
   <li>minimize collisions
   <li>uniformly distribute hash values
   <li>be easy to calculate
   </ul>
   </div>

   <div class="step slide vsebina" data-x="4000" data-y="-1500" data-z="0" data-rotate="90">
   <h1 class="naslov">Python dictionaries</h1>
   <p>Python relys heavily on dictionaries, so it is important they are efficient. Uses open addressing multihash to minimize collisions.</p>
   <pre style="font-size:15pt;margin-top:-10px">
<code>
table = [None] * n;
for hash, key, value in entries:
    perturb = hash
    i = hash % n
    while table[i] is not None:
        #collision
        i = (5 * i * perturb + 1) % n
        perturb >>= 5
    table[i] = (key, value)
</code></pre>

   <p>See talk: Raymond Hettinger -- Modern dictionaries (SF Python 2006)</p>
   </div>


   <div class="step slide vsebina" data-x="4000" data-y="-2500" data-z="0" data-rotate="90">
   <h1 class="naslov">Hash tables in firmware</h1>
   <ul>
   <li>Hash tables have average time complexity around O(1) for I,L,D
   <li>Do not resize tables - plan in advance
   <li>Use the power of prime numbers
   <li>Storing pointers of data in hash is not a bad idea (!)
      <ul style="margin-left:50px">
      <li>to save memory, when data is large
      <li>to get ordered dict if needed
      </ul>
   </div>