La relatia de echivalenta ar mai trebui adaugate si toate sirurile permutari ale lui S2 , nu ?
adica... Si ~ Sj <=> |Hash[p]| pentru sirul "i" = |Hash[p]| pentru sirul "j" ( unde 0 <= p < M-1 )
// Am putea sa definim si sa luma siruri echivalente inclusiv pe acelea care pentru care lungimile lanturilor din tabela ( Hash ) sunt egale pentru o anumita permutare a acestora . Cred insa ca acesta clauza duce demonstratia pe un drum mai greoi.
Plecand de la ideea ta : Este necesar si suficient sa luam numai sirurile de lungime N a caror elemente se gasesec in interiorul valorilor 0 M-1 ca si multime de reprezentanti a numerelor pentru generarea multimii factor data de relatia de echivalenta mai sus precizata .
Numarul total de de echivalente ( marimea multimii cat ) este de Nr[N][M] care reprezinta numarul de a imparti cele N numere in M clase fiecare.
De aici rezulta ca fiecare numar poate fi la un moment dat in una din cele M clase intr-un sir de N elemente adica N^M posibilitati.
De aici s-ar putea face inca o factorizare a acestor clase de echivalente dupa lungimea celui mai mare lant din Hash[p] . In acesta situatie avem clar "N" clase in care se vor imparti cele N^M clase . Si trebuie vazut care dintre aceste clase are cele mai multe elemente. Intuiesc ca cele mai multe se regasesc undeva pe la o clasa care face ca lungimea sa fie logN . [desi ciudat, pentru ca in cel mai bun caz lungimea acestuia ar trebui sa fie N/M atunci cand functia de dispersie isi face treba bine, singura logica ar fi ca in urma verificarii sa se arate ca de fapt in majoritatea claselor de echivalenta lungimea majoritatii lanturilor din hash sa fie suficient de mica si sa se arate ca acesta ar fi ~ logN si ca sa fie posibil asa ceva existand si lanturi mai mari dar care sa nu fie extrem de multe in comparatie cu cele mici] ( Ar trebui sa fac un program sa vad dispersia ... uniforma a elementelor ) . Ar fi interesant insa sa si demonstram asta .
Ceea ce ma intriga este faptul ca in gandirea mea. Numarul de liste din tabela de dispersie adica "M" are o importanta in a valida complexitatea pe cand cele prezentate in articol singurul factor importantant era secventa de lumgime N care era adaugata in Hash .
. Evident, se poate considera ca M este un factor constant in creerea tabelei de dispersie initiale si N nu este dar totusi in cele mai multe tabele de dispersie acesta este foarte mare si este destul de important pentru a creste performantele hash-ului .
De asemenea e destul de usor de vazut ca toate clasele de echivalenta au acelasi nr de elemente .
Nu sunt chiar de aceeasi parere. Detaliaza te rog