Un tânăr matematician din SUA a infirmat o teorie considerată invariabilă timp de 40 de ani

De fiecare dată când deschideți o listă de contacte pe telefon, căutați un produs într-un magazin online sau verificați e-mailul, structurile speciale de date - tabelele hash - ajută la recuperarea rapidă a informațiilor de care ai nevoie. Datorită acestora, Internetul modern funcționează, de fapt, așa cum ne-am obișnuit. Dar se credea că tabelele hash au o limită. Descoperirea accidentală a unui tânăr doctorand, Andrew Krapivin, a răsturnat percepția asupra capacităților acestui instrument. Ilia Kabanov, jurnalist științific și autor al canalului de Telegram Lifelong Flours, explică cum funcționează tabelele hash, semnificația succesului lui Krapivin și dacă acesta va afecta eficiența manipulării datelor în viitor, relatează meduza.io.

Mai întâi, puțin mai multe despre ce sunt tabelele hash și de ce sunt necesare

Un tabel hash este o structură de date, adică un mod de organizare și stocare a informațiilor care ajută la accesarea și modificarea eficientă a datelor. Tabelele hash stochează perechi cheie-valoare și permit efectuarea de operațiuni asupra acestora: adăugarea de perechi noi, ștergerea celor existente și căutarea unei valori după cheie.

Acestea utilizează funcții hash, transformări care calculează un index care indică locația datelor în matrice. Atunci când un utilizator dorește să găsească ceva într-un tabel hash, sistemul nu parcurge întregul set de date, ci găsește imediat valoarea corectă pe baza indicelui calculat, accelerând considerabil căutarea.

Poate cel mai simplu analog al unui tabel hash în lumea reală este o bibliotecă, în care fiecare carte este stocată într-un anumit loc pe un raft, marcată cu un număr de identificare (cheie). În loc să caute o carte în întreaga colecție a bibliotecii, cititorul trebuie doar să consulte catalogul (funcția hash), care calculează locația exactă (index) a volumului dorit pe raft.

Funcția hash distribuie datele uniform în tabel, reducând la minimum probabilitatea ca mai multe elemente să ajungă în aceeași celulă și să creeze coliziuni. Din acest motiv, tabelele hash au devenit populare în serviciile moderne de Internet, utilizatorii nu doresc să petreacă timp suplimentar așteptând în timp ce sistemul caută prin datele din baza de date.

Problema este că eficiența tabelului depinde de gradul său de umplere - raportul dintre numărul de elemente stocate și dimensiunea matricei. Atunci când tabelul devine mai plin, numărul de posibile coliziuni crește și pot fi necesare mai multe etape pentru căutare.

De ce, înainte de descoperirea lui Krapivin, se credea că performanța tabelelor hash își atinsese limita

În tabelele hash cu adresare deschisă, una dintre cele mai comune două varietăți de tabele hash (cealaltă este utilizarea listelor), datele sunt stocate direct într-o matrice de celule. Fiecare celulă poate fi goală sau poate conține o anumită cheie. Atunci când trebuie introdusă o nouă cheie, se utilizează o secvență de funcții hash pentru a determina pozițiile posibile în matrice pentru plasarea acesteia.

Sarcina este de a utiliza funcțiile hash pentru a găsi o celulă goală. Numărul de pași necesari pentru a face acest lucru se numește complexitatea căutării. De fapt, aceasta este cea care determină viteza operațiunilor cu tabele hash.

Scopul dezvoltatorilor este de a reduce complexitatea căutării, în special atunci când tabelul este aproape complet umplut. În termeni simpli, am defini plinătatea în procente, să spunem că tabelul este plin în proporție de 50% sau 80%. La rândul lor, cercetătorii folosesc valoarea lui x pentru a indica cât de aproape este tabelul de 100% plin. Dacă x este egal cu 100, masa este plină în proporție de 99%, iar dacă x este egal cu 1.000, este plină în proporție de 99,9%.

