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  :