presentations/meetup-hashtables.git

Added singlepage version of presentation

Samo Penic

2019-12-11 4ecb96bc16a0b5bccd0a9186af95d846b00c6ca6

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" />
0d52a3	17	<style>
SP	18	div.linkedlist{
	19	width:120px;height:35px;border:1px solid #000;font-size:16px;display:inline-block;padding-left:10px;margin-left:30px;
	20	}
	21	div.linkedlist::before{
	22	content: '\1F82A';
	23	font-size: 16pt;
	24	left: -1.5em;
	25	margin-top:-5px;
	26	position: relative;
	27	}
	28
	29	div.addrvertical{
	30	width:90px;height:35px;border:1px solid #000;background:grey;color:white;font-size:16px;display:inline-block
	31	}
	32
	33	</style>
c43c7b	34	</head>
SP	35
	36	<body class="impress-not-supported">
	37
	38	<div class="fallback-message">
	39	<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>
	40	<p>For the best experience please use the latest <b>Chrome</b>, <b>Safari</b> or <b>Firefox</b> browser.</p>
	41	</div>
	42
	43	<div id="impress">
2bee68	44	<script>
SP	45	var names;
	46	var phones;
	47	var memory;
2d5ffe	48	var backupmemory;
2bee68	49	var insert_idx=0;
0d52a3	50	var insert_idx_without_collision=0;
2bee68	51	function hash(stringval){
SP	52	hashval= 0;
	53	strlen=stringval.length;
	54	i=0;
	55	for(i=0;i<strlen;i++){
	56	hashval=hashval+stringval.charCodeAt(0);
	57	}
	58	console.log(stringval + " == " + hashval %13);
	59	return hashval % 13;
	60	}
	61
	62	function currentInner(element,data_index){
	63	element.innerHTML="Inserting <b>"+names[data_index]+ "</b>. Calculated hash_function is: <b>" + hash(names[data_index])+"</b>";
	64	}
	65
	66
	67
0d52a3	68	function insertMissingIntoLL(data_index){
SP	69	if(data_index==-1) data_index=insert_idx;
	70	hashval=hash(names[data_index]);
	71	console.log("f"+hashval);
	72	elll=document.getElementById("ll"+hashval);
	73	elll.innerHTML=elll.innerHTML+"<div class='linkedlist'>"+names[data_index]+"</div>";
	74
	75	memory[hashval]=data_index;
	76	insert_idx++;
215778	77	if(insert_idx==13){
SP	78	document.getElementById("currll").innerHTML="DONE!";
0d52a3	79	alert("Completed!");
SP	80	}
	81	else {
	82	currentInner(document.getElementById("s1current"), insert_idx);
	83	currentInner(document.getElementById("currll"), insert_idx);
	84	}
	85
	86	}
	87
