COMP 2140 Lecture 12: 10_15_hash.pdf
13 Aug 2014
School
Department
Course
Professor
Document Summary
Follow probe sequence until you reach the target or a null reference. Warning: you can get into infinite loop if the array is full solution: stop after checking tablesize positions. Advantage if there is an open position, linear probing will eventually find it. When we remove an item, we need to mark this position as being removed e. g. use another array of boolean. Search: stop probing when we encounter an empty position, but not when we encounter a removed position. Insert: can insert item in either empty or removed position. Primary clustering occurs with linear probing because the same linear pattern: if a slot is inside a cluster, then the next slot must either: also be in that cluster, or expand the cluster. Instead of searching forward in a linear fashion, consider searching forward using a quadratic function. Quadratic probing hash function: h(x)= x % 10 keys: 24, 34, 14, 54, 64, 35, 26.
