Weeeeeeeeeeeeeee

Synonym= two or more keys that hash to the same home address

Collision= event that occurs when a hashing algorithm produces an address which is already occupied

Home Address= address produced by the hashing algorithm

Prime Area= memory that contain s all of the home addresses

Probe= calculation of an address and test for success

Collision Resolution= an algorithmic processing that determines an alternative address after a collision

3 General Methods:

1. Open Addressing

2. Linked List

3. Buckets

1. Open Addressing

a. Linear Probe-when the collision occurs, the second data will be stored in the next available address.

b. Quadratic method-the increment is the collision probe number squared

c. Pseudorandom Number Rehashing- we use a random generator to rehash the address

d. Key-offset rehashing-we use an offset to rehash the address

(no collision) First Insert: 070918, [001] 379452 | Dodd

Trapp at index 2 [002] 070918 | Trapp

Second Insert: 1196702, [003] 121267 | Dexaux

(collision) Eagle at index 2 [004] |

[005] |

[006] | Eagle

[307] | Feldman

Probe | Collision Location | Probe^2 | New Address Location |

12 | 12 | 1^2=12^2=4 | 26 |

3 | 6 | 3^2=9 | 15 |

4 | 15 | 4^2=16 | 31 |

5 | 31 | 5^2=25 | 56 |

6 | 56 | 6^2=36 | 82 |

C. Pseudo random number rehashing

Formula:

Y=(ax=c) modulo listsize + 1

Ex.

a=3

c=-1

y=(3x2+(-1))mod 307 +1

= 5 Mod 307 + 1

= 3

Y=(3x3+(-1)) Mod 307 + 1

= 8 Mod 307 + 1

= 3 + 1

= 4

D. Formula:

Offset= [key/list size]

Address=((offset + old address)modulo list size)+ 1

Offset= 166702/307=543

Address=((543+002)mod 307)+1

=238+1

=239(2nd Collision)

Offset = 543

Address=((543=239)mod 307)+1

=168+1

=169