Hash table question

[calvinfornia]

Hi, everyone. I'm working on a hash table program, but while I run it, the windows just ended with "Process exited after 2.92 seconds with return value 3221225477" without showing the correct result. I can't find what's wrong with my code.
Thanks a LOT for your help!!

//main.cpp
#include <iostream>
#include <fstream>
#include <ctime>
#include <chrono>
#include <cstdlib>
#include <vector>
#include "HashTable ver3.h"

using namespace std;

/**
class to evaluate time cost
*/
template <typename Timer = std::chrono::milliseconds>
struct measure
{
    template <typename F, typename... Args>
    static typename Timer::rep execution(F func, Args &&... args)
    {
        auto start = std::chrono::high_resolution_clock::now();
        func(std::forward<Args>(args)...);
        auto duration = std::chrono::duration_cast<Timer>(std::chrono::high_resolution_clock::now() - start);
        return duration.count();
    }
};

/**
function to be evaluated
*/
void EvaluateFunc(HashTable hashtable, vector<string> testCases)
{
    string gender;
    int height, weight;
    for (int i = 0; i < testCases.size(); i++)
    {
        gender = hashtable[testCases.back()].getGender();
        height = hashtable[testCases.back()].getHeight();
        weight = hashtable[testCases.back()].getWeight();
        testCases.pop_back();
    }
}


/**
Start main function
*/
int main()
{
    /** 
    HashTable is the class implemented by yourself, 5 member functions you need to implement as belows:
        1. addItem(key, gender, height, weight) : add data into your hash table
        2. operator[key]    : return item by selected key
        3. getGender()      : return gender by item
        4. getHeight()      : return height by item
        5. getWeight()      : return weight by item
    */
    HashTable hashtable;

    // for evaluation
    vector<string> testCases;

    // read data line by line
    std::ifstream infile("data.txt");
    string key, gender;
    int height, weight;


    while (infile >> key >> gender >> height >> weight)
    {
        hashtable.addItem(key, gender, height, weight);

        // collect evaluated test cases
        testCases.push_back(key);
    }
	
    /**
    basic test cases
    ANS:
    hashtable["0015239667"].getGender(): female
    hashtable["0015239667"].getHeight(): 160
    hashtable["0015239667"].getWeight(): 57
    */
    cout << "hashtable[\"0015239667\"].getGender(): " << hashtable["0015239667"].getGender() << endl;
    cout << "hashtable[\"0015239667\"].getHeight(): " << hashtable["0015239667"].getHeight() << endl;
    cout << "hashtable[\"0015239667\"].getWeight(): " << hashtable["0015239667"].getWeight() << endl;

    // Evauluate the speed of your hash table
    auto totalCost = measure<std::chrono::nanoseconds>::execution(EvaluateFunc, hashtable, testCases);
    cout << "Mean: " << totalCost / testCases.size() << " ns" << endl;

    return 0;
}

//HashTable ver3.h
#ifndef HASHTABLE ver3_H
#define HASHTABLE ver3_H

#include<vector>
#include"string.h"
using namespace std;

class Table_Items 
{

public:
	
	string key, gender;
	
	int height, weight;
	
	//Default constructor
	Table_Items();
	
	//Constructor
	Table_Items(string, string, int, int);
	
	//return gender by item
    string getGender();      
        
	//return height by item
	int getHeight();      
        
	//return weight by item
	int getWeight();   
};


class HashTable
{
	
public:
	
	//Hash function using quadratic probing
	int QuadraticProbing(string key, int i);
	
	
public:
	
	//Default constructor
	HashTable();
	
	//Destructor
	~HashTable();
	
	//add data into your hash table
	void addItem(string key, string gender, int height, int weight);
	    
    //return gender by item
    //string getGender();      
        
	//return height by item
	//int getHeight();      
        
	//return weight by item
	//int getWeight();      

    //return item by selected key
    Table_Items & operator [] (string key);	
    
private:
	
	//Number of slots in table
	static const int table_size = 10000;
	
	Table_Items patients_data[table_size];
	
	// Will hold table_arr status
	// (0 for Empty, 1 for there is data, -1 for deleted)
	int status_arr[table_size];
	
	//Number of elements stored in table 
	int count = 0;
	
};

#endif 

