Хеш таблица C++

[Last]

Сообщение от Jirogirg

Прошу прощения, а в какой момент мне нужно давать значение пункту none? В самом конструкторе наверное рано. Тогда в классе. А как можно задать каждому из 50-ти элементов полю none значение true?

В конструкторе.

[Jirogirg]

В конструкторе класса?

[Last]

Можно и в конструкторе структуры, ведь он будет вызываться перед конструктором класса.

[Jirogirg]

Сделал по нубски.
Инициализировал переменные в main через цикл

for (i=0;i<50;i++)
	{
		x.xesh[i].Key="";
		x.xesh[i].znach="";
		x.xesh[i].none=true;
	}

Прикол в том, что одну запись он добавить может, три тоже иногда (иногда вылетает винда с ошибкой.
Но вывести через GetKey он может только первое значение, если попросить второе или третье обязательно вылетает с ошибкой. В чём может быть проблема?
Переменные инициализировал, фунгкцию всю просмотрел, вроде никаких косяков нет, а прога не работает совсем.

[Last]

Какой-то неправильный подход.
Имхо, надо делать как-то так:

class Hash
{
private:
	string Key;
	string znach;
	bool none;
public:
        Hash () :  Key(""), znach(""), none(TRUE)//или FALSE, смотря что Вам нужно.
        {   }
        Hash (string k, string z, bool n) : Key(k), znach(z), none(n)
        {   }
	~Hash ();
	void AddKeyValue (string x, string y);
	void DelKey (string x);
	string GetKey (string x);
	
};

int main()
{
      Hash *table = new Hash [m];
        
}

Структуру я бы убрал вообще, зачем усложнять?

[Jirogirg]

Спасибо, попробую. А со структурой просто более понятно по мне так.
Тут получается два конструктора, да?
Но тогда получается, что теперь мне в каждой функции (добавление, удаление и поиск) на входе ещё запрашивать размер массива или вызывать эту функцию в цикле для каждого из m элементов массива. по-моему это неочень удобно или я могу чего-то непонимать.

[Last]

Сообщение от Jirogirg

Тут получается два конструктора, да?

Вообще говоря это две разных реализации одного интерфейса. Перегрузка конструктора. Читайте про перегрузку функций и полиморфизм.

Сообщение от Jirogirg

Но тогда получается, что теперь мне в каждой функции (добавление, удаление и поиск) на входе ещё запрашивать размер массива или вызывать эту функцию в цикле для каждого из m элементов массива. по-моему это неочень удобно или я могу чего-то непонимать.

Нет. В main можно объявить вектор из элементов класса.

vector<Hash> vHash; //объявляем вектор
vector<Hash>::nterator it; //объявляем итератор
for (it = vHash.begin(); it != vHash.end(); it++)
 /*здесь делаем всё что хотим с элементами вектора*/

[Jirogirg]

Фигась. Пойду про векторы почитаю, спасибо!

[Jirogirg]

Вобщем сказал мне преподаватель забыть о векторах. С той проблемой кое-как разобрались. Дал задание мне сделать тесты на супешные - добавление, удаление и поиск записей. Сделал. Но теперь надо сделать тест, при котором проверится быстродействие программы. Это тест, которые вызывает другие тесты. Дело в том, что нужен таймер, который мне будет выдавать время, чтобы я мог посчитать среднее. Преподаватель сказал, что лучше через time. Другие функции он сказал не трогать, так как некоторые работают на Винде, но не работают на Линуксе и наоборот. А я программирую дома на винде, а показываю прогу на Линуксе.
Вот собственно весь код:

#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <stdint.h>
#include <string>
#include <set>
#include <time.h>

using namespace std;

struct tab
{
	tab();
	string Key;
	string znach;
	bool none;
};

tab::tab()
{
	none=true;
}
#include <time.h>

class Hash
{
public:
	Hash ();
	tab xesh[50];
	void AddKeyValue (string x, string y);
	void DelKey (string x);
	string GetKey (string x);
	~Hash ();
};



void testcaseAdGet (string S1, string S2)
{	
	Hash x;
	x.AddKeyValue(S1, S2);
	if (x.GetKey(S1)==S2)
		cout<<"OK\n";
	else 
		cout<<"FAIL\n";
	return;
}

void testcaseAdDel (string S1, string S2)
{
	Hash x;
	x.AddKeyValue(S1, S2);
	x.DelKey(S1);
	if (x.GetKey(S1)=="no such key")
		cout<<"OK\n";
	else
		cout<<"FAIL\n";
	return;
}

int timetest ()
{
	Hash x;
	int i=0;
	string k,z;
	time_t start, finish;
	for (;i<25;i++)
	{
		char rand_buf[8];
		for (i = 0; i < 7; ++i)
			rand_buf[i] = 'A'+rand()%26;
		rand_buf[7]=0;
		k=(string)rand_buf;
		char rand_znach[4];
		for (i = 0; i < 3; ++i)
			rand_znach[i] = 'A'+rand()%26;
		rand_buf[3]=0;
		z=(string)rand_znach;
		x.AddKeyValue(k,z);
	}
	x.AddKeyValue("one", "Boris");
	x.AddKeyValue("two", "Petya");
	x.AddKeyValue("three", "senya");
	x.AddKeyValue("four", "Misha");
	x.AddKeyValue("five", "kolya");
	x.GetKey("one");
	x.GetKey("two");
	x.GetKey("three");
	x.GetKey("four");
	x.GetKey("five");
	finish=time_t;
	return (finish-start);
}



Hash::Hash()
{
}
Hash::~Hash()
{
}




uint_least32_t Crc32(unsigned char *buf, size_t len)
{
    uint_least32_t crc_table[256];
    uint_least32_t crc; int i, j; 
    for (i = 0; i < 256; i++)
    {
        crc = i;
        for (j = 0; j < 8; j++)
            crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
 
        crc_table[i] = crc;
    };
 
    crc = 0xFFFFFFFFUL;
 
    while (len--) 
        crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
 
    return crc ^ 0xFFFFFFFFUL;
}

void Hash::AddKeyValue (string x, string y)
{
	int s,m;
	unsigned i;
	i=Crc32 ((unsigned char *)x.c_str(), x.size());
	i=i%50;
	s=i;
	m=50;
	for (;i<m;i++)
	{
		if (xesh[i].none==true)
		{
			xesh[i].Key=x;
			xesh[i].znach=y;
			xesh[i].none=false;
			return;
		}
		if (i==50-1)
		{
			m=s;
			i=0;
		}
	}
}

void Hash::DelKey(string x)
{
	int s,m;
	unsigned i;
	i=Crc32 ((unsigned char *)x.c_str(),x.size());
	i=i%50;
	s=i;
	m=50;
	for (;i<m;i++)
	{
		if (xesh[i].Key==x)
		{
			xesh[i].none=true;
			return;
		}
		if (i==50-1)
		{
			m=s;
			i=0;
		}
	}
}

string Hash::GetKey(string x)
{
	int m,s;
	unsigned i;
	i=Crc32((unsigned char *)x.c_str(), x.size());
	i=i%50;
	s=i;
	m=50;
	for (;i<m;i++)
	{
		if ((xesh[i].none==false) && (xesh[i].Key==x))
			return xesh[i].znach;
		if (i==50-1)
		{
			m=s;
			i=0;
		}
	}
	return "no such key";
}
int main ()
{
	int i;
	testcaseAdGet("one", "Boris");
	testcaseAdGet("two", "Petya");
	testcaseAdGet("three", "senya");
	testcaseAdGet("four", "Misha");
	testcaseAdGet("five", "kolya");
	
	testcaseAdDel("one", "Boris");
	testcaseAdDel("two", "Petya");
	testcaseAdDel("three", "senya");
	testcaseAdDel("four", "Misha");
	testcaseAdDel("five", "kolya");

	
	scanf("%*c");
	return 0;
}

при компиляции пишет ошибку в функции timetest. Я неправильно присваиваю тип time переменным. Весь инет облазил нормальных примеров ну просто нет. Скажите, как это исправить?

[Jirogirg]

Херню написал... Нашёл про time_t немного. Испраивл timetest

int timetest ()
{
	Hash x;
	int i=0;
	string k,z;
	time_t start, finish;
	time_t time (time_t start);
	for (;i<25;i++)
	{
		char rand_buf[8];
		for (i = 0; i < 7; ++i)
			rand_buf[i] = 'A'+rand()%26;
		rand_buf[7]=0;
		k=(string)rand_buf;
		char rand_znach[4];
		for (i = 0; i < 3; ++i)
			rand_znach[i] = 'A'+rand()%26;
		rand_buf[3]=0;
		z=(string)rand_znach;
		x.AddKeyValue(k,z);
	}
	x.AddKeyValue("one", "Boris");
	x.AddKeyValue("two", "Petya");
	x.AddKeyValue("three", "senya");
	x.AddKeyValue("four", "Misha");
	x.AddKeyValue("five", "kolya");
	x.GetKey("one");
	x.GetKey("two");
	x.GetKey("three");
	x.GetKey("four");
	x.GetKey("five");
	time_t time (time_t finish);
	return (finish-start);
	 
}

Всё компилится, но программа зависает при вызове..