[c++] Simple search with hashmap

[Kalashnikov.]

Ce este hashmap? Este o lista de obiecte, fiecare continand un identificator(key)+un atribut(ori mai multe), punctand inspre urmatoru obiect.

La o prima vedere acest lucru nu ne va facilita cautarea in cazul unor date 'neordonate'. Parcurgerea fiecarui element fiiind o pacoste in a descoperi elementul cautat.

Plecand de la ideea de hashmap, putem implementa ceva asemanator, oarecum ordonat(vom vedea in cateva minute de ce), cu timp de acces instant pentru a identifica cheia, si regasirea attributului dorit din obiectul dorit.

Vom porni de la ideea de a imparti informatiile in sub categorii ce se aseamana. Clasa vector reprezinta un intermediu usor in aplicarea acestei idei, din pricina faptului ca putem accesa orice element instant.

Elementul va fi in cazul de fata un 'tabel' (lista simpla de elemente, hashmap ul in sine).

Pentru a va familiariza cu ideea, priviti exemplul de mai jos.

#include <vector>
#include <string>

using namespace std;

typedef string TKey;
typedef string TAttribut;

struct Node {
	TKey key;
	TAttribut attr;
	Node *next;
};

struct Table {
	Node *head;
};

typedef vector<Table> HashMap;

Pentru a modifica o tabla, avem nevoie de a implementa cateva functii (intr-un fisier header 'abc.h')

// initializeaza lista la valoarea nullptr
void initTable(Table &t);
// verifica daca lista contine macar un nod
bool isEmpty(const Table & t);

// adauga ori modifica
// - adauga daca cheia cautata nu exista in lista
// - modifica atributul cheii corespunzatoare in caz ca exista
void addModify(const TKey &c, const TAttribut &a, Table &t);
// sterge o intrare din lista
void rem(const TKey &c, Table &t);
// intoarce valoarea atributului
bool getAttr(const TKey &c, const Table &t, TAttribut &a);

Iar in alt fisier 'abc.cpp' vom implementa aceste functii.

Initializarea si verificarea sunt simple.

#include "TableList.h"
#include <string>
using namespace std;

void initTable(Table & t) {
	t.head = nullptr;
}

bool isEmpty(const Table & t) {
	return t.head == nullptr;
}

Pentru a simplifica algoritmele, am implementat separat o functie care creeaza un nod cu parametrii specificati.

Node *createNode(const TKey &c, const TAttribut &a, Node *nP) {
	Node *tmp = new Node;
	tmp->key = c;
	tmp->attr = a;
	tmp->next = nP;
	return tmp;
}

Acum ca avem toate uneltele, putem implementa diferite concepte.

Primul este adaugarea ori modificarea unui element inexistent ori existent

Ce avem de facut, e sa navigam printre noduri si in momentul in care l-am gasit pe cel ce contine cheia cautata ori nu mai exista nici un alt nod de analizat iesim din bucla.

In cazul in care it (nod ul curent) nu este nullptr inseamna ca cea de a doua conditie (it->key == c) a fost indeplinita. In acest caz am desi sa modificam atributul.

Iar daca (it == nullptr), vom adauga on nod nou la inceputul listei.

void addModify(const TKey &c, const TAttribut &a, Table &t) {
	Node *it = t.head;
	while(it != nullptr && it->key != c)
       		it = it->next;

	if(it != nullptr)
		it->attr = a;
	else
		t.head = createNode(c, a, t.head);
}

Urmatoarea functie implementata este inlaturarea nodurilor dorite.

De aceasta data algoritmul este un pic mai complex. Faptul ca lucram cu liste simple, implica existenta unor exceptii ce trebuiesc luate in calcul.

In cazul in care nu avem nici un nod in lista (table), atunci nu facem nimic.

Daca avem macar un element, verificam daca cheia acestuia este aceea pe care o cautam. Aceasta exceptie este determinata de comportamentul listei, care din natura ei nu poate primi schimbari directe(gen eliberarea memoriei utilizate de acel nod) + reconectarea pointerului precedent cu cel ce urmeaza. Dar pentru ca avem un sens (next) putem sa luam o marja de un nod (inainte de cel dorit) si restructura mai usor lista stiind ca exista macar un next (chiar daca e reprezentat de nullptr), dupa nodul ce ne intereseaza.

La o anumita instanta a buclei(nodul 'n') vom descoperi ca nodul n+1 contine cheia cautata.

