0
我正在使用線性探測的簡單HashTable程序。使用重載打印HashTable時奇怪的輸出...？
HashTable包含我定義的Symbol類的對象。我剛剛寫完print（）函數，它遍歷對象的矢量，它可以工作......但是......它也偶爾將「0：1」附加到輸出。
我認爲這可能與在HashTable類中的Symbol類和HashEntry結構中的「< <」流操作符的重載有關。
我已經附加了我的LinearProbing.h，Driver.cpp，Symbol.h和我的輸出。
輸出：
: 0
: 1
address : 6
: 0
: 0
: 1
greeting : 6
: 0
max2 : 3
: 0
: 0
: 1
studentID : 1
: 0
count : 2
: 1
pi : 5
: 1
: 0
: 1
city : 6
: 0
debt : 5
: 0
name : 6
: 1
num : 2
: 0
myDouble : 5
: 1
: 0
: 1
gpa : 4
: 1
ID : 1
: 0
city : 6
: 1
: 0
: 1
: 0
: 1
: 0
: 1
max : 3
: 0
count : 2
: 0
ch2 : 0
: 0
myFloat : 4
: 0
county : 6
: 0
ch : 0
: 0
: 0
: 1
: 0
: 1
: 0
: 1
state : 6
: 0
: 0
: 1
myDouble : 5
: 0
name : 6
: 0
pi : 5
: 0
: 0
: 1
salary : 5
: 0
gdp : 5
: 0
: 0
: 1
: 0
: 1
gpa : 4
: 0
: 0
: 1
LinearProbing.h：
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include "Symbol.h"
using namespace std;
int nextPrime(int n);
bool isPrime(int n);
size_t hasher(const string & key);
template<typename string>
class thehash2
{
public:
size_t operator()(const string & key)
{
size_t hashVal = 0;
for(char ch : key)
hashVal = 37 * hashVal + ch;
return hashVal;
}
};
template<typename Symbol>
class thehash
{
public:
size_t operator()(const Symbol & item)
{
static thehash2<string> hf;
return hf(item.getData());
}
};
template<typename HashedObj>
class HashTable
{
public:
explicit HashTable(int TABLE_SIZE)
{
currentSize = 0;
array.resize(TABLE_SIZE);
}
void makeEmpty()
{
currentSize = 0;
for(int i = 0; i < array.size(); i++)
array[i].info = EMPTY;
}
bool contains(const HashedObj & x) const
{
return isActive(findPos(x));
}
bool insert(const HashedObj & x)
{
int currentPos = findPos(x);
if(isActive(currentPos))
return false;
array[currentPos] = HashEntry(x, ACTIVE);
if(++currentSize > array.size()/2)
rehash();
return true;
}
bool remove(const HashedObj & x)
{
int currentPos = findPos(x);
if(!isActive(currentPos))
return false;
array[currentPos].info = DELETED;
return true;
}
void print()
{
typename vector<HashEntry>::iterator vIter = array.begin();
while(vIter != array.end())
{
cout << *vIter << "\n";
++vIter;
}
}
enum EntryType{ ACTIVE, EMPTY, DELETED };
private:
struct HashEntry
{
HashedObj element;
EntryType info;
HashEntry(const HashedObj & e = HashedObj(), EntryType i = EMPTY) : element(e), info(i) {}
friend ostream & operator <<(ostream & os, HashEntry & hashentry) //overloaded to print out the the HashTable
{
HashedObj Element = hashentry.element;
EntryType Info = hashentry.info;
os << Element << " : " << Info << endl;
return os;
}
};
vector<HashEntry> array;
int currentSize;
bool isActive(int currentPos) const
{
return array[currentPos].info == ACTIVE;
}
int findPos(const HashedObj & x) const
{
int offset = 1;
int currentPos = myhash(x);
while(array[currentPos].info != EMPTY && array[currentPos].element != x)
{
currentPos += offset;
offset +=2;
if(currentPos >= array.size())
{
currentPos -= array.size();
}
}
return currentPos;
}
void rehash()
{
vector<HashEntry> oldArray = array;
array.resize(nextPrime(2*oldArray.size()));
for(int j = 0; j < array.size(); j++)
array[j].info = EMPTY;
currentSize = 0;
for(int i = 0; i < oldArray.size(); i++)
if(oldArray[i].info == ACTIVE)
insert(oldArray[i].element);
}
int myhash(const HashedObj & x) const
{
static thehash<HashedObj> hf;
return hf(x) % array.size();
}
};
int nextPrime(int n)
{
if(n % 2 == 0)
{
++n;
}
for(; !isPrime(n); n += 2)
{
}
return n;
}
bool isPrime(int n)
{
if(n == 2 || n == 3)
return true;
if(n == 1 || n % 2 == 0)
return false;
for(int i = 3; i * i <= n; i += 2)
if(n % i == 0)
return false;
return true;
}
Symbol.h：
using namespace std;
class Symbol
{
private:
int type;
string data;
public:
const string & getData() const
{
return data;
}
int getType()
{
return type;
}
void setType(int Type)
{
type = Type;
}
void setData(string Data)
{
data = Data;
}
bool operator== (const Symbol & rhs) const
{
return getData() == rhs.getData();
}
bool operator!= (const Symbol & rhs) const
{
return !(*this == rhs);
}
friend ostream & operator <<(ostream & outstream, Symbol & symbol) //overloaded to print out the the HashTable
{
int num = symbol.getType();
string name = symbol.getData();
outstream << name << " : " << num << endl;
return outstream;
}
};
和... Driver.cpp：
#include <iostream>
#include <iomanip>
#include <cassert>
#include <fstream>
#include <string>
#include <vector>
#include <time.h>
#include <unistd.h>
#include <map>
#include <cstdlib>
#include <cmath>
#include "LinearProbing.h"
using namespace std;
int TABLE_SIZE; //I know it's a global, but it allows the Table Size to be taken in within main() and used in hash()
size_t hasher(const string & key);
int main()
{
Symbol temp;
vector<Symbol> symbols;
string s;
int t;
int hash_key_array[TABLE_SIZE]; //array to hold hash key values
ifstream file;
file.open("symbols.txt");
cout << "Opening file..." << endl;
usleep(1000000);
if(!file)
{
cout << "System failed to open file.";
}
else
{
cout << "File successfully opened" << endl;
}
//for loop to read in the string name and the integer that follows the string name from symbols.txt
while(file >> s)
{
temp.setData(s);
file >> t;
temp.setType(t);
symbols.push_back(temp);
}
for(int i = 0; i < TABLE_SIZE; i++)
{
cout << symbols[i].getData() << "\n";
cout << symbols[i].getType() << "\n";
}
cout << "What would you like the table size to be?" << endl;
cin >> TABLE_SIZE;
HashTable<Symbol> hashtable(TABLE_SIZE);
cout << endl;
for(int j = 0; j < TABLE_SIZE; j++)
{
temp.setData(symbols[j].getData());
//cout << temp.getData() << endl;
temp.setType(symbols[j].getType());
//cout << temp.getType() << endl;
cout << endl;
hashtable.insert(temp);
}
hashtable.print();
}
size_t hasher(const string & key)
{
size_t hashVal = 0;
for(char ch : key)
{
hashVal = 37 * hashVal + ch;
}
return labs(hashVal % TABLE_SIZE);
}