• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Hashing

4
  • Publicat de Andrei Misarca
  • în C/C++
  • — 23 iul., 2009 at 12:58 pm

Am vrut sa scriu primul meu post despre STL, dar am renuntat intrucat nu aveam timpul si nervii necesari (nu faceam altceva decat sa traduc de prin alte parti). Asadar pentru a afla mai multe despre STL (care va putea fi folosit de la anul si la OJI) consultati http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary, http://www.sgi.com/tech/stl/ si mai sunt si altele. Daca aveti ceva intrebari puteti sa le puneti tot aici.

Hashingul (in engleza a toca) este foarte folositor in multe cazuri. Sa presupunem ca trebuie rezolvata urmatoarea aplicatie: Se da o lista cu N elemente (care poate fi de numere, stringuri sau orice altceva). Gasitit duplicatele din acea lista.

Un programator incepator ar cauta pentru fiecare element sa vada daca il mai gaseste in lista => complexitate O(N^2). Pentru N mai mic de 2000-3000 e ok, dar daca N ajunge pe la 10000 executia programului incepe sa dureze foarte mult.

Un programator mediu ar sorta elementele si le-ar compara cu vecinii din lista sortata => complexitate O(N*logN). Pentru N de cateva sute de mii treaba merge ok, dar daca N este de ordinul milioanelor, aplicatia iarasi dureaza foarte mult.

Un programator ceva mai experimentat ar folosi hash-urile pentru a rezolva aceasta problema. Sa presupunem ca toate elementele sunt numere naturale mai mici decat 1000. In acest caz se poate tine un sir de „vizitate”, care ia valoarea 1 sau 0 daca elementul a mai fost intalnit sau nu. Dar daca numerele depasesc 15-20 de milioane, nu se mai poate retine un astfel de sir. Pentru asta s-a „inventat” hashingul.

Nu pot retine un sir de cateva milioane sau miliarde, dar un sir de cateva sute de elemente se poate retine. Cum stim ca A mod B < B, oricat ar fi A, putem retine un sir de B elemente (B trebuie sa fie suficient de mic ca sa putem un sir de B elemente). Astfel putem verifica daca elementul a mai fost intalnitin sir verificand valoarea lui viz[A mod B].

Dar problemele apar cand numarul de elemente este mai mare decat B+1. Conform pricipiului lui Dirichlet, cel putin 2 elemente vor fi congruente modulo B. Aceasta situatie se numeste coliziune. Cum programatorii sunt niste oameni foarte descurcareti, au gasit si solutia acestei situatii. In loc de un sir de vizitate (care ia valori 1 sau 0, daca elementul a mai fost intalnit sau nu), pentru fiecare valoare de la 0 la B se retine o lista (vector) dinamica. Iar cand intalnesc o valoare A, o introduc in lista L[A mod B]. Iar in cazul in care vreau sa caut un element C, doar caut elementul C in lista L[C mod B].

Valoarea lui B trebuie aleasa astfel incat sa asiguram o distributie normala a valorilor modulo B. De aceea se prefera ca B sa fie un numar prim, si in niciun caz putere a lui 2. Cele mai utilizate sunt 666013 (multa lume are o preferinta pentru acest numar), 11677, si altele. Evident, exista mai multe metode de a „hashui” elementele, insa aceasta cu modulo este cea mai utilizata.

Pentru stringuri se procedeaza exact la fel, considerand fiecare litera ca pe un numar.

Astept evenetuale intrebari 😀

Etichete: hashinglistamodulovector

— Andrei Misarca a scris 13 articole

Nu există o descriere a autorului.

  • Articolul anterior Variabile, constante si expresii in C++/Pascal[2]
  • Articolul următor Yahoo! a cumparat compania Xoopit

4 Comentarii

  1. Avadanei Andrei spune:
    iulie 23, 2009 la 1:35 pm

    Eu in general pentru a evita coliziunile intre hash`uri folosesc lista simplu inlantuite! Mi se pare cea mai simpla implementare.

    Operatiile ce se pot face foarte rapid cu hashuri sunt :
    Adaugare element : O(1)
    Cauta element : O(k), k = numarul de coliziuni
    Sterge element(daca exista) : O(1) + O(k), k = numar de coliziuni.

    Daca numarul elementelor este mic(aproximativ 1000) si pastram un sir de „vizitate” atunci toate operatiile descrise mai sus se fac in O(1).

    Una din aplicabilitati este algoritmul lui Rabin-Karp ce il voi implementa curand,acum avand si baza teoretica pentru hashuri. 🙂

  2. Andrei Misarca spune:
    iulie 23, 2009 la 1:36 pm

    Defapt complexitatea pentru fiecare operatie se considera O(1), acel k fiind in general destul de mic

  3. Avadanei Andrei spune:
    iulie 23, 2009 la 2:01 pm

    Da in medie este O(1), insa cu exactitate e O(k), daca functia ce stabileste pozitia este proasta atunci acel k poate fi destul de mare.

    Spre exemplu :
    Vom avea numere intre 1 si 1 milion,iar functia de dispersie este : h(x) { return x % 2; } va dispera toate elementele in 0 si 1.In aceasta situatie in medie k va fi n/2 elemente daca numerele sunt random si practic cautarea si stergerea unui element va fi O(n/2).

    Pentr a avea o functie ce ofera cat mai putine coliziuni este indicat ca numarul ce face dispersia sa fie un numar cat mai indepartat de 2 puteri ale lui 2 si NICIODATA sa nu fie o putere a lui 2.

  4. Algoritmul Rabin-Karp pentru potrivirea sirurilor | WorldIT spune:
    octombrie 3, 2009 la 4:25 pm

    […] acestui algoritm consta in rezolvarea in timp liniar folosind algoritmul Rabin-Karp, ce are la baza hashuri.Acest algoritm are timpul de executie […]


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • februarie 2021
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Hashing
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons