CS234 Lecture Notes - Lecture 10: Linear Probing, Hash Function, Priority Queue
25 Sep 2017
School
Department
Course
Professor
Document Summary
Cs234 lecture note # 19 2017/07/04 tuesday front = (front + 1) % max size e. g. (21000+1) % 4000 = 1001. 97 % 20 = 17, however index 17 is already occupied, a collision! Solve for collision: probing: linear probing, put the value into the next index if the current index is occupied, if the next index is full then try the next of the next index, try until the last index. If the array is full, then there is no empty cell to place the value: clustering: 202 % 20 = 2, when value in index 4 has already been deleted and the cell remained empty, the searching algorithm may cause error. Instead of remove the value, we have to replace it with a value representing deleted (i. e. empty, but previously occupied) 63%20 = 3, however index 3 has already been occupied, but index 4 is empty because of previous removal, thus 63 should be inserted on index 4.
