Thursday, November 7, 2013

CSC508 DATA STRUCTURE HASH TABLE

SOLUTION FOR PROBLEM 1


Value to Hash :

2341
4234
2839
430
22
397
3920

h(x) = x mod 7

2341 % 7 = 3
4234 % 7 = 6
2839 % 7 = 4
430   % 7 = 3
22    % 7 = 1
397   % 7 = 5
3920 % 7 = 0


Original Table :

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY


SOLUTION USING SEPARATE CHAINING :

Step 1 : insert value 2341
Calculation : 2341 % 7 = 3

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
EMPTY
EMPTY
EMPTY

Step 2 : insert value 4234
Calculation : 4234 % 7 = 6

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
EMPTY
EMPTY
4234

Step 3 : insert value 2839
Calculation : 2839 % 7 = 6

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
2839
EMPTY
4234

Step 4 : insert value 430
Calculation : 430 % 7 = 3

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
2839
EMPTY
4234









430




Step 5 : insert value 22
Calculation : 22  % 7 = 1


0
1
2
3
4
5
6
EMPTY
22
EMPTY
2341
2839
EMPTY
4234
430




Step 6 : insert value 397
Calculation : 397  % 7 = 5


0
1
2
3
4
5
6
EMPTY
22
EMPTY
2341
2839
397
4234
430






Step 7 : insert value 3920
Calculation : 3920 % 7 = 0


0
1
2
3
4
5
6
3920
22
EMPTY
2341
2839
397
4234
430

Final table Values :

0
1
2
3
4
5
6
3920
22
EMPTY
2341
2839
397
4234
430





FINISH SOLUTION USING SEPARATE CHAINING :


SOLUTION USING OPEN ADDRESSING :


USING LINEAR PROBING :

LINEAR PROBING - Step 1 : insert value 2341
Calculation : 2341 % 7 = 3

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
EMPTY
EMPTY
EMPTY


LINEAR PROBING - Step 2 : insert value 4234
Calculation : 4234 % 7 = 6

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
EMPTY
EMPTY
4234


LINEAR PROBING - Step 3 : insert value 2839
Calculation : 2839 % 7 = 6

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
2839
EMPTY
4234


LINEAR PROBING - Step 4 : insert value 430
Calculation : 430 % 7 = 3
Position 3 is not empty so try : ( 3 + 1 ) % 7 = 4
Position 4 also is not empty so try : ( 4 + 1 ) % 7 = 5
Finally position 5 is empty.


0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
2839
430
4234

LINEAR PROBING - Step 5 : insert value 22
Calculation : 22  % 7 = 1


0
1
2
3
4
5
6
EMPTY
22
EMPTY
2341
2839
430
4234


LINEAR PROBING - Step 6 : insert value 397
Calculation : 397  % 7 = 5

Position 5 is not empty so try : ( 5 + 1 ) % 7 = 6
Position 6 also is not empty so try : ( 6 + 1 ) % 7 = 0

Finally position 0 is empty.


0
1
2
3
4
5
6
397
22
EMPTY
2341
2839
430
4234


LINEAR PROBING - Step 7 : insert value 3920
Calculation : 3920 % 7 = 0

Position 0 is not empty so try : ( 0 + 1 ) % 7 = 1
Position 1 also is not empty so try : ( 1 + 1 ) % 7 = 2

Finally position 2 is empty.


0
1
2
3
4
5
6
397
22
3920
2341
2839
430
4234









LINEAR PROBING - Final table Values :

0
1
2
3
4
5
6
397
22
3920
2341
2839
430
4234


FINISH USING LINEAR PROBING :




USING DOUBLE HASHING  with second hash function h’(x) = (2x-1) mode 7



DOUBLE HASHING - Step 1 : insert value 2341
Calculation : 2341 % 7 = 3

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
EMPTY
EMPTY
EMPTY


DOUBLE HASHING - Step 2 : insert value 4234
Calculation : 4234 % 7 = 6

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
EMPTY
EMPTY
4234


DOUBLE HASHING - Step 3 : insert value 2839
Calculation : 2839 % 7 = 6

0
1
2
3
4
5
6
EMPTY
EMPTY
EMPTY
2341
2839
EMPTY
4234


DOUBLE HASHING - Step 4 : insert value 430
Calculation : 430 % 7 = 3
Collision detected so use second hash function : h’(x) = (2x-1) mode 7

Position 3 is not empty so try : ( 2 * 430 - 1 ) % 7 = 5
So : ( 3 + ( 1 * 5 )) % 7 = 1

Finally position 1 is empty.


0
1
2
3
4
5
6
EMPTY
430
EMPTY
2341
2839
EMPTY
4234


DOUBLE HASHING - Step 5 : insert value 22
Calculation : 22  % 7 = 1

Collision detected so use second hash function : h’(x) = (2x-1) mode 7

Position 1 is not empty so try : ( 2 * 22 - 1 ) % 7 = 1
So : ( 1 + ( 1 * 1 )) % 7 = 2

Finally position 2 is empty.

0
1
2
3
4
5
6
EMPTY
430
22
2341
2839
EMPTY
4234


DOUBLE HASHING - Step 6 : insert value 397
Calculation : 397  % 7 = 5


0
1
2
3
4
5
6
EMPTY
430
22
2341
2839
397
4234


DOUBLE HASHING - Step 7 : insert value 3920
Calculation : 3920 % 7 = 0

0
1
2
3
4
5
6
3920
430
22
2341
2839
397
4234



DOUBLE HASHING - Final table Values :

0
1
2
3
4
5
6
3920
430
22
2341
2839
397
4234




FINISH USING DOUBLE HASHING  :