HashTable.2.cpp

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

struct HashNode;
int Insert(vector<HashNode> *&table, HashNode elem);
typedef unsigned int int_t;
struct HashNode {
	HashNode(const string &temp = "") : now(0) {
		this->str = temp;
	}
	string str;

	int now;
#define IN_USE 1
#define DELETED 2
#define CLEAR 0
};

//(c) Vatulin.A
int HashFunc1(const string &temp) {
	size_t c = 12343;
	size_t a = 31247;
	size_t b = 42589;

	size_t value = c;
	size_t multiplier = 1;
	for (size_t i = 0; i < temp.size(); ++i) {
		value += temp[i] * multiplier;
		value = value % b;

		multiplier = (multiplier * a) % b;
	}

	return value % b;
}

int HashFunc2(const string &temp) {

	size_t c = 12343;
	size_t a = 31247;
	size_t b = 42589;

	size_t value = c;
	size_t multiplier = 1;
	for (size_t i = 0; i < temp.size(); ++i) {
		value += temp[i] * multiplier;
		value = value % b;

		multiplier = (multiplier + a) % b;
	}

	return value % b;
}
//(c) end

size_t Hash(const string &temp, int_t i, int_t M) {
	return (HashFunc1(temp) + i*HashFunc2(temp)) % M;
}

void Resize(vector<HashNode> *&table) {
	vector<HashNode> *newtable = new vector<HashNode>(table->size() * 2);
	for (int_t i = 0; i < table->size(); ++i) {
		if ((*table)[i].now == IN_USE)
			Insert(newtable, (*table)[i]);
	}
	delete table;
	table = newtable;
}

inline int_t Find(vector<HashNode> *&table, const string &temp) {
	for (int_t i = 0; i < table->size(); ++i) {
		int j = Hash(temp, i, table->size());
		if ((*table)[j].now == CLEAR)
			return -1;
		if ((*table)[j].now == IN_USE && (*table)[j].str == temp)
			return j;
	}

	return -1;
}

int Insert(vector<HashNode> *&table, HashNode elem) {
	if (Find(table,elem.str) != -1)
		return -1;
	for (int_t i = 0; i < table->size(); ++i) {
		int j = Hash(elem.str, i, table->size());
		if ((*table)[j].now == CLEAR || (*table)[j].now == DELETED) {
			(*table)[j] = elem;
			(*table)[j].now = IN_USE;
			return j;
		}
		if ((*table)[j].str == elem.str)
			return -1;
	}

	Resize(table);
	return Insert(table, elem);
}

bool Delete(vector<HashNode> *&table, const string &temp) {
	int_t pos = Find(table, temp);
	if(pos == -1)
		return false;
	(*table)[pos].now = DELETED;
	return true;
}

int main() {
	vector<HashNode> *table = new vector<HashNode>(2);
	string temp, type;
	while(1) {
		cin >> type>> temp;
		cin.ignore();
		if (type == "?") 
			printf("%s", Find(table, temp)!=-1 ? "OK\n" : "FAIL\n");
		else if (type == "+") 
			printf("%s", Insert(table, HashNode(temp))!=-1 ? "OK\n" : "FAIL\n");
		else if (type == "-") 
			printf("%s", Delete(table, temp) ? "OK\n" : "FAIL\n");
	}

	return 0;
}