CSCI1102 Lecture Notes - Lecture 10: Linked List, Quadratic Probing, Linear Probing
10 Dec 2015
School
Department
Course
Professor
Document Summary
Unsuccessful search continues until an empty slot is reached==> never fill the table completely==> empty slots should be scattered e. g. slot 0 through 8, with data in 3 5 7. In this case the next insert item has twice as likely to go into 4, 6, and 8 then the other remaining empty slots. When you have a big chunk of filled slots (cluster), the next empty slot has very high chance of getting filled. With linear probing there is a tendency toward. Hit every slot in the table before you start repeating. 2 hash functions: 1st determine initial probe, 2nd determine the probe sequence. A table with 0 to 7 slots. k1 in 2, k3 in 4, k2 in 5. hash(k4)=4. slot 4 already has k3. compute hash2(k4)=5. 5 slots. so put k4 into slot 1. hash(k5)=4 //already filled hash2(k5)=3 jump 3 steps and put k5 into slot 7. //probe sequence is independent of the initial probe.