d01ede	88	function insertMissingIntoOpen(data_index){
SP	89	insert_idx=insert_index_without_collision;
2d5ffe	90	if(data_index==-1) data_index=insert_idx;
d01ede	91	hashval=hash(names[data_index]);
SP	92	console.log("f"+hashval);
215778	93	oldhashval=hashval;
2d5ffe	94	while(backupmemory[hashval]!=-1) hashval=(hashval+1)%13;
SP	95	backupmemory[hashval]=data_index;
d01ede	96	insert_idx++;
2d5ffe	97	insert_index_without_collision++;
SP	98	console.log(names[data_index] + "==> REMAPPED ==>" + hashval);
d01ede	99
SP	100	el1=document.getElementById("o"+hashval);
	101	el2=document.getElementById("of"+hashval);
	102
	103	el1.innerHTML=names[data_index];
	104	el2.innerHTML=phones[data_index];
215778	105	if(oldhashval!=hashval){
SP	106	el1.style.color="red";
	107	el2.style.color="red";
	108	}
	109	if(insert_idx==13){
2d5ffe	110	document.getElementById("open1current").innerHTML="DONE!";
215778	111	alert("Completed!");
2d5ffe	112	} else{
SP	113	currentInner(document.getElementById("open1current"), insert_idx);
	114	}
	115	//}
d01ede	116
SP	117	}
0d52a3	118
2bee68	119	function insertIntoMemory(data_index){
SP	120	if(data_index==-1) data_index=insert_idx;
	121	hashval=hash(names[data_index]);
	122	console.log("f"+hashval);
	123	if(memory[hashval]!=-1){
	124	alert("Collision!!!");
0d52a3	125	insert_index_without_collision=insert_idx;
2bee68	126	}
SP	127	else{
	128	el1=document.getElementById("f"+hashval);
	129	el2=document.getElementById("nf"+hashval);
	130
	131	el1.innerHTML=names[data_index];
	132	el2.innerHTML=phones[data_index];
0d52a3	133
SP	134	elll=document.getElementById("ll"+hashval);
	135	elll.innerHTML=elll.innerHTML+"<div class='linkedlist'>"+names[data_index]+"</div>";
d01ede	136
SP	137	el1=document.getElementById("o"+hashval);
	138	el2=document.getElementById("of"+hashval);
	139
	140	el1.innerHTML=names[data_index];
	141	el2.innerHTML=phones[data_index];
0d52a3	142
2bee68	143	memory[hashval]=data_index;
2d5ffe	144	backupmemory[hashval]=data_index;
2bee68	145	insert_idx++;
215778	146	if(insert_idx==13){
2bee68	147	alert("Completed!");
SP	148	}
	149	else {
	150	currentInner(document.getElementById("s1current"), insert_idx);
d01ede	151	currentInner(document.getElementById("open1current"), insert_idx);
0d52a3	152	currentInner(document.getElementById("currll"), insert_idx);
2bee68	153	}
SP	154	}
	155	}
	156
	157
	158	function loadNames(){
	159	names=[
	160	document.getElementById("name1").value,
	161	document.getElementById("name2").value,
	162	document.getElementById("name3").value,
	163	document.getElementById("name4").value,
	164	document.getElementById("name5").value,
	165	document.getElementById("name6").value,
	166	document.getElementById("name7").value,
215778	167	document.getElementById("name8").value,
SP	168	document.getElementById("name9").value,
	169	document.getElementById("name10").value,
	170	document.getElementById("name11").value,
	171	document.getElementById("name12").value,
	172	document.getElementById("name13").value
2bee68	173	];
215778	174	phones=[1,2,3,4,5,6,7,8,9,10,11,12,13]
SP	175	for(i=0;i<13;i++){
2d5ffe	176	phones[i]="(01)"+Math.floor((Math.random() * 9000) + 1000)+"-"+Math.floor((Math.random() * 900) + 100);
2bee68	177	}
SP	178	memory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];
2d5ffe	179	backupmemory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];
2bee68	180
SP	181
	182	/* Slide 1 actions */
	183	//Names goes into storages s0-s4 on first slide...
	184	document.getElementById("s0").innerHTML=names[0];
	185	document.getElementById("s1").innerHTML=names[1];
	186	document.getElementById("s2").innerHTML=names[2];
	187	document.getElementById("s3").innerHTML=names[3];
	188	document.getElementById("n0").innerHTML=phones[0];
	189	document.getElementById("n1").innerHTML=phones[1];
	190	document.getElementById("n2").innerHTML=phones[2];
	191	document.getElementById("n3").innerHTML=phones[3];
	192	//
	193	document.getElementById("intro0").innerHTML=names[0];
	194	document.getElementById("s0result").innerHTML=document.getElementById("s0").innerHTML;
2d5ffe	195	document.getElementById("s3value").innerHTML=document.getElementById("s3").innerHTML;
SP	196	document.getElementById("s0number").innerHTML=document.getElementById("n0").innerHTML;
2bee68	197	/* End Slide 1 */
SP	198
	199	/Filling the values into array demo until collision occurs /
	200
	201	currentInner(document.getElementById("s1current"), 0);
	202
	203	}
	204
	205
	206	</script>
c43c7b	207
SP	208
	209	<div id="naslovnica" class="step slide" data-x="-1000" data-y="-1500">
215778	210	<h1>Hardware Meetup - Sputnik, 24. October 2019</h1>
c43c7b	211	<q>Hash tables</q><br />
SP	212
215778	213	<p class="center"> ... the basic background of their implementations.</p><br />
c43c7b	214
SP	215	<p class="footnote">Samo Penič</p>
215778	216	<img src="images/hashtag.png" style="width:500px" />
c43c7b	217	</div>
SP	218
	219	<!--
	220
	221	The `id` attribute of the step element is used to identify it in the URL, but it's optional.
	222	If it is not defined, it will get a default value of `step-N` where N is a number of slide.
	223
	224	So in the example below it'll be `step-2`.
	225
	226	The hash part of the url when this step is active will be `#/step-2`.
	227
	228	You can also use `#step-2` in a link, to point directly to this particular step.
	229
	230	Please note, that while `#/step-2` (with slash) would also work in a link it's not recommended.
	231	Using classic `id`-based links like `#step-2` makes these links usable also in fallback mode.
	232
	233	-->
	234	<div class="step slide vsebina" data-x="-250" data-y="-1250" data-z="1500">
2bee68	235	<h1 class="naslov">About me...</h1>
c43c7b	236	<img class="samo" src="images/Samo1.png">
SP	237
	238	<ul>
