C++ hashing function?

I want to write some simple C++ code to practice the basic hashing function like linear probing, quadratic probing and double hashing.





Even though i have studied the notes i still dont have much of an idea about how to start coding. Especially about the hash table, key value and hash functions.....





can someone please kindly type out some C++ code showing how hashing really works .... key generation and stuff like that.





thanks

C++ hashing function?
Hi,


first of all the following code could not be consider the state of art about hashing due to fact that a forum is not the best place for this kind of answer :)





Remember that the main missing part are:


1st) a real hash function (for the example I create a hash function very is easy create collision ;)


2nd) the get from vector method (easy to implement, with the shrewdness to check if the element to extract is what we really want... we are in presence of collisions ;)





For this short example I'll consider the "linear probing" technique for resolving hash collision in a simple hash vector of string (i.e. the key corresponds to the value).





#include %26lt;iostream%26gt;


#include %26lt;string%26gt;





using namespace std;








class HashVector {


public:


HashVector(const size_t %26amp;Dim) : Dimension(Dim) {


Elements = new string*[Dim];





for(int i = 0; i %26lt; Dim; ++i) {


Elements[i] = NULL;


}


}


virtual ~HashVector() {


delete Elements;


}





virtual void add(const string %26amp;str) = 0;





void debugPrint() {


cout %26lt;%26lt; "HashVector contents:" %26lt;%26lt; endl %26lt;%26lt; endl;





for(size_t i = 0; i %26lt; Dimension; ++i) {





cout %26lt;%26lt; "\tVector[ " %26lt;%26lt; i %26lt;%26lt; " ] = ";


if ( NULL == Elements[i] ) {


cout %26lt;%26lt; "Empty";


} else {


cout %26lt;%26lt; *Elements[i];


}





cout %26lt;%26lt; endl;


}





cout %26lt;%26lt; endl;


}





protected:


size_t Dimension;


string **Elements;


};





class LinearProbingHashVector : public HashVector {


public:


LinearProbingHashVector(const size_t %26amp;Dim, const size_t %26amp;Step) :


HashVector(Dim), StepSize(Step) {}


virtual ~LinearProbingHashVector() {}





void add(const string %26amp;str) {


size_t Index = makeHash(str, 0);





Elements[Index] = new string(str);


}





private:


/* very simple hash function: sum all the ordinal position of the string


* adding the current step size in order to find the first free position


*/


size_t makeHash(const string %26amp;key, const size_t currentStep) {


size_t Index = currentStep % Dimension;





for(int i = 0; i %26lt; key.length(); ++i) {


Index += (unsigned int)key.c_str()[i];


Index = Index % Dimension;


}





if ( NULL != Elements[Index] ) {


Index = makeHash(key, currentStep + StepSize);


}





return Index;


}





size_t StepSize;


};





int main(int argc, char *argv[]) {


HashVector *HV = new LinearProbingHashVector(10, 3);





HV-%26gt;add("Conte");


HV-%26gt;add("Zero");





HV-%26gt;debugPrint();





HV-%26gt;add("etnoC");





HV-%26gt;debugPrint();





return 0;


}








cheers,
Reply:First steps are always the hardest to find and biggest hurdle. Don't give in and take answers for this from here.





Write your own code. Compile for every two new lines you add. Hard code as many values as you want. Then generalise the values one at a time. Good luck!