view | history | commit | commitdiff
Samo Penic
2019-10-23 2bee68f6a75616eea5a26dbf398ca895958fe78e
commit | author | age
c43c7b 1 <html lang="en">
SP 2 <head>
3     <meta charset="utf-8" />
4     <meta name="viewport" content="width=1024" />
5     <meta name="apple-mobile-web-app-capable" content="yes" />
6     <title>Ljubljana Hardware Meetup :: Sputnik, 24.10.2019</title>
7     
8     <meta name="description" content="Short presentation of what hash tabes are, how they are implemented and how to use them when you are an electrical engineer. This presentation is based on impress.js default demo presentation" />
9     <meta name="author" content="Samo Penic" />
10
11     <link href="http://fonts.googleapis.com/css?family=Open+Sans:regular,semibold,italic,italicsemibold|PT+Sans:400,700,400italic,700italic|PT+Serif:400,700,400italic,700italic" rel="stylesheet" />
12
13     <link href="impress.js/css/impress-demo.css" rel="stylesheet" />
14     
15     <link rel="shortcut icon" href="favicon.png" />
16     <link rel="apple-touch-icon" href="apple-touch-icon.png" />
17 </head>
18
19 <body class="impress-not-supported">
20
21 <div class="fallback-message">
22     <p>Your browser <b>doesn't support the features required</b> by impress.js, so you are presented with a simplified version of this presentation.</p>
23     <p>For the best experience please use the latest <b>Chrome</b>, <b>Safari</b> or <b>Firefox</b> browser.</p>
24 </div>
25
26 <div id="impress">
2bee68 27 <script>
SP 28 var names;
29 var phones;
30 var memory;
31 var insert_idx=0;
32 function hash(stringval){
33     hashval= 0;
34     strlen=stringval.length;
35     i=0;
36     for(i=0;i<strlen;i++){
37         hashval=hashval+stringval.charCodeAt(0);
38     }
39     console.log(stringval + " == " + hashval %13);
40     return hashval % 13;
41 }
42
43 function currentInner(element,data_index){
44     element.innerHTML="Inserting <b>"+names[data_index]+ "</b>. Calculated hash_function is: <b>" + hash(names[data_index])+"</b>";
45 }
46
47
48
49 function insertIntoMemory(data_index){
50     if(data_index==-1) data_index=insert_idx;
51     hashval=hash(names[data_index]);
52     console.log("f"+hashval);
53     if(memory[hashval]!=-1){
54         alert("Collision!!!");
55     }
56     else{
57         el1=document.getElementById("f"+hashval);
58         el2=document.getElementById("nf"+hashval);
59
60         el1.innerHTML=names[data_index];
61         el2.innerHTML=phones[data_index];
62         
63         memory[hashval]=data_index;
64         insert_idx++;
65         if(insert_idx==12){
66             alert("Completed!");
67         }
68         else {
69             currentInner(document.getElementById("s1current"), insert_idx);
70         }
71     }
72 }
73
74
75 function loadNames(){
76     names=[
77         document.getElementById("name1").value,
78         document.getElementById("name2").value,
79         document.getElementById("name3").value,
80         document.getElementById("name4").value,
81         document.getElementById("name5").value,
82         document.getElementById("name6").value,
83         document.getElementById("name7").value,
84         document.getElementById("name8").value
85     ];
86     phones=[1,2,3,4,5,6,7,8]
87     for(i=0;i<8;i++){
88         phones[i]="(01)"+Math.floor((Math.random() * 1000) + 1)+"-"+Math.floor((Math.random() * 1000) + 1);
89     }
90     memory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];
91
92
93 /* Slide 1 actions */
94 //Names goes into storages s0-s4 on first slide...
95 document.getElementById("s0").innerHTML=names[0];
96 document.getElementById("s1").innerHTML=names[1];
97 document.getElementById("s2").innerHTML=names[2];
98 document.getElementById("s3").innerHTML=names[3];
99 document.getElementById("n0").innerHTML=phones[0];
100 document.getElementById("n1").innerHTML=phones[1];
101 document.getElementById("n2").innerHTML=phones[2];
102 document.getElementById("n3").innerHTML=phones[3];
103 //
104 document.getElementById("intro0").innerHTML=names[0];
105 document.getElementById("intro1").innerHTML=names[0];
106 document.getElementById("s0result").innerHTML=document.getElementById("s0").innerHTML;
107 document.getElementById("s0result").innerHTML=document.getElementById("n0").innerHTML;
108 /* End Slide 1 */
109
110 /*Filling the values into array demo until collision occurs */
111
112 currentInner(document.getElementById("s1current"), 0);
113 /*end demo until collision*/
114
115 }
116
117
118 </script>
c43c7b 119
SP 120  
121     <div id="naslovnica" class="step slide" data-x="-1000" data-y="-1500">
122     <h1>Hardware Meetup - Sputnik, 24. october 2019</h1>
123         <q>Hash tables</q><br />
124
125     <p class="center"> ... the background of their implementations.</p><br />
126
127     <p class="footnote">Samo Penič</p>
128     </div>
129
130     <!--
131         
132         The `id` attribute of the step element is used to identify it in the URL, but it's optional.
133         If it is not defined, it will get a default value of `step-N` where N is a number of slide.
134         
135         So in the example below it'll be `step-2`.
136         
137         The hash part of the url when this step is active will be `#/step-2`.
138         
139         You can also use `#step-2` in a link, to point directly to this particular step.
140         
141         Please note, that while `#/step-2` (with slash) would also work in a link it's not recommended.
142         Using classic `id`-based links like `#step-2` makes these links usable also in fallback mode.
143         
144     -->
145     <div class="step slide vsebina" data-x="-250" data-y="-1250" data-z="1500">
2bee68 146     <h1 class="naslov">About me...</h1>
c43c7b 147     <img class="samo" src="images/Samo1.png">
SP 148     
149     <ul>
2bee68 150     <li> phD in Electrical engineering</li>
SP 151     <li> working at the Faculty of electrical engineering, teaching fundamentals of EM fields</li>
152     <li> promoting open source since... ever?</li>
153     <li> hobby programmer </li>
c43c7b 154     </ul>
SP 155     
156     </div>
157
2bee68 158 <div class="step slide vsebina" data-x="-250" data-y="-500" data-z="750" data-rotate-x="90">
SP 159     <h1 class="naslov">Let's fill in the data...</h1>
160     <form>
161     <ol>
162     </li> Name: <input id="name1"></input><br />
163     </li> Name: <input id="name2"></input><br />
164     </li> Name: <input id="name3"></input><br />
165     </li> Name: <input id="name4"></input><br />
166     </li> Name: <input id="name5"></input><br />
167     </li> Name: <input id="name6"></input><br />
168     </li> Name: <input id="name7"></input><br />
169     </li> Name: <input id="name8"></input><br />
170     </ol><br /><br />
171     <button onClick="loadNames()">Save data</button>
172     </form>
173 </div>
c43c7b 174
2bee68 175 <div class="step slide vsebina" data-x="0" data-y="-1500" data-z="0">
SP 176         <h1 class="naslov">What is a hash table</h1>
177     <p>Sometimes also called associative array or dictionary. <b>It is a data structure used to map key into values</b></p>
178     <br /><br />
179     <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>
180     <br /><br />
181     <p style="font-size:18pt">It is widely used to build things such us dictionaries, telephone books, book indexes, ...</p><br />
182     <p>Hash table provide <b>Insertion, Deletion and Retreival</b> in <b>constant time</b>!</p>
183 </div>
184
185
186
187     <div class="step slide vsebina" data-x="1000" data-y="-1500" data-z="0">
188         <h1 class="naslov">However...</h1>
189
190     <p class="" style="margin-bottom:30px">The memory is accessible by addressing the data numerically.</p>
c43c7b 191     
2bee68 192         <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>
SP 193         <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>
194         <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>
195         <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>
196     <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 />
197
198     <p>Finding phone number of <span id="s3value">Darth</span> requires linear search through the array, which is not efficient.</p>
199
c43c7b 200     </div>
SP 201
202  <!--   <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
203     </div>
204 -->
2bee68 205
SP 206
207     <div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="0">
208         <h1 class="naslov">Mapping key to index</h1>
209
210         <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 />
211
212         <p>Let's try it out for our phone directory (array_size=13):</p>
213         <div id="s1current"></div><br />
214         <button onclick="insertIntoMemory(-1);">Insert</button>
215         <br /><br />
216
217         <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>
218         <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>
219         <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>
220         <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>
221         <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>
222         <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>
223         <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>
224         <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>
225         <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>
226         <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>
227         <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>
228         <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>
229         <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>
230
231     </div>
232
233
234     <div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="-1500">
235     <h1 class="naslov">Collisions!</h1>
236     
237     <p>They will occur. The probability depends on Load factor (LF=number_of_items/array_size)</p>
238     
239     <p>We can cope with collisions in multitude of ways:</p>
240     <ul>
241     <li>Closed addressing (chaining)
242     <li>Open addressing (linear probing) (million ways how to do it)
243     <li>using alternate hash functions (million ways how to do it)
244     <li>Resize array ;) (not a scientific way to do it)
245     </ul>
246     </div>
247
248
249     <div class="step slide vsebina" data-x="2000" data-y="-2500" data-z="0">
250     <h1 class="naslov">Closed addressing</h1>
251     
252     </div>
253
254
255     <div class="step slide vsebina" data-x="2000" data-y="-3500" data-z="0">
256     <h1 class="naslov">Open addressing</h1>
257     
258     </div>
259
260
261
262     <div class="step slide vsebina" data-x="3000" data-y="-1500" data-z="0">
263     <h1 class="naslov">Hash function properties</h1>
264     <ul>
265     <li>Hash function should minimize collisions
266     <li>Uniformly distribute hash values
267     <li>Are easy to calculate
268     </ul>
269     </div>
270
271     <div class="step slide vsebina" data-x="4000" data-y="-1500" data-z="0" data-rotate="90">
272     <h1 class="naslov">Python dictionaries</h1>
273     </div>
274
275
276     <div class="step slide vsebina" data-x="4000" data-y="-2500" data-z="0" data-rotate="90">
277     <h1 class="naslov">Hash tables in firmware</h1>
278     </div>
279
280
281     <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
282     </div>
283
284
285
c43c7b 286 </div>
SP 287
288 <div id="impress-toolbar"></div>
289
290 <div class="hint">
291     <p>Use a spacebar or arrow keys to navigate. <br/>
292        Press 'P' to launch speaker console.</p>
293 </div>
294 <script>
295 if ("ontouchstart" in document.documentElement) { 
296     document.querySelector(".hint").innerHTML = "<p>Swipe left or right to navigate</p>";
297 }
298 </script>
299
300 <script src="impress.js/js/impress.js"></script>
301 <script>impress().init();</script>
302
303
304 </body>
305 </html>
306