Таблицы, списки, две коллизии - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Тут мы рассмотрим реализацию хеш-таблицы на методе цепочек.

Суть

Каждая ячейка таблицы является односвязным списком. В случае возникновения коллизии элемент записывается в голову списка.

Структура узла

struct Node {
	T data;
	Node* next;
	Node() {
		data = T();
		next = nullptr;
	}
	Node(T _data) {
		data = _data;
		next = nullptr;
	}
};

С чем будем играться

Node** table;
int SIZE;
int amount;

Конструктор

HashTableWithList(int size) {
	SIZE = size;
	table = new Node*[size];
	for (int i = 0; i < SIZE; i++) {
		table[i] = nullptr;
	}
	amount = 0;
}

Деструктор

~HashTableWithList() {
	for (int i = 0; i < SIZE; i++) {
		clear(table[i]);
	}
	delete[] table;
};
void clear(Node*& node) {
	while (node) {
		deleteFromHead(node);
	}
}

Вставка элемента

void insert(const T& elem) {
	if (amount * 3 > SIZE * 2) {
		cout << "resi" << endl;
		resize();
	}
	long long h = elem.hash();
	int hash = h % SIZE;
	addToHead(table[hash], elem);
	amount++;
	cout << amount << endl;
}

Удаление элемента

bool remove(const T& elem) {
	int hash = elem.hash() % SIZE;
	if (!table[hash]) {
		return false;
	}
	else {
		if (table[hash]->data == elem) {
			deleteFromHead(table[hash]);
			amount--;
			return true;
		}
		else {
			Node* p = search_pos(table[hash], elem);
			if (p->next != nullptr) {
				deleteAfterNode(p);
				amount--;
				return true;
			}
			else {
				return false;
			}
		}
	}
}

я бы на самом деле кидался ошибками при попытке удалить несуществующий элемент, а не возвращал true/false.

Поиск элемента

bool search(const T& elem) {
	int hash = elem.hash() % SIZE;
	if (table[hash] == nullptr) {
		return false;
	}
	else {
		if (table[hash]->data == elem) {
			return true;
		}
		if (search_pos(table[hash], elem)->next != nullptr) {
			return true;
		}
		else {
			return false;
		}
	}
}
Node* search_pos(Node* head, const T& elem) {
	Node* cur = head;
	while (cur->next != nullptr && cur->next->data != elem) {
		cur = cur->next;
	}
	return cur;
}

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

void resize() {
	Node** tmp = new Node * [SIZE * 2];
	for (int i = 0; i < SIZE*2; i++) {
		tmp[i] = nullptr;
	}
	for (int i = 0; i < SIZE; i++) {
		if (table[i]) {
			Node* temp = table[i];
			while (temp) {
				long long h = temp->data.hash();
				int hash = h % (SIZE * 2);
				addToHead(tmp[hash], temp->data);
				temp = temp->next;
			}
		}
	}
	SIZE *= 2;
	delete[] table;
	table = tmp;
}