//HashTable ver3.cpp
#include<iostream>
#include<vector>
#include<sstream>
#include"HashTable ver3.h"
using namespace std;


/* Member functions of Table_items */

//Default constructor of Table_items
Table_Items::Table_Items()
:key(""), gender(""), height(0), weight(0)
{
	
};


//Copy constructor of Table_items
Table_Items::Table_Items(string Key, string Gender, int Height, int Weight)
:key("Key"), gender("Gender"), height(Height), weight(Weight)
{
	
};



/* Member functions of HashTable */

//Default constructor of Hashtable
HashTable::HashTable()
{
	for(int i = 0; i < table_size; i++)
	{
		patients_data[i].key    = "NULL";
		patients_data[i].gender = "NULL";
		patients_data[i].height = 0;
		patients_data[i].weight = 0;
	}

	for (int i = 0; i < table_size; i++)
	{
		status_arr[i] = 0;
	}
};


//Destructor of Hashtable
HashTable::~HashTable()
{
	//delete [] patients_data;
	//delete [] status_arr;
};


//Hash function 
int HashTable::QuadraticProbing(string key, int i)
{
	stringstream st;
	st << key;
	int Key;
	st >> Key;
	return ((int)( (Key % table_size) + 0.5*i + 0.5*i*i ) % table_size);
}


//Add item into Hashtable
void HashTable::addItem(string key, string gender, int height, int weight)
{
	int i = 0;
	while(i != table_size)
	{
		int j = QuadraticProbing(key, i);
		if( status_arr[j] == 0)
		{
			patients_data[j].key    = key;
			patients_data[j].gender = gender;
			patients_data[j].height = height;
			patients_data[j].weight = weight;
			count++;
			return;
		}
		else
		{
			i++;
		}
	}
	cout << "Hash Table Overflow !"<< endl;
};


//Return the gender of specific item
string Table_Items::getGender()
{
	return gender;
}; 


//Return the height of specific item
int Table_Items::getHeight()
{
	return height;
}; 


//Return the weight of specific item
int Table_Items::getWeight()
{
	return weight;
}; 


//Return item by selected key
Table_Items & HashTable::operator [] (string Key)
{	
	for(int i = 0; i< table_size; i++)
	{
		if(patients_data[i].key == Key)
		{
			return patients_data[i];
		}
	}
	
}

[salem c]

How about a sample data.txt to go along with that?

> https://stackoverflow.com/questions/24106139/process-exited-with-return-value-3221225477
Basically, your program crashed with a memory access violation.

Ordinarily, you would run the code in the debugger and let it catch the point of failure.

By that, it would be pointing you at an actual line of code, which would give you a lot more information than "it doesn't work".

[calvinfornia]

Here is a sample of data.txt, there are ten thousand data like below:

0050253839 female 155 43
0054203884 male 177 73
0076792815 female 178 71
0037780853 female 158 87
0024923679 male 160 44
.....

btw thanks a lot!!

[Repeater]

Is the file opening correctly? I suspect not.

 if (infile.is_open())
  {
    cout << "File successfully open";
  }
else
 {
  cout <<  "File not opened";
  }

I suspect that the input file is not in the correct place.

[calvinfornia]

I've added the above code in it, and the result is :
"File successfully open
--------------------------------
Process exited after 2.389 seconds with return value 3221225477"

[Repeater]

Your function HashTable::operator [] doesn't return anything sometimes. This is very very bad.

[calvinfornia]

I've just found a problem, which is in the function addItem, I should add this
status_arr[j] = 1;
before
return

Hence, the result will become :

Hash Table Overflow !
hashtable["0015239667"].getGender(): female
hashtable["0015239667"].getHeight(): 160
hashtable["0015239667"].getWeight(): 57
--------------------------------
Process exited after 2.583 seconds with return value 3221225477

The last line for calculating speed is missing.

[Repeater]

I suspect it's simply crashing when the evaluation function executes.

[calvinfornia]

So, how can I fix it ?
Thanks a lot!

[Repeater]

You could start by replacing main with this and making it work:

	HashTable hashtable;
	hashtable.addItem("A", "B", 1000, 2000);
	cout << hashtable["A"].getHeight() << endl;

        // Now one that doesn't exist
	cout << hashtable["Z"].getHeight() << endl;

