CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 14, 2002 03:23 PM

#### Hashing: Collision Resolution: Brent's Method [1]

Record Keys: 27, 18, 29, 28, 39, 13, 16

Table Size = 11; Hash Function = hash(key) = key mod 11

Incrementing Function = i(key) = Quotient (Key / 11) mod 11 (computed on incoming key)

| Key |
0 |  |
1 |  |
2 |  |
3 |  |
4 |  |
5 | 27 | 1. 27 mod 11 = 5
6 |  |
7 | 18 | 2. 18 mod 11 = 7; 3. 29 mod 11 = 7; i(29) = 2 so try 9
8 |  |
9 |  |
10 |  |

Should we move 18 to reduce the total # of probes? 18 has 1; 29 has 2; Is there any combination of i + j < 2? No, so don't move anything. Only if s (# of probes required to retrieve the item if nothing is moved) is 3 or more do we try to move.

| Key |
0 |  |
1 |  |
2 |  |
3 |  |
4 |  |
5 | 27 |
6 | 28 | 4. 28 mod 11 = 6; 5. 39 mod 11 = 6; collision
7 | 18 |
8 |  |
9 | 29 |
10 |  |

s value of 39 is 3 (i(39) = 3; try loc9; then loc1 so we need 3 probes to find 39) - try to reduce this; start with i = 1 and j = 1 ; try moving what is at the home address one offset along its chain i.e. move 28 to (i(28) = 2; so offset is 2) loc8. This works, so move 28 to loc8 and put 39 in loc6

| Key |
0 |  |
1 |  |
2 | 13 | 6. 13 mod 11 = 2
3 |  |
4 |  |
5 | 27 | 7. 16 mod 11 = 5; i(16) = 1; its s value is 6
6 | 39 |
7 | 18 |
8 | 28 |
9 | 29 |
10 |  |

try i=1; j=1; moving 27 i(27) = 2; but loc7 is filled so try another.

try i=1; j=2; moving 27 to the next location 9; but it's filled too

try i=2; j=1; moving 39 i(39) = 3; but it's filled too

try i=1;j=3; moving 27 to the next location 0 - this works so move 27 to loc0 and put 16 in loc5

Is this better? Total probes for 27 and 16 without moves is 7; but with moves is 5 so we're ahead.

| Key |
0 | 27 |
1 |  |
2 | 13 |
3 |  |
4 |  |
5 | 16 |
6 | 39 |
7 | 18 |
8 | 28 |
9 | 29 |
10 |  |

CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 14, 2002 03:23 PM