| | |
|---|
| | | var names; |
|---|
| | | var phones; |
|---|
| | | var memory; |
|---|
| | | var backupmemory; |
|---|
| | | var insert_idx=0; |
|---|
| | | var insert_idx_without_collision=0; |
|---|
| | | function hash(stringval){ |
|---|
| | |
|---|
| | | |
|---|
| | | memory[hashval]=data_index; |
|---|
| | | insert_idx++; |
|---|
| | | if(insert_idx==8){ |
|---|
| | | if(insert_idx==13){ |
|---|
| | | document.getElementById("currll").innerHTML="DONE!"; |
|---|
| | | alert("Completed!"); |
|---|
| | | } |
|---|
| | | else { |
|---|
| | |
|---|
| | | |
|---|
| | | function insertMissingIntoOpen(data_index){ |
|---|
| | | insert_idx=insert_index_without_collision; |
|---|
| | | if(data_index==-1) data_index=insert_index_without_collision; |
|---|
| | | if(data_index==-1) data_index=insert_idx; |
|---|
| | | hashval=hash(names[data_index]); |
|---|
| | | console.log("f"+hashval); |
|---|
| | | while(memory[hashval]!=-1) hashval=(hashval+1)%13; |
|---|
| | | memory[hashval]=data_index; |
|---|
| | | oldhashval=hashval; |
|---|
| | | while(backupmemory[hashval]!=-1) hashval=(hashval+1)%13; |
|---|
| | | backupmemory[hashval]=data_index; |
|---|
| | | insert_idx++; |
|---|
| | | if(insert_idx==8){ |
|---|
| | | alert("Completed!"); |
|---|
| | | } |
|---|
| | | else { |
|---|
| | | currentInner(document.getElementById("open1current"), insert_idx); |
|---|
| | | insert_index_without_collision++; |
|---|
| | | console.log(names[data_index] + "==> REMAPPED ==>" + hashval); |
|---|
| | | |
|---|
| | | el1=document.getElementById("o"+hashval); |
|---|
| | | el2=document.getElementById("of"+hashval); |
|---|
| | | |
|---|
| | | el1.innerHTML=names[data_index]; |
|---|
| | | el2.innerHTML=phones[data_index]; |
|---|
| | | } |
|---|
| | | 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); |
|---|
| | | } |
|---|
| | | //} |
|---|
| | | |
|---|
| | | } |
|---|
| | | |
|---|
| | |
|---|
| | | el2.innerHTML=phones[data_index]; |
|---|
| | | |
|---|
| | | memory[hashval]=data_index; |
|---|
| | | backupmemory[hashval]=data_index; |
|---|
| | | insert_idx++; |
|---|
| | | if(insert_idx==8){ |
|---|
| | | if(insert_idx==13){ |
|---|
| | | alert("Completed!"); |
|---|
| | | } |
|---|
| | | else { |
|---|
| | |
|---|
| | | 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[i]="(01)"+Math.floor((Math.random() * 1000) + 1)+"-"+Math.floor((Math.random() * 1000) + 1); |
|---|
| | | 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]; |
|---|
| | | backupmemory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]; |
|---|
| | | |
|---|
| | | |
|---|
| | | /* Slide 1 actions */ |
|---|
| | |
|---|
| | | 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; |
|---|
| | | document.getElementById("s3value").innerHTML=document.getElementById("s3").innerHTML; |
|---|
| | | document.getElementById("s0number").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*/ |
|---|
| | | |
|---|
| | | } |
|---|
| | | |
|---|
| | |
|---|
| | | |
|---|
| | | |
|---|
| | | <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> |
|---|
| | | |
|---|
| | | <!-- |
|---|
| | |
|---|
| | | |
|---|
| | | </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 variable, 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> |
|---|
| | |
|---|
| | | <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"></span>(01)123-1234</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> |
|---|
| | | |
|---|
| | |
|---|
| | | <!-- <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">Building 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"> |
|---|
| | |
|---|
| | | <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> |
|---|
| | | <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"> </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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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">phone[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>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> |
|---|
| | | |
|---|
| | |
|---|
| | | <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> |
|---|
| | | <div id='ll0'><div class="addrvertical">phone[0]</div></div> |
|---|
| | | <div id='ll1'><div class="addrvertical">phone[1]</div></div> |
|---|
| | | <div id='ll2'><div class="addrvertical">phone[2]</div></div> |
|---|
| | | <div id='ll3'><div class="addrvertical">phone[3]</div></div> |
|---|
| | | <div id='ll4'><div class="addrvertical">phone[4]</div></div> |
|---|
| | | <div id='ll5'><div class="addrvertical">phone[5]</div></div> |
|---|
| | | <div id='ll6'><div class="addrvertical">phone[6]</div></div> |
|---|
| | | <div id='ll7'><div class="addrvertical">phone[7]</div></div> |
|---|
| | | <div id='ll8'><div class="addrvertical">phone[8]</div></div> |
|---|
| | | <div id='ll9'><div class="addrvertical">phone[9]</div></div> |
|---|
| | | <div id='ll10'><div class="addrvertical">phone[10]</div></div> |
|---|
| | | <div id='ll11'><div class="addrvertical">phone[11]</div></div> |
|---|
| | | <div id='ll12'><div class="addrvertical">phone[12]</div></div> |
|---|
| | | <div id='ll13'><div class="addrvertical">phone[13]</div></div> |
|---|
| | | </td> |
|---|
| | | <td> |
|---|
| | | <div id="currll"></div> |
|---|
| | |
|---|
| | | <button onclick="insertMissingIntoOpen(-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="o0" style="font-size:18px"> </div><div id="of0" 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="o1" style="font-size:18px"> </div><div id="of1" 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="o2" style="font-size:18px"> </div><div id="of2" 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="o3" style="font-size:18px"> </div><div id="of3" 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="o4" style="font-size:18px"> </div><div id="of4" 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="o5" style="font-size:18px"> </div><div id="of5" 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="o6" style="font-size:18px"> </div><div id="of6" 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="o7" style="font-size:18px"> </div><div id="of7" 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="o8" style="font-size:18px"> </div><div id="of8" 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="o9" style="font-size:18px"> </div><div id="of9" 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="o10" style="font-size:18px"> </div><div id="of10" 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="o11" style="font-size:18px"> </div><div id="of11" 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="o12" style="font-size:18px"> </div><div id="of12" 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">phone[0]</div><div id="o0" style="font-size:18px"> </div><div id="of0" 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">phone[1]</div><div id="o1" style="font-size:18px"> </div><div id="of1" 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">phone[2]</div><div id="o2" style="font-size:18px"> </div><div id="of2" 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">phone[3]</div><div id="o3" style="font-size:18px"> </div><div id="of3" 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">phone[4]</div><div id="o4" style="font-size:18px"> </div><div id="of4" 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">phone[5]</div><div id="o5" style="font-size:18px"> </div><div id="of5" 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">phone[6]</div><div id="o6" style="font-size:18px"> </div><div id="of6" 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">phone[7]</div><div id="o7" style="font-size:18px"> </div><div id="of7" 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">phone[8]</div><div id="o8" style="font-size:18px"> </div><div id="of8" 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">phone[9]</div><div id="o9" style="font-size:18px"> </div><div id="of9" 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">phone[10]</div><div id="o10" style="font-size:18px"> </div><div id="of10" 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">phone[11]</div><div id="o11" style="font-size:18px"> </div><div id="of11" 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">phone[12]</div><div id="o12" style="font-size:18px"> </div><div id="of12" style="font-size:11pt"> </div></span> |
|---|
| | | </div> |
|---|
| | | |
|---|
| | | |
|---|
| | | |
|---|
| | | <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> |
|---|
| | | |
|---|
| | | |
|---|