Vom inregistra intr-un nod temporar referinta catre (n+1), vom lega 'n' de 'n+2', si prin instructiunea 'delete' vom elibera memoria de la adresa specificata prin nodul temporar(fostul nod n+1).

void rem(const TKey &c, Table &t) {
	Node *it = t.head;
	if(it != nullptr) {
		if(it->key == c) {
			t.head = t.head->next;
			delete it;
		}else {
			while(it->next != nullptr && it->next->key != c)
				it = it->next;

			if(it->next != nullptr) {
				Node *n = it->next;
				it->next = it->next->next;
				delete n;
			}
		}
	}
}

Ceea ce ramane de facut este citirea informatiilor (atributelor) din acel nod.

bool getAttr(const TKey &c, const Table &t, TAttribut &a) {
    	Node *it = t.head;
	while(it != nullptr && it->key != c)
		it = it->next;

	if(it != nullptr) {
		a = it->attr;
		return true;
	}

	return false;
}

Revenind la 'abc.h' vom specifica si prototipele functiilor de hashmap

// initializarea unui hashmap, cat mai mare cu atat mai bine (nu exagerat, ci relativ volumului de informatii ce dorim sa stocam)
void initHashMap(vector<Table> &hm, unsigned sz);
// o functie ce va genera un index, specific cheii mentionate in parametru, si cat mai unic(tine de complexitatea algoritmului de triere a cheilor) 
unsigned getHash(string key, unsigned sz);

// verifica daca o cheie detine un nod in hashmap
bool keyInHashMap(const TKey &c, const HashMap &hm);

// adauga ori modifica la indexul corespunzator cheii
void addModify(const TKey &c, const TAttribut &a, HashMap &hm);
// sterge la indexul corespunzator cheii
void rem(const TKey &c, HashMap &hm);
// incarca atrbutul corespunzator hash ului, prin referinta 'a'
// intoarce 'true' in caz ca acel nod a fost gasit
// daca nu 'false'
bool getAttr(const TKey & c, const HashMap &hm, TAttribut & a);

Implementam si aceste functii in 'abc.cpp'

Cream hashmap de o marime (sa zicem 40000), si initializam fiecare lista.

A doua functie este aceea care va genera indexele specifice cheilor ( ceva simplu)

void initHashMap(HashMap &hm, unsigned sz) {
	hm.resize(sz);
	for(unsigned i=0; i<sz; ++i)
		initTable(hm[i]);
}

unsigned getHash(string key, unsigned sz) {
	if(s.empty())
		return sz;

	unsigned idh = 0;
	for(unsigned i=0; i<s.size(); ++i) {
		idh = 27*idh + int(s[i]);
		if(idh >= sz)
			idh %= sz;
	}
	return idh;
}

Pentru a cauta o cheie specifica intr-o tabla, mi-am luat libertatea de folosi recursivitatea.

bool cDHM_rec(const TKey &c, Node *n) {
	if(n == nullptr)
		return false;

	if(c == n->key)
		return true;

	return cDHM_rec(c, n->next);
}

Functiile ce urmeaza au un lucru in comun, si anume :

	unsigned id_hash = getHash(c, hm.size());
	if(id_hash != hm.size())

Identificam indexul tablei in care acea cheie ar trebui sa se regaseasca,

si aplicam o functie specifica tablei.

bool keyInHashMap(const TKey &c, const HashMap &hm) {
	unsigned id_hash = getHash(c, hm.size());
	if(id_hash != hm.size())
		return cDHM_rec(c, hm[id_hash].head);

	return false;
}

void addModify(const TKey &c, const TAttribut &a, HashMap &hm) {
	unsigned id_hash = getHash(c, hm.size());
	if(id_hash != hm.size())
		addModify(c, a, hm[id_hash]);
}

void rem(const TKey &c, HashMap &hm) {
	unsigned id_hash = getHash(c, hm.size());
	if(id_hash != hm.size())
		rem(c, hm[id_hash]);
}

bool getAttr(const TKey & c, const HashMap &hm, TAttribut & a) {
	unsigned id_hash = getHash(c, hm.size());
	if(id_hash != hm.size())
		return getAttr(c, hm[id_hash], a);

	return false
}

Cateva alternative a listelor simple, pot fi listele dublu inlantuite ori arbori binari de cautare(dar trebuiesc echilibrati mai mereu).

autor: noVaLue

Sursa: Simple search with hashmap