User Tools
Problem constructing authldap
arhiva:teme:2013:tema3
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
arhiva:teme:2013:tema3 [2014/10/27 19:53] Adriana Draghici [Resurse] |
arhiva:teme:2013:tema3 [2014/10/27 19:55] (current) Adriana Draghici |
||
|---|---|---|---|
| Line 19: | Line 19: | ||
| Principiul de bazǎ este urmǎtorul: în locul dispunerii într-o singurǎ listǎ liniarǎ a tuturor perechilor cheie-valoare (**entry**-uri) din tabelǎ, acestea sunt grupate în mai multe subliste (**bucket**-uri), pe baza unui anumit criteriu. Astfel, cǎutarea unei chei se va face **doar** în ''bucket''-ul corespunzǎtor, şi nu în toatǎ lista, fapt ce reduce timpul de cǎutare. Pentru stabilirea ''bucket''-ului în care va fi plasat un ''entry'', cheii îi este aplicatǎ o funcţie de dispersie (**hash function**) care întoarce un numǎr întreg, numit cod de dispersie (**hash code**). Pe baza acestuia se determinǎ ''bucket''-ul în care se va introduce intrarea. Iatǎ o tabelǎ de dispersie: | Principiul de bazǎ este urmǎtorul: în locul dispunerii într-o singurǎ listǎ liniarǎ a tuturor perechilor cheie-valoare (**entry**-uri) din tabelǎ, acestea sunt grupate în mai multe subliste (**bucket**-uri), pe baza unui anumit criteriu. Astfel, cǎutarea unei chei se va face **doar** în ''bucket''-ul corespunzǎtor, şi nu în toatǎ lista, fapt ce reduce timpul de cǎutare. Pentru stabilirea ''bucket''-ului în care va fi plasat un ''entry'', cheii îi este aplicatǎ o funcţie de dispersie (**hash function**) care întoarce un numǎr întreg, numit cod de dispersie (**hash code**). Pe baza acestuia se determinǎ ''bucket''-ul în care se va introduce intrarea. Iatǎ o tabelǎ de dispersie: | ||
| - | {{:teme:teme:tabela_de_dispersie.png}} | + | {{.:teme:tabela_de_dispersie.png}} |
| Sǎ luǎm exemplul **agendei telefonice**. Putem alege drept funcţie de dispersie ''h'' poziţia din alfabet a primei litere a numelui persoanei. De exemplu, ''h("Andrei") = 1'' (litera A ocupǎ poziţia 1 în alfabet). Avem astfel 26 de valori posibile ale funcţiei ''h'' şi introducem în tabelǎ 26 de ''bucket''-uri. Primul va reprezenta lista perechilor (''nume, numar_de_telefon'') pentru care numele încep cu litera A. Al doilea, cu litera B etc. Mai jos se aflǎ o reprezentare principialǎ a agendei. Desigur, în ultima coloanǎ se pot înlǎnţui mai multe intrǎri în acelaşi bucket. | Sǎ luǎm exemplul **agendei telefonice**. Putem alege drept funcţie de dispersie ''h'' poziţia din alfabet a primei litere a numelui persoanei. De exemplu, ''h("Andrei") = 1'' (litera A ocupǎ poziţia 1 în alfabet). Avem astfel 26 de valori posibile ale funcţiei ''h'' şi introducem în tabelǎ 26 de ''bucket''-uri. Primul va reprezenta lista perechilor (''nume, numar_de_telefon'') pentru care numele încep cu litera A. Al doilea, cu litera B etc. Mai jos se aflǎ o reprezentare principialǎ a agendei. Desigur, în ultima coloanǎ se pot înlǎnţui mai multe intrǎri în acelaşi bucket. | ||
| - | {{:teme:teme:agenda_telefonica.png}} | + | {{.:teme:agenda_telefonica.png}} |
| Constatǎm cǎ **eficienţa** operaţiei de cǎutare depinde de alegerea **funcţiei de dispersie**. De exemplu, pentru o funcţie de dispersie **constantǎ**, ''h(key) = 1'', pentru orice cheie ''key'', obţinem o unicǎ listǎ înlǎnţuitǎ. În acest caz eficienţa este **cea mai slabǎ**. La polul opus, cu eficienţǎ maximǎ, s-ar afla o funcţie de dispersie **injectivǎ**, care genereazǎ un cod de dispersie **unic** pentru fiecare cheie, astfel cǎ fiecare bucket ar conţine o singurǎ intrare. În practicǎ, astfel de funcţii sunt foarte greu de gǎsit. | Constatǎm cǎ **eficienţa** operaţiei de cǎutare depinde de alegerea **funcţiei de dispersie**. De exemplu, pentru o funcţie de dispersie **constantǎ**, ''h(key) = 1'', pentru orice cheie ''key'', obţinem o unicǎ listǎ înlǎnţuitǎ. În acest caz eficienţa este **cea mai slabǎ**. La polul opus, cu eficienţǎ maximǎ, s-ar afla o funcţie de dispersie **injectivǎ**, care genereazǎ un cod de dispersie **unic** pentru fiecare cheie, astfel cǎ fiecare bucket ar conţine o singurǎ intrare. În practicǎ, astfel de funcţii sunt foarte greu de gǎsit. | ||
arhiva/teme/2013/tema3.1414432395.txt.gz · Last modified: 2014/10/27 19:53 by Adriana Draghici
Page Tools
