Databases
StackOverflow2013
Postsdbo
POHash table(linear probing)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHash table(linear probing)
    primarykey
    data
    text
    <p>I am making a hash table using linear probing and i have to resize the array when ever the load factor i.e (no. of elements entered in hashtable)/(size of hashtable), becomes greater than 0.5, i have to resize the array.I am doing the resizing by initializing a pointer in a class which contains functions related to hashtable.I am putting the pointer equal to an array of a struct (struct only contains a string) of size 100.every time load factor becomes greater than 0.5, i resize the array by making a new array of double the previous size and point the pointer to the new array.I also have an int which stores current size of array and which is updated with every instance in which resize function is used.The number of elements inserted are incremented with every call to insert function.Am I doing this correctly?Below is my code</p> <pre><code>#include &lt;cstring&gt; #include &lt;vector&gt; #include &lt;math.h&gt; #include &lt;iomanip&gt; using namespace std; int power(int a,int b) { for (int i=0;i&lt;b;i++) { a*=a; } return a; }; struct Bucket { string word; }; const int size=100; class LProbing { private: int a; //a constant which is used in hashing int cursize; //current size of hash table Bucket *Table; //pointer to array of struct int loadfactor; //ratio of number of elements entered over size of hashtable int n; //number of elements entered Bucket table[size]; //array of structs public: LProbing(int A); //constant is decided by user void resize(); void insert(string word); void Lookup(string word); }; LProbing::LProbing(int A) { cursize=size; a=A; Table=table; loadfactor=0; //initially loadfactor is 0 as number of elements entered are 0 n=0; } void LProbing::resize() { cout&lt;&lt;"resize"&lt;&lt;endl; loadfactor=n/cursize; //ensuring if resize needs to be done if (loadfactor&lt;=0.5) { return; } const int s=2*cursize; Bucket PTable[s]; for (int i=0;i&lt;cursize;i++) { if (Table[i].word.empty()) continue; //rehashing the word onto the new array string w=Table[i].word; int key=0; for (int j=0;j&lt;w.size();j++) { unsigned char b=(unsigned char)w[j]; key+=(int)power(a,i)*b; } key=key%(2*cursize); PTable[key].word=w; //entering the word in the new array } Table=PTable; //putting pointer equal to new array cursize=2*cursize; //doubling the current size of array } void LProbing::insert(string word) { cout&lt;&lt;"1"&lt;&lt;endl; n++; //incrementing the number of elements entered with every call to insert //if loadfactor is greater than 0.5, resize array loadfactor=n/cursize; if (loadfactor&gt;0.5) { resize(); } //hashing the word int k=0; for (int i=0;i&lt;word.size();i++) { unsigned char b=(unsigned char)word[i]; int c=(int)((power(a,i))*b); k+=c; cout&lt;&lt;c&lt;&lt;endl; } int key=0; key=k%cursize; cout&lt;&lt;key&lt;&lt;endl; //if the respective key index is empty enter the word in that slot if (Table[key].word.empty()==1) { cout&lt;&lt;"initial empty slot"&lt;&lt;endl; Table[key].word=word; } else //otherwise enter in the next slot { //searching array for empty slot while (Table[key].word.empty()==0) { k++; key=k%cursize; } //when empty slot found,entering the word in that bucket Table[key].word=word; cout&lt;&lt;"word entered"&lt;&lt;endl; } } #include "Linear Probing.cpp" #include &lt;fstream&gt; using namespace std; int main() { LProbing H(35); ifstream fin; fin.open("dict.txt"); vector&lt;string&gt; D; string d; while (getline(fin,d)) { if (!d.empty()) { D.push_back(d); } } fin.close(); for (int i=0;i&lt;D.size();i++) { H.insert(D[i]); } system("PAUSE"); return 0; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USdigi_exp527
    1. USdigi_exp527
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHash table(linear probing)
      1. USdigi_exp527
      1. VTFavorite
    2. VO
      singulars
      1. POHash table(linear probing)
      1. USwchargin
      1. VTFavorite
    1. COTo convince yourself that it's working (or not), construct a suite of unit tests.
      singulars
      1. POHash table(linear probing)
      1. USNPE
    2. COWhen i am running this code on a file of words, i sometimes get negative values of key.i don't understand why that happens because i am not subtracting anything and i convert every letter to unsigned char first before calculating it's value.
      singulars
      1. POHash table(linear probing)
      1. USdigi_exp527
    3. COas a result of negative key, the program gives an error.
      singulars
      1. POHash table(linear probing)
      1. USdigi_exp527
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload