Tuesday, January 26, 2016

Week 3, day 1 - OOP and making my own hash

Part 2: OOP

The best part of today was learning how hash tables (aka dictionaries) work on a fairly basic level.  Essentially, the key of a dictionary entry {'key': 'value'} is converted to a number using a hashing function.  The essential elements of a hashing function are:  a prime number and a means of converting a text string to a number.  The prime can be of arbitrary size, but any reasonably sized dictionary would need a fairly large number.  The unicode values for letters in the key can be used as one way of generating a number.  When that number is divided by the prime, a semi-unique value is determined. (semi-unique because there will inevitably be a collision when two keys generate the same index).

One of the other interesting things about this project was building the hash as a class.  Doing so required overloading the __getitem__ and __setitem__ built-in methods.  I'd seen classes a bit in Learn Python the Hard Way and Code Academy, but I had no idea that built-in overload was possible.  So that was two lessons in one...

As a further extension, and third part of the lesson, I built a collision-handling mechanism whereby, instead of simply appending a value to the index, a key:value tuple was appended.  Then, when my class __getitem__ was called, the lookup method would iterate through the tuples looking for the matching key.


1 comment: