Hash Table Proof...

[cunimartum]

Duke ndihmuar Instruktoren e Kursit te Data Structures ne YorkU per Assignment numer 3 me ka dale nje problem i vogel.
Ja faqja, futu ke lectures nen Natalia Vlajic http://www.cs.yorku.ca/course/2011/

Problemi eshte me shume nje inat i vockel personal mbi nje ushtrim ne lidhje me Hash Tables. Po hedh njehere si mendojme ta paraqesim ushtrimin:

Hash Table [20 points]
Given the input sequence {4371, 1323, 6173, 4199, 4344, 9679, 1989}, a hash table of size b = 10,
and a hash function h(x) = x mod b, show each step needed to build a hash table in each of the
following cases.
a. [5 points] An open hash table, with insertion at the front of the chain.
b. [5 points] A closed hash table using linear probing (that is, f(i) = i).
c. [5 points] A closed hash table using quadratic probing (that is, f(i) = i2).
d. [5 points] A closed hash table using double hashing, with the second hash function as
h’(x) = 7 - (x mod 7).
This yields the sequence of hash functions
hi(x) = (x mod b + i⋅(7-(x mod 7))) mod b, for i=0,1,…
If, during the course of inserting into the hash table, you reach a point when it is not possible to
complete the insertion, then note this in your write-up. Briefly explain what happened to prevent the
insertion and why.

Tashti problemi eshte se ne piken (d.) po te ndiqen sakte veprimet duhet te arrihet ne dicka te tille

D- Fourth case:

In our fourth case of the Double Hashing the secondary function is: h’(x) = 7 - (x mod 7) which yields to the sequence of hash functions:
hi(x) = (x mod b + i•(7-(x mod 7))) mod b, for i=0,1,…

4371 -> 1
1323 -> 3
6173+1 -> 4 //since 3 is busy
4199 -> 9
4344+1 mod 10 -> 7 //since 4 is busy
9679+1 mod 10 -> 5 //since 9 and 1 and 3 were busy
1989+3² mod 10 -> error //the runout occurs because there is no tryout that can find a free space on the Hash Table

Por nuk do te kete kurrsesi perseritje nese i ne funksionin e dyte (double Hashing) do te fillonte nga 1 pra i = 1, 2, 3, .... dhe jo nga 0.
Une provova nje sere rastesh dhe vura re qe nese i fillon nga 0 bllokim total te vendeve do te ndodhin qe cojne ne Error ndersa nese ( i ) fillon nga 1 edhe shanset per perplasje jane me te rralla.
Tashti eshte rastesi apo ka te beje me ndonje vecori matematike, ky eshte gjithe "inati" qe kemi pasi nese dua ti ve kapak qe eshte vecori duhet dhe ta provoj.
Une kerkova ca dhe nje Profesor Rus e fillonte ( i ) nga 1 por vertetim s'gjeta gje. I thava ca trute me induksionin por sikur s'po leviz dot gje.

Them qe po te kete ndonje qe ka mbaruar per Pure Math e ka buke e djathe se nusja qe e ka marre Minor bashke me COSC s'me beri dot gje.

[edspace]

Cunimartum, po i futem njëherë kësaj valle edhe pse nuk kam mbaruar për matematikë dhe kam marrë vetëm një klasë me strukturat e informacionit. (data structures).

hi(x) = (x mod b + i•(7-(x mod 7))) mod b, për i=0,1,…

Nqs i=0 dhe b=10 atëherë funksioni do të thjeshtohet:
hi(x) = (x mod 10 + 0•(7-(x mod 7))) mod 10
hi(x) = (x mod 10 + 0) mod 10
hi(x) = (x mod 10) mod 10

(x mod 10) do ketë rezultat njëshifror prandaj (mod 10) e dytë del jashtë loje sepse nuk ndryshon asgjë.

Funksioni i fundit është
h(x) = (x mod 10)

Ky ëshë funksioni origjinal që është dhënë tek pyetja për metodën "single hashing". Prandaj do ketë patjetër përplasje (collision) sepse është funksion shumë i thjeshtë dhe çelësi është gjithnjë shifra e fundit (e njësheve).

Prandaj numrat:
1323
6173
kanë të njëjtin çelës dhe këtu ndodh përplasja.

Gjithashtu edhe numrat
4199
9679
1989
kanë të njëjtin çelës dhe këtu ndodh përplasja.

Duke filluar nga i=1 ky problem eliminohet sepse funksioni nuk mund të thjeshtohet.

Kjo mu duk si përgjigje e lehtë dhe nuk e di nqs ishte ajo çfarë kërkoje por shpresoj të të kem ndihmuar disi.

[cunimartum]

Edspace te falenderoj per kohen e harxhuar.
Pergjigja eshte shume e sakte dhe faktikisht i = 0 te con vetem ne perseritjen e dyte te "single hashing" por sipas rregullit kryesor te double hashing i pasi merr vleren 0 duhet te filloj te marre vlerat qe vijojne dhe tjetra vijuese eshte i =1, dhe tani fillon te vihet ne pune funksioni i dyte
h 1 (x) = (x mod 10 + 1 • (7-(x mod 7))) mod 10, për i=1
Dhe na del qe edhe zevendesimi i i-se me 1 rastesisht apo qellimisht godet ne runout
Ndodhi sepse funksioni i pare u perserit dy here apo ishte rastesi ??
Dhe nese ndodhi sepse funksioni i pare "single hashing" u perserit dy here atehere c'eshte ky efekt ? A arrihet dot ne nje konkluzion matematik ?
Kuptohet b eshte marre 10 vetem per te kuptuar nxenesit qe b ashtu sic theksohet ne c'do tekst duhet te jete te pakten numer primar dhe e mira eshte te jete 9 ose 11 ose 13
Ndodh ky problem vetem kur b nuk eshte primare apo edhe kur ajo eshte?

[edspace]

Rezultatet për i=0,1,2,3....oo

---------------------------------------------
hi(x) = (x % 10 + i * (7 - (x % 7))) % 10
---------------------------------------------
x=4371
i=0
hi(x)=1

---------------------------------------------
x=1323
i=0
hi(x)=3

---------------------------------------------
x=6173
i=0
hi(x)=3 ( perseritje )

i=1
hi(x)=4

---------------------------------------------
x=4199
i=0
hi(x)=9

---------------------------------------------
x=4344
i=0
hi(x)=4 ( perseritje )

i=1
hi(x)=7

---------------------------------------------
x=9679
i=0
hi(x)=9 ( perseritje )

i=1
hi(x)=1 ( perseritje )

i=2
hi(x)=3 ( perseritje )

i=3
hi(x)=5

---------------------------------------------
x=1989
i=0
hi(x)=9 ( perseritje )

i=1
hi(x)=5 ( perseritje )

i=2
hi(x)=1 ( perseritje )

i=3
hi(x)=7 ( perseritje )

i=4
hi(x)=3 ( perseritje )

i=5
hi(x)=9 ( perseritje )

i=6
hi(x)=5 ( perseritje )

i=7
hi(x)=1 ( perseritje )

i=8
hi(x)=7 ( perseritje )

i=9
hi(x)=3 ( perseritje )

i=10
hi(x)=9 ( perseritje )

i=11
hi(x)=5 ( perseritje )

i=12
hi(x)=1 ( perseritje )

i=13
hi(x)=7 ( perseritje )

i=14
hi(x)=3 ( perseritje )

......vazhdon ne pafundesi 95173....95173....95173...

---------------------------------------------

0 =
1 = 4371
2 =
3 = 1323
4 = 6173
5 = 9679
6 =
7 = 4344
8 =
9 = 4199
? = 1989

[edspace]

Rezultatet për i=1,2,3....oo
---------------------------------------------
hi(x) = (x % 10 + i * (7 - (x % 7))) % 10
---------------------------------------------
x=4371
i=1
hi(x)=5
---------------------------------------------
x=1323
i=1
hi(x)=0
---------------------------------------------
x=6173
i=1
hi(x)=4
---------------------------------------------
x=4199
i=1
hi(x)=0 ( perseritje )

i=2
hi(x)=1
---------------------------------------------
x=4344
i=1
hi(x)=7
---------------------------------------------
x=9679
i=1
hi(x)=1 ( perseritje )

i=2
hi(x)=3
---------------------------------------------
x=1989
i=1
hi(x)=5 ( perseritje )

i=2
hi(x)=1 ( perseritje )

i=3
hi(x)=7 ( perseritje )

i=4
hi(x)=3 ( perseritje )

i=5
hi(x)=9
---------------------------------------------

0 = 1323
1 = 4199
2 =
3 = 9679
4 = 6173
5 = 4371
6 =
7 = 4344
8 =
9 = 1989

[edspace]

Cunimartum,

Shkruajta nje program te shkruter (c++) per te llogaritur pergjigjet dhe i kam postuar ato me lart.
Ne rastin kur i=0,1,2... arrijme ne nje perseritje te pafund me numrin e fundit 1989. Ndersa ne rastin e dyte kur i=1,2,3...
te gjithe numrat gjejne vendin e tyre dhe funksioni ploteson nje hash ideal (pa perplasje).

Ndodh ky problem vetem kur b nuk eshte primare apo edhe kur ajo eshte?

Nuk mendoj se ka te beje vlera e [b]-së dhe funksioni eshte i sakte per cdo vlere te [b]-së.

Ndodhi sepse funksioni i pare u perserit dy here apo ishte rastesi ??

Nga provat qe bera, kur i=1 asnje seri numrash nuk arriti ne perseritje te pafund dhe funksioni krijonte hash ideal. Ndersa kur i=0 ka raste qe ka perseritje te pafund dhe ka raste qe krijohet hash ideal. Prandaj mund te them se vlera fillestare e
[i]-së luan nje rol të rendesishem dhe nuk eshte thjesht rastesi qe arrijme ne perseritje te pafund kur i=0. Megjithate duhen bere akoma me shume prova per te nxjerre nje konkluzion dhe per te gjetur nje lidhje midis i=0 dhe rezultateve te funksionit.

Këtu ke kodin në c++ të programit që bëra për të testuar formulën. Për të mbyllur programin x duhet të jetë 9999.

#include		

using namespace std;	

int main (void) 
{

	int x, i, answer;
	
	cout << "hi(x) = (x % 10 + i * (7 - (x % 7))) % 10 " << endl << endl;

	while( x != 9999 ){

		cout << "x=";
		cin >> x;
		cout << "i=";
		cin >> i;

		answer = ( (x % 10 + i * (7 - (x % 7))) % 10 );
		cout << "hi(x)=" << answer << endl << endl;

	}
	
	return 0;
}

[cunimartum]

Edspace mesazhin e pashe qe ne dreke por s'kisha kohe. Ideja ishte shume e mire dhe te falenderoj. Une perdora kodin tend vetem sa i shtova nje Random Number Generator, i hoqa me te shumtat e detajeve dhe e lashe vetem "testPassed" ose "testFailed" nese while do te perseritej me shume se 7 here.
Ja tregova Pr. Vlajic rezultatet e testit por sic edhe prisja ma preu shkurt duke thene qe " Duhet ta dish randoms s'jane kurre nje 'justifikim' i vlefshem" , dhe me tregoi nje vertetim qe e kishte bere nje prof. ne University of Michigan - Ann Arbor. Faktikisht ai perdorte induksionin mbi faktin qe perseritja dy here e funksionit te pare con ne perplasje.
Nejse ma futi pak se e mbylli sikur fitoi ajo
Edspace rrofsh per kohen. Shendet.