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 :
