利用hash fuction 写好的函数，如何将时间复杂度降到最低！！！请大神回答。
#include <iostream> // for cin & cout
#include <fstream> // for file i/o
#include <cstdlib> // for exit() function
#include <string>
using namespace std;
// total codes in AirportCodes.txt is 3589
const int NumberOfAirportCodes = 100;
// holds airport codes and cities
struct AirportCode {
string code;
string city;
} temp;
class AirportCodeHash {
public:
AirportCodeHash(int size) {
hashTableSize = size;
HashTable = new AirportCode[size];
}
~AirportCodeHash() {
delete [] HashTable;
}
int hashFunction(string code) {
/*long hash=0;
for(int i =0;i<hashTableSize;i++)
hash=code[1] + (hash<<6)+(hash<<16)-hash;
return hash;*/
return code[0]*code[1]*code[2]*26; //原来是return 0；
}
void insert(AirportCode ac) {
int hash = hashFunction(ac.code);
for(int i = 0; i < hashTableSize; i++) {
// find a place to insert the code
if((HashTable[(i + hash) % hashTableSize].code).empty()) {
HashTable[(i + hash) % hashTableSize].code = ac.code;
HashTable[(i + hash) % hashTableSize].city = ac.city;
break;
}
}
}
// find a city in the hash table ans determine the number of comparisons required
string findCity(string code, int & increment) {
int hash = hashFunction(code);
increment = 0;
while(true) {
if((HashTable[(increment + hash) % hashTableSize].code == code)) {
increment++;
return HashTable[(increment + hash) % hashTableSize].city;
}
increment++;
}
}
private:
// the hash table containing the airport codes
AirportCode * HashTable;
int hashTableSize;
};
int main() {
AirportCodeHash MyHashTable(int(NumberOfAirportCodes / 0.75)); // load factor of 0.75 在0.75不变的前提下
char buffer[256];
// input from file FAA.txt
ifstream inputFile( "c:\\AirportCodes.txt", ios::in);
// check if input file is accessable
if( !inputFile ) {
cerr << "input file cound not be opened" << endl;
exit(1); // exit gracefully with return code of 1
}
// get the input and populate the hash teble
for(int i = 0; i < NumberOfAirportCodes; i++) {
inputFile >> temp.code;
inputFile.getline(buffer, 256);
temp.city = buffer;
MyHashTable.insert(temp);
}
// move to the beginning of the file
inputFile.seekg (0, ios::beg);
// get the input and populate the hash teble
int comparisonCount = 0, count;
for(int i = 0; i < NumberOfAirportCodes; i++) {
inputFile >> temp.code;
inputFile.getline(buffer, 256);
temp.city = buffer;
MyHashTable.findCity(temp.code, count);
comparisonCount += count;
}
cout << "Total Comparisons = " << comparisonCount << endl;
cout << "Average number of comparisons = " << (float) comparisonCount / NumberOfAirportCodes << endl;
inputFile.close();
return 0;
}
对文件进行查找，尽量降低时间复杂度，降到2以下最佳
AirportCodes.txt
http://pheatt.emporia.edu/courses/2012/cs345s12/MP10/AirportCodes.txt
[解决办法]
