| | |
|---|
| | | |
|---|
| | | <link rel="shortcut icon" href="favicon.png" /> |
|---|
| | | <link rel="apple-touch-icon" href="apple-touch-icon.png" /> |
|---|
| | | <style> |
|---|
| | | div.linkedlist{ |
|---|
| | | width:120px;height:35px;border:1px solid #000;font-size:16px;display:inline-block;padding-left:10px;margin-left:30px; |
|---|
| | | } |
|---|
| | | div.linkedlist::before{ |
|---|
| | | content: '\1F82A'; |
|---|
| | | font-size: 16pt; |
|---|
| | | left: -1.5em; |
|---|
| | | margin-top:-5px; |
|---|
| | | position: relative; |
|---|
| | | } |
|---|
| | | |
|---|
| | | div.addrvertical{ |
|---|
| | | width:90px;height:35px;border:1px solid #000;background:grey;color:white;font-size:16px;display:inline-block |
|---|
| | | } |
|---|
| | | |
|---|
| | | </style> |
|---|
| | | </head> |
|---|
| | | |
|---|
| | | <body class="impress-not-supported"> |
|---|
| | |
|---|
| | | </div> |
|---|
| | | |
|---|
| | | <div id="impress"> |
|---|
| | | <script> |
|---|
| | | var names; |
|---|
| | | var phones; |
|---|
| | | var memory; |
|---|
| | | var insert_idx=0; |
|---|
| | | var insert_idx_without_collision=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 insertMissingIntoLL(data_index){ |
|---|
| | | if(data_index==-1) data_index=insert_idx; |
|---|
| | | hashval=hash(names[data_index]); |
|---|
| | | console.log("f"+hashval); |
|---|
| | | elll=document.getElementById("ll"+hashval); |
|---|
| | | elll.innerHTML=elll.innerHTML+"<div class='linkedlist'>"+names[data_index]+"</div>"; |
|---|
| | | |
|---|
| | | memory[hashval]=data_index; |
|---|
| | | insert_idx++; |
|---|
| | | if(insert_idx==8){ |
|---|
| | | alert("Completed!"); |
|---|
| | | } |
|---|
| | | else { |
|---|
| | | currentInner(document.getElementById("s1current"), insert_idx); |
|---|
| | | currentInner(document.getElementById("currll"), insert_idx); |
|---|
| | | } |
|---|
| | | |
|---|
| | | } |
|---|
| | | |
|---|
| | | |
|---|
| | | 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!!!"); |
|---|
| | | insert_index_without_collision=insert_idx; |
|---|
| | | } |
|---|
| | | else{ |
|---|
| | | el1=document.getElementById("f"+hashval); |
|---|
| | | el2=document.getElementById("nf"+hashval); |
|---|
| | | |
|---|
| | | el1.innerHTML=names[data_index]; |
|---|
| | | el2.innerHTML=phones[data_index]; |
|---|
| | | |
|---|
| | | elll=document.getElementById("ll"+hashval); |
|---|
| | | elll.innerHTML=elll.innerHTML+"<div class='linkedlist'>"+names[data_index]+"</div>"; |
|---|
| | | |
|---|
| | | memory[hashval]=data_index; |
|---|
| | | insert_idx++; |
|---|
| | | if(insert_idx==8){ |
|---|
| | | alert("Completed!"); |
|---|
| | | } |
|---|
| | | else { |
|---|
| | | currentInner(document.getElementById("s1current"), insert_idx); |
|---|
| | | currentInner(document.getElementById("currll"), 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"> |
|---|
| | |
|---|
| | | |
|---|
| | | --> |
|---|
| | | <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 /> |
|---|
| | | |
|---|
| | | <p>Let's try it out for our phone directory (array_size=13):</p><br /> |
|---|
| | | <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"> </div><div id="nf0" style="font-size:11pt"> </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"> </div><div id="nf1" style="font-size:11pt"> </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"> </div><div id="nf2" style="font-size:11pt"> </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"> </div><div id="nf3" style="font-size:11pt"> </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"> </div><div id="nf4" style="font-size:11pt"> </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"> </div><div id="nf5" style="font-size:11pt"> </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"> </div><div id="nf6" style="font-size:11pt"> </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"> </div><div id="nf7" style="font-size:11pt"> </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"> </div><div id="nf8" style="font-size:11pt"> </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"> </div><div id="nf9" style="font-size:11pt"> </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"> </div><div id="nf10" style="font-size:11pt"> </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"> </div><div id="nf11" style="font-size:11pt"> </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"> </div><div id="nf12" style="font-size:11pt"> </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> |
|---|
| | | <table style="width:100%"> |
|---|
| | | <col width="70%"> |
|---|
| | | <col width="30%"> |
|---|
| | | <tr> |
|---|
| | | <td> |
|---|
| | | <div id='ll0'><div class="addrvertical">data[0]</div></div> |
|---|
| | | <div id='ll1'><div class="addrvertical">data[1]</div></div> |
|---|
| | | <div id='ll2'><div class="addrvertical">data[2]</div></div> |
|---|
| | | <div id='ll3'><div class="addrvertical">data[3]</div></div> |
|---|
| | | <div id='ll4'><div class="addrvertical">data[4]</div></div> |
|---|
| | | <div id='ll5'><div class="addrvertical">data[5]</div></div> |
|---|
| | | <div id='ll6'><div class="addrvertical">data[6]</div></div> |
|---|
| | | <div id='ll7'><div class="addrvertical">data[7]</div></div> |
|---|
| | | <div id='ll8'><div class="addrvertical">data[8]</div></div> |
|---|
| | | <div id='ll9'><div class="addrvertical">data[9]</div></div> |
|---|
| | | <div id='ll10'><div class="addrvertical">data[10]</div></div> |
|---|
| | | <div id='ll11'><div class="addrvertical">data[11]</div></div> |
|---|
| | | <div id='ll12'><div class="addrvertical">data[12]</div></div> |
|---|
| | | <div id='ll13'><div class="addrvertical">data[13]</div></div> |
|---|
| | | </td> |
|---|
| | | <td> |
|---|
| | | <div id="currll"></div> |
|---|
| | | <button onclick="insertMissingIntoLL(-1);">Insert</button> |
|---|
| | | |
|---|
| | | </td> |
|---|
| | | |
|---|
| | | </tr> |
|---|
| | | </table> |
|---|
| | | |
|---|
| | | </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> |
|---|