2bee68	239	<li> phD in Electrical engineering</li>
SP	240	<li> working at the Faculty of electrical engineering, teaching fundamentals of EM fields</li>
	241	<li> promoting open source since... ever?</li>
	242	<li> hobby programmer </li>
c43c7b	243	</ul>
SP	244
	245	</div>
	246
	247
2bee68	248	<div class="step slide vsebina" data-x="0" data-y="-1500" data-z="0">
SP	249	<h1 class="naslov">What is a hash table</h1>
	250	<p>Sometimes also called associative array or dictionary. <b>It is a data structure used to map key into values</b></p>
	251	<br /><br />
215778	252	<p class="center">phone_number["<span id='intro0'>Yoda</span>"]</p><br />
3d558a	253	<p class="center" style="font-size:18pt"> stores and returns us the information stored for variable, object, ...</p>
2bee68	254	<br /><br />
SP	255	<p style="font-size:18pt">It is widely used to build things such us dictionaries, telephone books, book indexes, ...</p><br />
	256	<p>Hash table provide <b>Insertion, Deletion and Retreival</b> in <b>constant time</b>!</p>
	257	</div>
	258
	259
	260
	261	<div class="step slide vsebina" data-x="1000" data-y="-1500" data-z="0">
	262	<h1 class="naslov">However...</h1>
	263
215778	264	<p class="" style="margin-bottom:30px">The computer memory is accessible by addressing the data numerically.</p>
c43c7b	265
215778	266	<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>
SP	267	<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>
	268	<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>
	269	<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>
	270	<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 />
2bee68	271
SP	272	<p>Finding phone number of <span id="s3value">Darth</span> requires linear search through the array, which is not efficient.</p>
	273
c43c7b	274	</div>
SP	275
	276	<!-- <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
	277	</div>
	278	-->
215778	279
SP	280	<div class="step slide vsebina" data-x="1000" data-y="-500" data-z="750" data-rotate-x="90">
3d558a	281	<h1 class="naslov">Building a phonebook...</h1>
215778	282	<form>
SP	283	<table style="width:100%;">
	284	<col width="70%">
	285	<col width="30%">
	286	<tr>
	287	<td>
	288	<ol style="font-size:16pt;">
	289	</li> Name: <input id="name1"></input><br />
	290	</li> Name: <input id="name2"></input><br />
	291	</li> Name: <input id="name3"></input><br />
	292	</li> Name: <input id="name4"></input><br />
	293	</li> Name: <input id="name5"></input><br />
	294	</li> Name: <input id="name6"></input><br />
	295	</li> Name: <input id="name7"></input><br />
	296	</li> Name: <input id="name8"></input><br />
	297	</li> Name: <input id="name9"></input><br />
	298	</li> Name: <input id="name10"></input><br />
	299	</li> Name: <input id="name11"></input><br />
	300	</li> Name: <input id="name12"></input><br />
	301	</li> Name: <input id="name13"></input><br />
	302	</ol>
	303	</td>
	304	<td>
	305	<button onClick="loadNames()">Save data</button><br />
	306	</td>
	307	</tr>
	308	</table>
	309	</form>
	310	</div>
2bee68	311
SP	312
	313	<div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="0">
	314	<h1 class="naslov">Mapping key to index</h1>
	315
0d52a3	316	<p>... is performed by so called hash functions. It can be as simple as <b>sum(ascii_code[i]) % array_size</b></p><br />
2bee68	317
0d52a3	318	<p>Let's try it out for our phone directory (array_size=13):</p><br />
2bee68	319	<div id="s1current"></div><br />
SP	320	<button onclick="insertIntoMemory(-1);">Insert</button>
	321	<br /><br />
	322
215778	323	<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>
SP	324	<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>
	325	<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>
	326	<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>
	327	<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>
	328	<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>
	329	<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>
	330	<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>
	331	<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>
	332	<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>
	333	<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>
	334	<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>
	335	<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>
2bee68	336
SP	337	</div>
	338
	339
	340	<div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="-1500">
	341	<h1 class="naslov">Collisions!</h1>
	342
215778	343	<p>They will occur. The probability depends on Load factor (LF=number_of_items/array_size)</p><br />
2bee68	344
215778	345	<p>We can cope with collisions in different of ways:</p><br />
2bee68	346	<ul>
SP	347	<li>Closed addressing (chaining)
215778	348	<li>Open addressing (linear probing)
SP	349	<li>using alternate hash functions
	350	<li>Resize the array ;)
2bee68	351	</ul>
SP	352	</div>
	353
	354
	355	<div class="step slide vsebina" data-x="2000" data-y="-2500" data-z="0">
	356	<h1 class="naslov">Closed addressing</h1>
0d52a3	357	<table style="width:100%">
SP	358	<col width="70%">
	359	<col width="30%">
	360	<tr>
	361	<td>
