[Year 12 SofDev] Associative arrays

[Tyler, Simon J]

Thanks for the links and ideas Mark,

We did dictionaries and (a quick look at) hashes last semester since they are such a useful data structure it seemed a shame not to introduce them at the same time as the other basic structures. One task I gave the students was to read in a english dictionary from a file and find how many hash collisions it generates using Python's standard hash. It is different every time you run it due to the salting.

This semester we started off with security and talking about the differences between quick hashes used for hash tables and cryptographic hashes used for storing passwords. Quite a few of my students are rolling their own login and password systems (not a good idea in public facing code). The comparison between the two types of hashes ties into the exercise that you suggest.

A really interesting article about the standard hashes used by most languages is The moment when you realize every server in the world is vulnerable<https://medium.freecodecamp.com/hash-table-attack-8e4371fc5261>. It talks about a vulnerability in web servers using hash tables that exploits cleverly generated hash collisions to overload a server. And how the standard fix of salting the hashes used by most languages is not enough to completely stop this exploit. The solution is to find a new compromise point for the speed of the standard hash algorithms that makes the exploit impractical.

Simon

PS
I described linked lists to a couple of my more engaged students, and one of them responded with horror - "why would anyone want to do that?!"  :)

---

Simon Tyler
Classroom Teacher
Footscray City College


________________________________
From: sofdev-bounces at edulists.com.au [sofdev-bounces at edulists.com.au] on behalf of Mark [mark at vceit.com]
Sent: Tuesday, 30 August 2016 1:16 PM
To: Year 12 Software Development Teachers' Mailing List
Subject: [Year 12 SofDev] Associative arrays

Hi, hash fans

A couple of approachable explanations of hash functions, associative arrays and collisions can be found on Youtube. They would be good for your class' potential future hash users.

https://www.youtube.com/watch?v=MfhjkfocRR0
https://www.youtube.com/watch?v=h2d9b_nEzoA

There are several others, BTW. Have a look around.

Linked lists are not KK, but are often essential in solving collisions, and are good basic nutritious IT theory if you find the time.

Also, sparse arrays may become relevant as hash functions create huge hash values, requiring huge arrays that can accommodate huge hashed indexes. Sparse arrays are not key knowledge, but your stronger students might find them an interesting problem.

An interesting exercise is to get your kids to brainstorm hashing algorithms and choose the best one based on its speed, the number of collisions it will create, and the size of the necessary array will have to be. (Other criteria may also apply, e.g. whether similar values generate similar hash codes.)

Some very basic starting points for algorithms:
- the length of the string (very easy to compute, many many collisions)
- the sum of the ASCII codes of each letter of the string. (but letter positioning loses value, so "cat" and "act" will generate the same hash value)
- as above, but each letter's ASCII code is multiplied by the letter's position in the string. This introduces information based on the position of text, not just its presence, so "cat" and "act" generate different hash codes. - hard to compute, very few collisions, huge array needed.

- others?


Regards,
Mark
--

Mark Kelly

mark at vceit.com<mailto:mark at vceit.com>
http://vceit.com

IMPORTANT - This email and any attachments may be confidential. If received in error, please contact us and delete all copies. Before opening or using attachments check them for viruses and defects. Regardless of any loss, damage or consequence, whether caused by the negligence of the sender or not, resulting directly or indirectly from the use of any attached files our liability is limited to resupplying any affected attachments. Any representations or opinions expressed are those of the individual sender, and not necessarily those of the Department of Education and Training.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.edulists.com.au/pipermail/sofdev/attachments/20160830/d8b85488/attachment.html