Hashtable

Buna ziua

Ati vazut cat de usoara si rapida este cautarea intr-un vector dupa indice: a[1], a[3000] ...
Ce ne facem insa daca vrem sa cautam dupa un sir de caractere, de exemplu a["blabla"] ?
Va prezint pentru asta un hashtable. Cautarea este foarta rapida si aproape independenta de numarul de inregistrari. Totodata este case-insensitive.

Orice critica e bine venita.
Arhiva contine si un program de test.

Interesant, bine gandit si util. Felicitari.

L-am testat si eu . E ok clasa si din cate vad, merge cam la fel ca aceea din std ( map cred ca se numeste ) ... Bravo  

Critica :

- cel mai grav, din punctul meu de vedere - nu are documentatie...
- nu are unit teste - nu poti dovedi cat e de fiabil. Unit testele constituie si o buna documentatie la o adica.
- nu are un fel de insertOrChange() (put() ii zice in HashMap-ul din Java) - nu tot timpul cand ai ceva de pus in hashtable stii daca e sau nu deja introdus, si poate nici nu te intereseaza.

N-as folosi in nici un caz aceasta clasa in productie fara documentatie si unit teste...

Am gasit si vreo doua buguri (vezi, daca n-ai unit teste... ):

	cls1::hashtable<string> htb13("");
	htb13.insert("key1", "val1");
	htb13.insert("key2", "val2");

	cout << "bug 1:" << endl;
	cout << "current = " << htb13.current().key << "; " <<  htb13.current().value << endl;
	htb13.move_next();
	cout << "current = " << htb13.current().key << "; " <<  htb13.current().value << endl;
	htb13.move_next();
	cout << "current = " << htb13.current().key << "; " <<  htb13.current().value << endl;

// aici crapa prima data, move_next() dereferentiaza ceva pointer NULL (cred).
	htb13.move_next();


// aici ai a doua problema (comenteaza codul de deasupra ca sa treaca de prima):

	cout << "bug 2:" << endl;

	htb13.begin();
	htb13.removeall();

// surprise! 
	cout << "current = " << htb13.current().key << "; " <<  htb13.current().value << endl;

// daca nu mai faci move_next() ca sa crape, nici n-ai zice ca tocmai ai facut removeall()...

	htb13.move_next();
	cout << "current = " << htb13.current().key << "; " <<  htb13.current().value << endl;
	htb13.move_next();
	cout << "current = " << htb13.current().key << "; " <<  htb13.current().value << endl;
	htb13.move_next();

spor

Edited by sapho, 06 October 2008 - 20:11.

Ms mult pentru pareri in special sapho
Am reparat cele doua bug'uri si am adaugat si changeorinsert

Documentia va urma

Nu m-am uitat pe cod, dar e reentrant/thread safe?

Sper sa nu te deranjeze, dar am si eu cateva obiectii/pareri:
- codul e un pic dezordonat;
- insertOrChange() sugerata de cineva e de fapt functia de inserare, dar care nu esueaza daca exista deja cheia in hashtable; nu cred ca are rost sa existe doua functii pentru chestia asta;
- un hashtable are doi parametri, capacitate maxima si gradul de umplere; fiind o clasa generica, fara un scop anumit si exact, ambii ar trebui sa poata fi modificati (cu valori default alese cu grija); capacitatea maxima e de obicei un numar prim; gradul de umplere default se alege in functie de metoda de hash pe care o folosesti; cand se ajunge la gradul de umplere, se mareste capacitatea la urmatorul numar prim si se face rehash la tot tabelul;
- in loc de begin(), move_next(), operator++(), eof(), poti sa faci un iterator;
- daca dupa begin() tabelul este modificat, mai ai garantia ca te poti baza pe valoarea curenta? Daca tot s-a adus vorba de Java, implementarile din Java si C# invalideaza iteratorul daca se modifica tabelul;
- ar trebui sa faci niste teste sa vezi cat de "imprastiate" sunt cheile sau cum se distribuie in tabel;
- ar trebui sa faci niste teste sa vezi daca get/put bat spre timp constant.

Quote

Nu am verificat inca.

johnnyl, on Oct 8 2008, 15:09, said:

dani.user, on Oct 10 2008, 16:59, said:

La teste cu 1 mil/10 mil de chei, de acord, timpii pot parea OK, dar nu ai cu ce sa-i compari ca sa vezi daca sunt liniari sau nu. In loc de timpul efectiv, incearca sa numeri operatiile (cate chei se verifica pana este gasita aia pe care o cauti). De aici iti poti face si o idee despre distributie. Timpul efectiv nu inseamna mare lucru. Mai ales ca la implementarea actuala cu siguranta este O(n) nu constant, pentru ca nu creste capacitatea maxima a tabelului.

Ok, mersi de sugestie.
Cand am zis 10, ma refer la 10 nu 10 milioane

Update major
- Am rescris o parte din cod; acuma e mai "frumos" si usor de urmarit/inteles
- Am invatat cum sa fac un iterator

Am reparat un memory leak.

Cum s-a creat noul subforum Articole si cod sursa, cred ca acest topic s-ar potrivi acolo