701627	362	<div id='ll0'><div class="addrvertical">phone[0]</div></div>
SP	363	<div id='ll1'><div class="addrvertical">phone[1]</div></div>
	364	<div id='ll2'><div class="addrvertical">phone[2]</div></div>
	365	<div id='ll3'><div class="addrvertical">phone[3]</div></div>
	366	<div id='ll4'><div class="addrvertical">phone[4]</div></div>
	367	<div id='ll5'><div class="addrvertical">phone[5]</div></div>
	368	<div id='ll6'><div class="addrvertical">phone[6]</div></div>
	369	<div id='ll7'><div class="addrvertical">phone[7]</div></div>
	370	<div id='ll8'><div class="addrvertical">phone[8]</div></div>
	371	<div id='ll9'><div class="addrvertical">phone[9]</div></div>
	372	<div id='ll10'><div class="addrvertical">phone[10]</div></div>
	373	<div id='ll11'><div class="addrvertical">phone[11]</div></div>
	374	<div id='ll12'><div class="addrvertical">phone[12]</div></div>
	375	<div id='ll13'><div class="addrvertical">phone[13]</div></div>
0d52a3	376	</td>
SP	377	<td>
	378	<div id="currll"></div>
	379	<button onclick="insertMissingIntoLL(-1);">Insert</button>
2bee68	380
0d52a3	381	</td>
SP	382
	383	</tr>
	384	</table>
	385
2bee68	386	</div>
SP	387
	388
	389	<div class="step slide vsebina" data-x="2000" data-y="-3500" data-z="0">
	390	<h1 class="naslov">Open addressing</h1>
d01ede	391
SP	392	<div id="open1current"></div><br />
	393	<button onclick="insertMissingIntoOpen(-1);">Insert</button>
	394	<br /><br />
	395
701627	396	<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>
SP	397	<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>
	398	<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>
	399	<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>
	400	<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>
	401	<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>
	402	<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>
	403	<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>
	404	<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>
	405	<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>
	406	<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>
	407	<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>
	408	<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>
2bee68	409	</div>
SP	410
	411
	412
	413	<div class="step slide vsebina" data-x="3000" data-y="-1500" data-z="0">
215778	414	<h1 class="naslov">Hash function has to...</h1>
2bee68	415	<ul>
215778	416	<li>minimize collisions
SP	417	<li>uniformly distribute hash values
	418	<li>be easy to calculate
2bee68	419	</ul>
SP	420	</div>
	421
	422	<div class="step slide vsebina" data-x="4000" data-y="-1500" data-z="0" data-rotate="90">
	423	<h1 class="naslov">Python dictionaries</h1>
215778	424	<p>Python relys heavily on dictionaries, so it is important they are efficient. Uses open addressing multihash to minimize collisions.</p>
SP	425	<pre style="font-size:15pt;margin-top:-10px">
	426	<code>
	427	table = [None] * n;
	428	for hash, key, value in entries:
	429	perturb = hash
	430	i = hash % n
	431	while table[i] is not None:
	432	#collision
	433	i = (5 * i * perturb + 1) % n
	434	perturb >>= 5
	435	table[i] = (key, value)
	436	</code></pre>
	437
	438	<p>See talk: Raymond Hettinger -- Modern dictionaries (SF Python 2006)</p>
2bee68	439	</div>
SP	440
	441
	442	<div class="step slide vsebina" data-x="4000" data-y="-2500" data-z="0" data-rotate="90">
	443	<h1 class="naslov">Hash tables in firmware</h1>
215778	444	<ul>
SP	445	<li>Hash tables have average time complexity around O(1) for I,L,D
	446	<li>Do not resize tables - plan in advance
	447	<li>Use the power of prime numbers
	448	<li>Storing pointers of data in hash is not a bad idea (!)
	449	<ul style="margin-left:50px">
	450	<li>to save memory, when data is large
	451	<li>to get ordered dict if needed
	452	</ul>
2bee68	453	</div>
SP	454
	455
	456	<div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
	457	</div>
	458
	459
	460
c43c7b	461	</div>
SP	462
	463	<div id="impress-toolbar"></div>
	464
	465	<div class="hint">
	466	<p>Use a spacebar or arrow keys to navigate. <br/>
	467	Press 'P' to launch speaker console.</p>
	468	</div>
	469	<script>
	470	if ("ontouchstart" in document.documentElement) {
	471	document.querySelector(".hint").innerHTML = "<p>Swipe left or right to navigate</p>";
	472	}
	473	</script>
	474
	475	<script src="impress.js/js/impress.js"></script>
	476	<script>impress().init();</script>
	477
	478
	479	</body>
	480	</html>
	481