Talk finished and debugged

Samo Penic

2019-10-23 21577824dbea88b590dd8b61b5a72c18f9697708

Talk finished and debugged

 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>



 images/hashtag.png