Какие к черту таблицы и причем тут хеш‐функции - EcsFlash/DataTypes GitHub Wiki

Исходный код таблицы - тут Исходный код элемента - тут

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

class Item {
	int id;
	string name;
public:
	Item(int _id, string _name) {
		id = _id;
		name = _name;
	}
	Item() {
		id = 0;
		name = "";
	}
	Item(const Item& obj) {
		id = obj.id;
		name = obj.name;
	}
	Item& operator=(const Item& obj) {
		id = obj.id;
		name = obj.name;
		return *this;
	}
	long long hash() const {
		long long h = 0;
		for (int i = 0; i < name.length(); i++) {
			h += (int)name[i] * pow(23, i);
		}
		return h + id;
	}
	friend ostream& operator<<(ostream& os, const Item& obj) {
		return os << obj.name << " " << obj.id;
	}
};

Категорически важно чтобы у вашего класса были все необходимые конструкторы, операторы присваивания и тд. Также необходимо наличие конструкторов у ячейки нашей таблицы.(и у нашего класса и у ячейки должны быть минимум конструкторы по умолчанию, иначе да здравствует attemding to reference a deleted function Помня, что для зондирования мы должны знать статус/состояние ячейки, напишем:

enum Status {
	FREE, USED, DELETED
};

Опишем ячейку нашей таблицы:

struct Cell {
	Status status = FREE;
	T object;
	Cell() {
		status = FREE;
		object = T();
	}
	void clear() {
		status = DELETED;
	}
	void set(const T& obj) {
		object = obj;
		status = USED;
	}

};

Вот с каким набором параметров таблицы мы будем играться:

Cell* table;
int size;
int c;
int amount;

Разберем что к чему: table - сама наша таблица size - размер нашей таблицы c - шаг с которым будет производиться линейное пробирование amount - текущее количество элементов

Конструктор:

HashTable2(int _size, int _c) {
	if (_c == 0) {
		throw invalid_argument("c parameter must be not 0");
	}
	table = new Cell[_size];
	size = _size;
	c = _c;
	amount = 0;
}

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

Деструктор:

~HashTable2() {
	delete[] table;
}

Вставка элемента в таблицу:

void insert(const T& elem) {
	if (amount * 3 > size * 2) {
		resize();
	}
	insertToTable(table, elem);
	amount++;
}

Нужно не забывать расширять таблицу, если количество элементов в ней превышает 2/3 размера таблицы. Расширять будем в 2 раза, но про расширение потом. В красивой функции вставки мы используем менее красивую, но более занимательную функцию insertToTable. Заглянем в неё:

void insertToTable(Cell*& table, const T& elem) {
	long long h = elem.hash() % size;
	if (table[h].status != USED) {
		table[h].set(elem);
	}
	else {
		int i = 0;
		int hash_i = hash(i, h);
		while (table[hash_i].status == USED) {
			i++;
			hash_i = hash(i, h);
		}
		table[hash_i].set(elem);
	}
}

Зачем передавать в функцию таблицу, до которой и так можно дотянутся? Ответ прост - при расширении таблицы нам потребуется перебросить элементы из старой таблицы в новую, причем не просто new_table[i] = old_table[i] а так, чтобы хоть немного снизить уровень кластеризации данных. Раз заговорили про расширение таблицы, заглянем в функцию расширения.

Расширение таблицы

void resize() {
	Cell* tmp = new Cell[size * 2];
	int _size = size;
	size *= 2;
	for (int i = 0; i < _size; i++) {
		if (table[i].status == USED) {
			insertToTable(tmp, table[i].object);
		}
	}
	delete[] table;
	table = tmp;
}

Функция ре-хеширования(черт его знает как правильно её обозвать)

Так как мы создавали хеш-таблицу с линейной пробацией, то наша функция выглядит так:

int hash(int i, long long h) {
	return (h + i * c) % size;
}

то есть она возвращает число в пределах размера нашей таблицы с линейным сдвигом на i*c ячеек от начального 'индекса'. если бы пробирование было квадратичным, функция выглядела бы как-то так:

int hash_power2(int i, long long) {
	return (h + i * c + i * i * d) % size;
}

а где-то функцию для квадратичной пробы пишут так:

int hash_power2_other(int i, long long) {
	return (h + (i*i*c*c)) % size;
}

Вообщем то, не суть важно.

Функция поиска элемента

int indexOf(const T& elem) {
	long long true_hash = elem.hash();
	long long hash = true_hash % size;
	int i = 0;
	int hash_i = hash;
	while (table[hash_i].status != FREE) {
		if (table[hash_i].status == USED) {
			if (table[hash_i].object == elem) {
				return hash_i;
			}
		}
		i++;
		hash_i = hash(i, hash_i);
	}
	return -1;
}
bool search(const T& elem) {
	if (indexOF(elem) != -1)
	{
		return true;
	}
	return false;
};

Функция удаления элемента

void remove(const T& elem) {
	int index = indexOf(elem);
	if (index != -1) {
		table[index].clear();
		amount--;
	}
}