Словари - EcsFlash/DataTypes GitHub Wiki

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

При необходимости, словарь расширяется (в нашем случае если длина словаря составляет 2/3 от его вместимости)
Высчитывается хеш для КЛЮЧА, от данного хэша берется остаток от деления на вместимость словаря(ровно так же мы делали в хеш таблицах)
Полученное значение - индекс цепочки/ячейки в хеш таблицы.
Возможные коллизии разрешаются в соответствии выбранным методом.
В ячейку/начало цепочки помещается пара ключ-значение.
Длина словаря увеличивается на 1.

При считывании значения/удалении пары ключ-значение со словаря происходит следующее:

Высчитывается хеш для КЛЮЧА, от данного хэша берется остаток от деления на вместимость словаря(ровно так же мы делали в хеш таблицах)
Полученное значение - индекс цепочки/ячейки в хеш таблицы.
Возможные коллизии разрешаются в соответствии выбранным методом.
Возвращается найденное значение/удаляется пара ключ-значение

Рассмотрим устройство нашего словаря на методе цепочек:

Примечание: я везде буду использовать встроенный метод подсчета хеша для ключа, так как писать функцию самому - хуйня а не затея.

Общий вид:

Сам узел словаря:

struct Node {
	K key;
	V data;
	Node* next;
	Node() {
		key = K();
		data = V();
		next = nullptr;
	}
	Node(const K& _key, const V& _data) {
		key = _key;
		data = _data;
		next = nullptr;
	}
};

Расширение словаря:

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 = hash<K>()(temp->key);
				int hash = abs(h % (SIZE * 2));
				addToHead(tmp[hash], temp->key, temp->data);
				temp = temp->next;
			}
		}
	}
	for (int i = 0; i < SIZE / 2; i++) {
		if (table[i]) {
			clear(table[i]);
		}
	}
	SIZE *= 2;

	delete[] table;
	table = tmp;
}

Вставка пары ключ-значение в словарь:

void insert(const K& key, const V& value) {
	if (amount * 3 > SIZE * 2) {
		resize();
	}
	long long h = hash<K>()(key);
	int _hash = abs(h % SIZE);
	addToHead(table[_hash], key, value);
	amount++;
}
void addToHead(Node*& head, const K& key, const V& elem) {
	Node* newEl = new Node(key, elem);
	newEl->next = head;
	head = newEl;
}

Поиск ключа в словаре:

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

Примечание: search_pos используется для поиска пары ключ-значение в цепочке, и может вернуть либо последний элемент цепочки(что означает что в цепочке нет пары с заданным ключом) либо элемент перед необходимой парой

Удаление из словаря:

bool remove(const K& key) {
	long long h = hash<K>()(key);
	int _hash = abs(h % SIZE);
	if (!table[_hash]) {
		return false;
	}
	else {
		if (table[_hash]->key == key) {
			deleteFromHead(table[_hash]);
			amount--;
			return true;
		}
		else {
			Node* p = search_pos(table[_hash], key);
			if (p->next != nullptr) {
				deleteAfter(p);
				amount--;
				return true;
			}
			else {
				return false;
			}
		}
	}
}