În lucrarea sa din 1985, informaticianul Andrew Yao, care a câștigat ulterior premiul Turing, a demonstrat că pentru tabelele hash cu adresare deschisă, cel mai bun mod de a găsi un element sau o celulă goală este de a căuta aleatoriu printre locațiile posibile. Această abordare se numește hashing universal. Yao a sugerat, de asemenea, că în cel mai rău caz, atunci când trebuie găsită ultima celulă liberă, nu există nicio modalitate de a evita costul de timp proporțional cu x. Dacă tabelul hash este plin în proporție de 99%, ar trebui probabil să se verifice aproximativ 100 de poziții diferite pentru a găsi o celulă liberă.

Timp de patru decenii, majoritatea cercetătorilor au crezut că ipoteza lui Yao descrie cu exactitate realitatea. Însă în ianuarie 2025, Andrew Krapivin, un tânăr doctorand de la Universitatea Cambridge, împreună cu câțiva colegi, a demonstrat că clasicistul se înșela, iar comunitatea științifică trecuse cu vederea faptul că tabelele hash puteau fi făcute și mai eficiente.

Ce anume a reușit să demonstreze Krapivin și de ce descoperirea a fost fortuită

La sfârșitul anului 2021, Andrew Krapivin, pe atunci student la Universitatea Rutgers (în prezentarea sa recentă, cercetătorul apare ca atare; în 2020, într-o conversație cu bunicul său care locuia în Ucraina, el se numea Andrei), a dat întâmplător peste o publicație despre reducerea dimensiunii pointerelor în memoria calculatoarelor. Câțiva ani mai târziu, el a revenit la articol, l-a recitit și și-a dat seama că este posibil ca pointerii să ocupe și mai puțină memorie. Cu toate acestea, pentru a face acest lucru, trebuie îmbunătățită însăși organizarea datelor către care vor îndrepta indicatorii.

Krapivin a acordat atenție tabelelor hash și în acest proces a creat în mod neașteptat noul său tip, care s-a dovedit a fi mult mai rapid. Tabelul său i-a permis să găsească elemente în mai puțin timp și cu mai puțin efort.

Studentul s-a adresat profesorului său, Martin Farah-Colton, care fusese coautor al unei lucrări despre indici. Profesorul era sceptic cu privire la idee: tabelele hash au fost cercetate în detaliu și s-ar părea că nu se poate spune nimic nou în acest domeniu. Dar când Farah-Colton l-a rugat pe colegul său William Kuzmal de la Universitatea Carnegie Mellon să verifice lucrarea lui Krapivin, și-a dat seama imediat că era vorba de o descoperire reală.

Kuzmal i-a spus lui Krapivin că nu doar a creat un nou tabel hash, ci a infirmat de fapt o ipoteză pe care nimeni nu o contestase timp de 40 de ani. Cel mai surprinzător este faptul că Krapivin pur și simplu nu știa despre munca lui Yao - poate de aceea nu a fost descurajat de înțelepciunea convențională.

Împreună cu Farah-Colton și Kuzmal, el (acum doctorand la Cambridge) a elaborat o lucrare în care descrie o metodă care găsește elemente mai rapid decât prin căutarea aleatorie, chiar și atunci când tabelul este aproape complet plin. Metoda lor nu numai că face căutarea mai rapidă, dar, de asemenea, caută datele într-un timp constant, indiferent de cât de plin este tabelul.

Deși este puțin probabil ca descoperirea să conducă la schimbări imediate, pe termen lung, metoda lui Krapivin și a colegilor săi ar putea accelera multe procese pe Internet. Cel puțin, ei vor inspira cercetări ulterioare. Sau, mai degrabă, au făcut-o deja: la scurt timp după publicarea lucrării lor, a fost publicată o altă lucrare care propunea un nou model pentru adaptarea dinamică a strategiei de căutare în funcție de celulele tabelului care sunt deja ocupate.

Acum ne puteți urmări și pe Telegram, Facebook și Instagram pentru a fi la curent cu ultimele știri.