C++

Forum

 
implementing hash table with vectors

miamidawgs (42)
I wrote this program that is supposed to hash values and place them in a table. It uses 2 hash functions and 2 collision resolution strategies. The first function calculates the last 7 characters of the key which is in hex. the second divides the hex key in 7 groups and XORs the value. The collision strategies are linear probing and double hashing. The problem I am having is with the functions and not with the main function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
#include "hash140.h"
#include <cstdio>
#include <cstdlib>
using namespace std;

HashTable::HashTable( int table_size, string function, string collision )
{
   nkeys = table_size;               // sets size of table in nKeys
   if( function == "Last7" )
   {
      Fxn = 0;                    // sets Fxn to 0 if function is Last7
   }
   else
   {
      Fxn = 1;                    // sets Fxn to 1 if function is XOR
   }
   if( collision == "Linear" )
   {
      Coll = 0;               // sets Coll to 0 if strategy is linear
   }
   else
   {
       Coll = 1;             // sets Coll to 1 if strategy is double
   }
   keys.resize( nkeys );   // resize keys vector to size of table
   vals.resize( nkeys );  // resize vals vector to size of table
}
void HashTable::Add_Hash( string &key, string &val )
{
vector <string> temp;       // temp variable to hold key
int Xval = 0;              // holds value of XOR
int count = 0;            // count variable
int count2 = 6;          // 2nd count variable set to length of key for Last7
int count3 = 0;         // 3rd count variable
int counter = 0;       // number of elements in table

for( count = 0; count < nkeys; count++ )
{
    if( keys[count] != " " )
    {
        counter++;      // increment counter
    }
}
if( counter == nkeys )
{
    fprintf( stderr,"Hash Table Full\n" );
    exit( EXIT_FAILURE );
}
else if( Fxn == 0 )
{
    if( Coll == 0 )
    {
        temp.resize( 1 );       // resize temp
        for( count = key.size(); count > key.size() - 7 || count > 0; count-- )
        {
            temp[0][count2] = key[count];       // set temp to last 7 of the key
            count2--;                      // decrement count2
        }
        count = atoi( temp[0].c_str() ) % nkeys;             // set count to int value of hex mod table size
        while( keys[count] != " " )
        {
            count++;                    // go to next slot to see if empty
            tmp++;                     // increment # of probes
         }
        keys[count] = key;            // put key in hash table
        vals[count] = val;           // put value in hash table
    }
    else
    {
        temp.resize( 1 );           // resize temp
        for( count = key.size(); count > key.size() - 7 || count > 0; count-- )
        {
            temp[0][count2] = key[count];      // set temp to last 7 of the key
            count2--;                      // decrement count2
        }
        count = atoi( temp[0].c_str() ) % nkeys;            // set count to int value of hex mod table size
        while( keys[count] != " " )
        {
            tmp++;                               // increment # of probes
            if( tmp == nkeys )
            {
                fprintf( stderr, "Couldn't put %s into the table\n", key.c_str() );
                break;
            }

            temp.resize( (key.size()/7) + 1 );  // resize temp to number of groups of 7
            for( count2 = 0; count2 < temp.size(); count2++ )
            {
                for( count3 = 0; count3 < key.size(); count3 + 7 )
                {
                    temp[count2][count3] = key[count3+(count2*7)];      // set temp vector to groups of 7
                }
                Xval ^= atoi( temp[count2].c_str() );   // compute XOR value
            }
            Xval = Xval % nkeys;        // calculate mod value
            if( Xval > 0 )
            {
                count += Xval;         // add to first probe
            }
             else
                count += 1;             // add 1 to because Xval is 0
        }
        keys[count] = key;      // set key in table
        vals[count] = val;     // set value in table
    }
}
else
{
    if( Coll == 0 )
    {
        temp.resize( (key.size()/7) + 1 );  // resize temp to number of groups of 7
        for( count = 0; count < temp.size(); count++ )
        {
            for( count2 = 0; count2 < key.size(); count2 + 7 )
            {
                temp[count][count2] = key[count2+(count*7)];      // set temp vector to groups of 7
            }
            Xval ^= atoi( temp[count].c_str() );   // compute XOR value
        }
        count = Xval % nkeys;        // calculate mod value
        while( keys[count] != " " )
        {
            count++;            // go to next slot in table
            tmp++;             // increment # of probes
        }
        keys[count] = key;     // set key in table
        vals[count] = val;    // set value in table
    }
    else
    {
        temp.resize( (key.size()/7) + 1 );  // resize temp to number of groups of 7
        for( count2 = 0; count2 < temp.size(); count2++ )
        {
            for( count3 = 0; count3 < key.size(); count3 + 7 )
            {
                temp[count2][count3] = key[count3+(count2*7)];      // set temp vector to groups of 7
            }
            if( count2 > 0 )
            {
                Xval ^= atoi( temp[count2].c_str() );   // compute XOR value
            }
        }
        count = Xval % nkeys;        // calculate mod value
        while( keys[count] != " " )
        {
            tmp++;                       // increment # of probes
            temp.resize( 1 );           // resize temp
            for( count2 = key.size(); count2 > key.size() - 7 || count2 > 0; count2-- )
            {
                temp[0][count3] = key[count2];      // set temp to last 7 of the key
                count3--;                      // decrement count2
            }
            count2 = atoi( temp[0].c_str() ) % nkeys;            // set count2 to int value of hex mod table size
            if( count2 > 0 )
            {
                count += count2;
            }
            else
            {
                count += 1;
            }
        }
        keys[count] = key;      // set key in table
        vals[count] = val;     // set value in table
    }
}
}

string HashTable::Find( string &key )
{
    int count = 0;          // count variable
    string Nval = " ";     // empty string

    for( count = 0; count < nkeys; count++ )
    {
       if( keys[count] == key )
       {
          return vals[count];     // return value if found
          Nval = "found";
        }
      }
      if( Nval == " " )
      {
         return Nval;        // return empty string
       }

  }

 void HashTable::Print()
 {
   int count = 0;     // count variable

   for( count = 0; count < nkeys; count++ )
   {
      if( keys[count] != " " )
      {
         printf( "%5i %s %s\n", count, keys[count].c_str(),            vals[count].c_str() );   // print nonempty table slots
       }
    }
   }


The result I get looks like it keeps trying to enter the same value in the table. Does anyone know how I can fix this. I also have not tested the whole thing so if you see anymore errors let me know. Thanks
Last edited on
SakurasouBusters (732)
Can you show us the header file "hash140.h"?
miamidawgs (42)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class HashTable {
  public:
    HashTable(int table_size, string function, string collision);
    void Add_Hash(string &key, string &val);
    string Find(string &key);
    void Print();
    int Total_Probes();
  protected:
    vector <string> keys;
    vector <string> vals;
    int nkeys;
    int Fxn;
    int Coll;
    int tmp;
};


miamidawgs (42)
here is main:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
main(int argc, char **argv)
{
  string s, s2, key;
  string digits = "0123456789abcdef";
  int i;
  HashTable *h;
  int ts;
  ifstream f;

  if (argc != 5 && argc != 4) usage("");
  ts = atoi(argv[1]);
  if (ts <= 0) usage("Bad Table Size");
  s = argv[2];
  if (s != "Last7" && s != "XOR") usage("Bad function");
  s = argv[3];
  if (s != "Linear" && s != "Double") usage("Bad resolution");
  if (argc == 5) {
    f.open(argv[4]);
    if (f.fail()) { perror(argv[4]); exit(1); }
  }

  h = new HashTable(ts, argv[2], argv[3]);
  if (argc == 5) {
    while (getline(f, s)) {
      for (i = 0; digits.find(s[i]) != string::npos; i++) ;
      if (i == 0 || i == s.size() || s[i] != ' ') {
        cerr << "Bad line: " << s << endl;
        exit(1);
      }
      key = s.substr(0, i);
      for (; s[i] == ' '; i++) ;
      if (i == s.size()) { cerr << "Bad line: " << s << endl; exit(1); }
      s2 = s.substr(i);
      if (h->Find(key) != "") {
        fprintf(stderr, "Key %s inserted twice\n", key.c_str());
        exit(1);
 }
      h->Add_Hash(key, s2);
    }
    f.close();
  }

  while (cin >> s) {
    if (s == "PRINT") {
      h->Print();
    } else if (s == "TPROBES") {
      printf("%d\n", h->Total_Probes());
    } else if (s == "ADD") {
      if (cin >> s >> s2) {
        if (h->Find(s) != "") {
          printf("Key %s is already in the table\n", s.c_str());
        } else {
          h->Add_Hash(s, s2);
        }
      }
    } else if (s == "FIND") {
      if (cin >> s) {
        s2 = h->Find(s);
        if (s2 == "") {
          printf("Didn't find %s\n", s.c_str());
        } else {
          printf("%s %s\n", s.c_str(), s2.c_str());
        }
      }
    } else {
      cerr << "Commands are PRINT, FIND key, ADD key val, and TPROBES\n";
    }
  }
}


