When constructing solutions as a programmer, time complexity should always be taken into consideration; the necessity of optimization is a simple fact of life. This process can be incredibly frustrating, especially for those who are just beginning to consider computation speed. However, there are structures for organizing and processing data which are significantly more efficient than the available alternatives. These structures represent a necessary tool for successful developers, one of which we will be exploring together: hash tables.
The hashing function is the part of the program which takes a key and converts it to a number which will be the index at which to store it. Visualize a box, into which you empty a container of tuples, or key-value pairs. Output is an array storing the key-value pair at a numeric index. The manner by which the index is assigned varies contingent on the hash function’s implementation. Not all hashing functions are equal, some are better at creating an even distribution of key-value pairs. If every tuple is placed in the same index, then the time complexity will be comparable to that of a plain array, linear.
Here we initialize the HashTable class:
Hashing function example implementation below originally posted here:
The second part of hash table implementation is the logic dedicated to handling collisions, or the instances in which there are multiple values at a particular index, called the bucket. This is accomplished by looping through all tuples in the hash table’s index of interest to find the desired tuple.
There is a great deal of confusion regarding the comparison between objects and hash tables. This is much like an attempted comparison between apples and granny smith apples, one is a subset of the other with particular qualities. The advantages offered by hash tables include its ability to handle cases in which a key corresponds with a native object attribute and provides constant time lookup. Below is a retrieve method added to the prototype of our HashTable class with a constant lookup time on average: