Question? Leave a message!




Quadratic probing

Quadratic probing
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Quadratic probing Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Quadratic probing 2 Outline This topic covers quadratic probing – Similar to linear probing • Does not step forward one step at a time – Primary clustering no longer occurs – Affected by secondary clusteringQuadratic probing 3 Background Linear probing: – Look at bins k, k + 1, k + 2, k + 3, k + 4, … – Primary clusteringQuadratic probing 4 Background Linear probing causes primary clustering – All entries follow the same search pattern for bins: int initial = hash_M( x.hash(), M ); for ( int k = 0; k M; ++k ) bin = (initial + k) % M; // ... Quadratic probing 5 Description Quadratic probing suggests moving forward by different amounts For example, int initial = hash_M( x.hash(), M ); for ( int k = 0; k M; ++k ) bin = (initial + kk) % M; Quadratic probing 6 Description Problem: – Will initial + kk step through all of the bins? – Here, the array size is 10: M = 10; initial = 5 for ( int k = 0; k = M; ++k ) std::cout (initial + kk) % M ' '; – The output is 5 6 9 4 1 0 1 4 9 6 5Quadratic probing 7 Description Problem: – Will initial + kk step through all of the bins? – Now the array size is 12: M = 12; initial = 5 for ( int k = 0; k = M; ++k ) std::cout (initial + kk) % M ' '; – The output is now 5 6 9 2 9 6 5 6 9 2 9 6 5Quadratic probing 8 Making M Prime If we make the table size M = p a prime number quadratic probing p  is guaranteed to iterates through entries  2  Problems: – All operations must be done using % • Cannot use &, , or • The modulus operator % is relatively slow – Doubling the number of bins is difficult: • What is the next prime after 2 × 263?Quadratic probing 9 Generalization More generally, we could consider an approach like: int initial = hash_M( x.hash(), M ); for ( int k = 0; k M; ++k ) bin = (initial + c1k + c2kk) % M; Quadratic probing 10 m Using M = 2 m If we ensure M = 2 then choose c = c = ½ 1 2 int initial = hash_M( x.hash(), M ); for ( int k = 0; k M; ++k ) bin = (initial + (k + kk)/2) % M; – Note that k + kk is always even 2 – The growth is still Q(k ) – This guarantees that all M entries are visited before the pattern repeats • This only works for powers of twoQuadratic probing 11 m Using M = 2 For example: – Use an array size of 16: M = 16; initial = 5 for ( int k = 0; k = M; ++k ) std::cout (initial + (k + kk)/2) % M ' '; – The output is now 5 6 8 11 15 4 10 1 9 2 12 7 3 0 14 13 13Quadratic probing 12 m Using M = 2 There is an even easier means of calculating this approach int bin = hash_M( x.hash(), M ); for ( int k = 0; k M; ++k ) bin = (bin + k) % M; 2 k kk  j – Recall that , so just keep adding the next highest value  2 j0Quadratic probing 13 Example Consider a hash table with M = 16 bins Given a 2-digit hexadecimal number: – The least-significant digit is the primary hash function (bin) – Example: for 6B7A , the initial bin is A 16 Quadratic probing 14 Example Insert these numbers into this initially empty hash table 9A, 07, AD, 88, BA, 80, 4C, 26, 46, C9, 32, 7A, BF, 9C 0 1 2 3 4 5 6 7 8 9 A B C D E FQuadratic probing 15 Example Start with the first four values: 9A, 07, AD, 88 0 1 2 3 4 5 6 7 8 9 A B C D E FQuadratic probing 16 Example Start with the first four values: 9A, 07, AD, 88 0 1 2 3 4 5 6 7 8 9 A B C D E F 07 88 9A ADQuadratic probing 17 Example Next we must insert BA 0 1 2 3 4 5 6 7 8 9 A B C D E F 07 88 9A ADQuadratic probing 18 Example Next we must insert BA – The next bin is empty 0 1 2 3 4 5 6 7 8 9 A B C D E F 07 88 9A BA ADQuadratic probing 19 Example Next we are adding 80, 4C, 26 0 1 2 3 4 5 6 7 8 9 A B C D E F 07 88 9A BA ADQuadratic probing 20 Example Next we are adding 80, 4C, 26 – All the bins are empty—simply insert them 0 1 2 3 4 5 6 7 8 9 A B C D E F 80 26 07 88 9A BA 4C AD