I am getting a seg fault in this function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
 long int count = 0;         // count variable
    int count2 = 6;        // 2nd count variable used to get last 7 of key
    int count3 = 0;       // 3rd count variable
    long int Xval = 0;       // value of XOR
    vector <string> temp; // vector of temperorary strings
    string Nval = " ";   // empty string

    if( Fxn == 0 )
    {
        temp.resize( 1 );       // resize temp
        if( key.size() > 7 )
        {
            temp[0] = key.substr( key.size() - 7, key.size() );
        }
        else
        {
            temp[0] = key;
        }
        count = strtol( temp[0].c_str(), NULL, 16 ) % nkeys;             // set count to int value of hex mod table size
        while( count < nkeys || keys[count] != key )
        {
            tmp++;
            if( Coll == 0 )
            {
                if( count <= nkeys )
                {
                    count++;
                }
            }
            else
            {
                temp.resize( (key.size()/7) + 1 );  // resize temp to number of groups of 7
                for( count2 = 0; count2 < temp.size(); count++ )
                {
                    if( count2 % 7 == 0 )
                    {
                          temp[count3] = key.substr( count2, count2 + 6 );
                        count3++;
                    }
                    Xval ^= strtol( temp[count2].c_str(), NULL, 16 );
                }
                Xval = Xval % nkeys;
                if( Xval > 0 )
                {
                    count += Xval;
                }
                else
                    count += 1;
            }
        }
        if( keys[count] == key )
        {
            return vals[count];     // return value if found
            Nval = "found";
        }
        else
        {
            return Nval;        // return empty string
        }
    }
    else
    {
        temp.resize( (key.size()/7) + 1 );  // resize temp to number of groups of 7
        for( count2 = 0; count2 < temp.size(); count++ )
        {
            if( count2 % 7 == 0 )
            {
                temp[count3] = key.substr( count2, count2 + 6 );
                count3++;
            }
            Xval ^= strtol( temp[count2].c_str(), NULL, 16 );
        }
 count = Xval % nkeys;        // calculate mod value
        while( keys[count] != key )
        {
            tmp++;
            if( tmp == nkeys )
            {
                break;
            }
            if( Coll == 0 )
            {
                count++;
            }
            else
            {
                temp.resize( 1 );       // resize temp
                if( key.size() > 7 )
                {
                    temp[0] = key.substr( key.size() - 7, key.size() );
                }
                else
                {
                    temp[0] = key;
                }
                count2 = strtol( temp[0].c_str(), NULL, 16 ) % nkeys;             // set count to int value of hex mod table size
                count2 = count2 % nkeys;
                if( count2 > 0 )
                {
                    count += count2;
                }
                else
                    count += 1;
            }
        }

        if( keys[count] == key )
        {
               return vals[count];     // return value if found
            Nval = "found";
        }
        else if( Nval == "NULL" )
        {
            return Nval;        // return empty string
        }
    }
}

any ideas on how to fix it. thanks
Topic archived. No new replies allowed.