[Year 12 SofDev] Associative arrays

[Mark]

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
http://vceit.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.edulists.com.au/pipermail/sofdev/attachments/20160830/b82bbab3/attachment.html