[Repeater]

I also suspect the hash table copy, made for the function EvaluateFunc, is bad. I suspect the copy is not being made properly; you have not provided a constructor to do it so you get the default copy constructor.


If EvaluateFunc received the hash table by reference, the copy would not be necessary:
void EvaluateFunc(HashTable& hashtable, vector<string> testCases)

[calvinfornia]

I got the result after adding
return patients_data[0];
in the operator [] function.

hashtable["0015239667"].getGender(): female
hashtable["0015239667"].getHeight(): 160
hashtable["0015239667"].getWeight(): 57
Mean: 146511 ns

which is correct !!
Thanks a lot for that, and I'll think about some better way to do when key can't be find !!

[salem c]

This is what you should be doing.

1. Compile with maximum warnings and pay attention.

$ g++ -g -Wall -Wextra -std=c++11 foo.cpp
foo.cpp:90:33: warning: unused parameter ‘Key’ [-Wunused-parameter]
 Table_Items::Table_Items(string Key, string Gender, int Height, int Weight)
                                 ^
foo.cpp:90:45: warning: unused parameter ‘Gender’ [-Wunused-parameter]
 Table_Items::Table_Items(string Key, string Gender, int Height, int Weight)
                                             ^
foo.cpp: In member function ‘Table_Items& HashTable::operator[](std::__cxx11::string)’:
foo.cpp:194:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Yes, that "control reaches end of non-void function" is a doozy, as pointed out by Repeater earlier.

2. Run a simple test case in the debugger - again, listen to Repeater.

$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) run
Starting program: ./a.out 
1000

Program received signal SIGSEGV, Segmentation fault.
0x00000000004017c0 in Table_Items::getHeight (this=0x0) at foo.cpp:172
172		return height;
(gdb) bt
#0  0x00000000004017c0 in Table_Items::getHeight (this=0x0) at foo.cpp:172
#1  0x00000000004019fa in main () at foo.cpp:202
(gdb) up
#1  0x00000000004019fa in main () at foo.cpp:202
202		cout << hashtable["Z"].getHeight() << endl;
(gdb) 

SIGSEGV in Linux == STATUS_ACCESS_VIOLATION in Windows.

LOOK at the value of 'this' in your function. No valid this is ever NULL.
And the culprit? A lookup of a non-existent entry.

[Repeater]

Just for the sake of stating the law of C++ clearly; if your operator[] claims to return a Table_Items object, it MUST return one. You MUST come up with some sensible way of handling the case where a non-existent entry is requested.

[calvinfornia]

Got it !
Thanks very much for your help !!!

[jonnin]

ten thousand data like below:
in
over 2 seconds??
did you forget to compile with optimize? This seems crazy slow to me for so little data.

[Repeater]

While we're on the subject of how long it takes, I note that while the insertion is done by hashing the key to find the insertion location, the lookup is not done by hashing the key to find where to start looking; the lookup simply walks over the entire table from start to end, until it finds what its looking for. In the worst case, when the key is not present, the lookup examines every element in the table.

[jonnin]

Well that would do it. I didn't look at wall of code, just his output and his orig post which indicated a desire for speed. Which I am not sure he read, looking at it.. string processing is adding no speed..

A hash table solution is supposed to do this:
insert:
data-> key
table[key] = data;

and searching:
data = table[key]; //NO ITERATION HERE

where you may or may not need to handle collisions (2 datas, same key).

[dhayden]

To deal with hash collisions, you look for an empty slot in the hash table. Your table has 10000 buckets and you're inserting 10,000 items. As the table fills up, you have to search longer and longer distances to find an empty slot. I'm not certain, but I suspect this makes your insertion O(n²)

And as Repeater points out, your lookup is linear, so that's definitely O(n) and looking up all n items takes O(n²) time.

So you're doing 2 things that require O(n²) time with n=10000, so that's O(100,000,000) operations for each. Add to that the fact that so many parameters are being passed by value and you've got a slow moving program.

The point of a hash table is that the hash value should quickly lead you to the item. Choosing the next empty hash bucket to resolve collisions is okay, but only if the number of hash buckets is large compared to the number of items in the table. Otherwise it's more common for each bucket to contain a linked list of items.

So I think you should decide how you want to resolve collisions. Then we can help you fix the other issues.