Lamuriri articol hashing

[•wickedman]

http://infoarena.ro/hashing

de ce O(lg(lg(n)) ?

ps: revin cu detalii

[•domino]

Se scrie "hashing" Din articolul scris de Mihai Patrascu:

Abordarea clasica:
* func?ii euristice de hashing
* rezolvarea coliziunilor prin inlantuire sau adresare deschisa
* daca functia de hash ar fi perfect random, lungimea medie pt cea mai lunga lista inlantuita este O(lgN/lglgN)

O solu?ie practic?:
* avem dou? func?ii hash ?i dou? tabele în care rezolv?m coliziunile prin înl?n?uire
* când inser?m un element, îl ad?ug?m la tabela în care intr? într-un lan? mai scurt
* c?utarea se face în amândou? tabelele în loca?iile corespunz?toare
* lungimea medie a lan?ului maxim este O(lglgN)
* dac? men?inem lan?urile care arbori echilibra?i avem opera?ii în O(lglglgN)

[•wickedman]

Si de unde ies logaritmii astia?

Daca functia de hash e perfecta, nu ar trebui sa avem N/M lungime medie de lant?
Daca faci functie dubla de hash si cauti in ambele parti, statistic nu e acelasi lucru ca si cum ai avea un singur lant mai mare?

[•domino]

Nu, nu e acelasi lucru fiindca functiile de hash sunt diferite.

[•Cosmin]

O(log log n) e numaru maxim de chestii din cel mai mare bucket. E O(1) in cazul mediu da te intereseaza ca si cazu naspa sa nu fie asa naspa. Parca in cazul normal bucketu maxim are O(log n), da nu mai stiu exact.

[•blasterz]

Eu am folosit un hash... destul de interesant si performant... Acum nu stiu cat de corect e... desi la problema loto (singura problema la care
am testat metoda) am luat 100.

fac asa:

Cod:

#define maxn 128123
#define maxlog 17

int H[maxn][maxlog];

inline void insert(int v) 
{
  H[v%maxn][v%maxlog]=v;
}

inline int find(int v)
{
  if(H[v%maxn][v%maxlog]==v)return 1;
  return 0;
}

inline void del(int v)  
{
  H[v%maxn][v%maxlog]=0;
}

Cele 3 operatii au complexitate O(1)
Daca stiti vreo problema la care nu functioneaza metoda asta va rog sa-mi spuneti!

[•Cosmin]

Mircea, mai sus era vorba de niste hashuri mai jmechere care merg mai rapid. In solutiile clasice si in solutia discutata de noi, complexitatea operatiilor in cazul mediu e O(1), dar noi discutam despre altceva. Este un articol care prezinta hashurile astea pe site si vorbeam de marimea medie a galetii celei mai umplute in acela hashuri.

[•blasterz]

Da am inteles ca vorbiti despre double hash... cand ai H1[maxn] si H2[maxn] si cand introduci un element, il pui in lista cu elemente mai putine... si am testat asta... dar sursa care am pus-o eu ruleaza de 3 ori mai repede...
pentru n=1 000 000 de insert si find a rulat in 0,1s pe un P4 3Ghz

[•Cosmin]

Ok, m-am uitat acum si la cod, si nu vad sa tratezi in vreun fel coliziunile, asa ca s-ar putea sa fie mai greu sa folosesti aceiasi metoda in toate problemele.

[•stef2n]

Discutia poate continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3687.0