Building an Hash Table in c++ - episode I

Hi everybody,

this is a new section dedicated to didactics issues where I try to explain step by step some problems and relative solutions derived from my lessons (I give private lessons). To inaugurate this new section, let's start talkin' about building an Hash Table, one of the most used examples for learning to use template classes. Yes, but what is an hash table, and what we need it for?? Hash table is a container of generic elements (integer, floating, classes...) which we can access using a code (for example a string, a number....), so for every elements corresponds another element. How do we dispose elements?? It should be better with a vector (supposing to use STL libraries) cause the access to elements is faster than other containers..Ok, let's choose a code composed by integer numbers and associate element A with code 54: we can associate A to the 54th element of our vector. Yeah, everytime we want the element with code 54 we get the 54th element, in this case A. First problem: memory is limitated, using this method we could exhaust it!! For example associating element 40000000 we waste too much memory, degrading performances..We need a limited vector and a function that given the code, transform it in an index included in the range of the vector..It's very easy, we have only to use the mod operator ( % in c ) with the maximum dimension of array. If we have a vector with dimension 127 our old code 40000000 will be transformed in 40000000 % 127 = 80. Using a code formed by a string, we have the same thing: we can get a number by a string adding every single char value, after that we can apply the mod operation again. Is that all? No, unfortunately. Using this method we can have collisions, that is have two codes that generate the same vector's position..How can we solve it? We must transform our vector of generic elements in a vector of lists of generic elements, so when we have two elements that generate the same index e.g. I1 we push elements back in the list at I1 position. We'll have a structure like this:

In the next lesson we will write the first draft of code, implementing the class' structure and the supporting functions...

::See you next post::