| | |
|---|
| | | |
|---|
| | | <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"> |
|---|
| | |
|---|
| | | var phones; |
|---|
| | | var memory; |
|---|
| | | var insert_idx=0; |
|---|
| | | var insert_idx_without_collision=0; |
|---|
| | | function hash(stringval){ |
|---|
| | | hashval= 0; |
|---|
| | | strlen=stringval.length; |
|---|
| | |
|---|
| | | |
|---|
| | | |
|---|
| | | |
|---|
| | | 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); |
|---|
| | |
|---|
| | | |
|---|
| | | 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==12){ |
|---|
| | | if(insert_idx==8){ |
|---|
| | | alert("Completed!"); |
|---|
| | | } |
|---|
| | | else { |
|---|
| | | currentInner(document.getElementById("s1current"), insert_idx); |
|---|
| | | currentInner(document.getElementById("currll"), insert_idx); |
|---|
| | | } |
|---|
| | | } |
|---|
| | | } |
|---|
| | |
|---|
| | | <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>... 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> |
|---|
| | | <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 /> |
|---|
| | |
|---|
| | | |
|---|
| | | <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> |
|---|
| | | |
|---|
| | | |
|---|
