Added hash demo

Samo Penic

2019-10-23 2bee68f6a75616eea5a26dbf398ca895958fe78e

Added hash demo

 docker.html

@@ -24,6 +24,98 @@
</div>

<div id="impress">
<script>
var names;
var phones;
var memory;
var insert_idx=0;
function hash(stringval){
    hashval= 0;
    strlen=stringval.length;
    i=0;
    for(i=0;i<strlen;i++){
        hashval=hashval+stringval.charCodeAt(0);
    }
    console.log(stringval + " == " + hashval %13);
    return hashval % 13;
}

function currentInner(element,data_index){
    element.innerHTML="Inserting <b>"+names[data_index]+ "</b>. Calculated hash_function is: <b>" + hash(names[data_index])+"</b>";
}



function insertIntoMemory(data_index){
    if(data_index==-1) data_index=insert_idx;
    hashval=hash(names[data_index]);
    console.log("f"+hashval);
    if(memory[hashval]!=-1){
        alert("Collision!!!");
    }
    else{
        el1=document.getElementById("f"+hashval);
        el2=document.getElementById("nf"+hashval);

        el1.innerHTML=names[data_index];
        el2.innerHTML=phones[data_index];
		
        memory[hashval]=data_index;
        insert_idx++;
        if(insert_idx==12){
            alert("Completed!");
        }
        else {
            currentInner(document.getElementById("s1current"), insert_idx);
        }
    }
}


function loadNames(){
    names=[
        document.getElementById("name1").value,
        document.getElementById("name2").value,
        document.getElementById("name3").value,
        document.getElementById("name4").value,
        document.getElementById("name5").value,
        document.getElementById("name6").value,
        document.getElementById("name7").value,
        document.getElementById("name8").value
    ];
    phones=[1,2,3,4,5,6,7,8]
    for(i=0;i<8;i++){
        phones[i]="(01)"+Math.floor((Math.random() * 1000) + 1)+"-"+Math.floor((Math.random() * 1000) + 1);
    }
    memory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];


/* Slide 1 actions */
//Names goes into storages s0-s4 on first slide...
document.getElementById("s0").innerHTML=names[0];
document.getElementById("s1").innerHTML=names[1];
document.getElementById("s2").innerHTML=names[2];
document.getElementById("s3").innerHTML=names[3];
document.getElementById("n0").innerHTML=phones[0];
document.getElementById("n1").innerHTML=phones[1];
document.getElementById("n2").innerHTML=phones[2];
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("s0result").innerHTML=document.getElementById("n0").innerHTML;
/* End Slide 1 */

/*Filling the values into array demo until collision occurs */

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

}


</script>

 
    <div id="naslovnica" class="step slide" data-x="-1000" data-y="-1500">
@@ -51,31 +143,146 @@
        
    -->
    <div class="step slide vsebina" data-x="-250" data-y="-1250" data-z="1500">
    <h1 class="naslov">O meni...</h1>
    <h1 class="naslov">About me...</h1>
    <img class="samo" src="images/Samo1.png">
    
    <ul>
    <li> Elektronik in "ljubiteljski" odprtokodnik</li>
    <li> Asistent na Fakulteti za elektrotehniko vodim vaje iz predmetov OET</li>
    <li> Od leta 2016 sodelujem pri izvajanju obštudijske dejavnosti <b>Praktični primeri uporabe odprte kode</b></li>
    <li> Programer entuzijast </li>
    <li> phD in Electrical engineering</li>
    <li> working at the Faculty of electrical engineering, teaching fundamentals of EM fields</li>
    <li> promoting open source since... ever?</li>
    <li> hobby programmer </li>
    </ul>
    
    </div>

    <div class="step slide vsebina" data-x="0" data-y="-1500" data-z="0">
        <h1 class="naslov">Kaj so kontejnerji?</h1>
<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>

    <p class="">Kontejner (vsebnik, zabojnik) je oblika enkapsulacije aplikacij</p>
<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>
    <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>
</div>



    <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>
    
<!--    <img src="images/container-app.jpg" style="width:800px;">     -->
		
    <p>Zapiranje applikacij v kontejnerje je nekje med popolno virtualizacijo in zagonom aplikacije v gostiteljevem okolju.</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"></span>(01)123-1234</p><br />

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

    </div>

 <!--   <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="2000" data-y="-1500" data-z="0">
        <h1 class="naslov">Mapping key to index</h1>

        <p>... is performed by so called hash functions. It can be as simple as <b>sum(ascii_code[i]) % array_size</b></p><br /><br />

        <p>Let's try it out for our phone directory (array_size=13):</p>
        <div id="s1current"></div><br />
        <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>

    </div>


    <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>We can cope with collisions in multitude of ways:</p>
    <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)
    </ul>
    </div>


    <div class="step slide vsebina" data-x="2000" data-y="-2500" data-z="0">
    <h1 class="naslov">Closed addressing</h1>
	
    </div>


    <div class="step slide vsebina" data-x="2000" data-y="-3500" data-z="0">
    <h1 class="naslov">Open addressing</h1>
	
    </div>



    <div class="step slide vsebina" data-x="3000" data-y="-1500" data-z="0">
    <h1 class="naslov">Hash function properties</h1>
    <ul>
    <li>Hash function should minimize collisions
    <li>Uniformly distribute hash values
    <li>Are 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>
    </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>
    </div>


    <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
    </div>



</div>

<div id="impress-toolbar"></div>