Question? Leave a message!




Linear probing

Linear probing
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Linear Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo probing Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Linear probing 2 Outline Our first scheme for open addressing: – Linear probing—keep looking ahead one cell at a time – Examples and implementations – Primary clustering – Is it working looking ahead every k entries?Linear probing 3 Linear Probing The easiest method to probe the bins of the hash table is to search forward linearly Assume we are inserting into bin k: – If bin k is empty, we occupy it – Otherwise, check bin k + 1, k + 2, and so on, until an empty bin is found • If we reach the end of the array, we start at the front (bin 0)Linear probing 4 Linear Probing Consider a hash table with M = 16 bins Given a 3-digit hexadecimal number: – The least-significant digit is the primary hash function (bin) – Example: for 6B72A , the initial bin is A and the jump size is 3 16 Linear probing 5 Insertion Insert these numbers into this initially empty hash table: 19A, 207, 3AD, 488, 5BA, 680, 74C, 826, 946, ACD, B32, C8B, DBE, E9C 0 1 2 3 4 5 6 7 8 9 A B C D E FLinear probing 6 Example Start with the first four values: 19A, 207, 3AD, 488 0 1 2 3 4 5 6 7 8 9 A B C D E FLinear probing 7 Example Start with the first four values: 19A, 207, 3AD, 488 0 1 2 3 4 5 6 7 8 9 A B C D E F 207 488 19A 3ADLinear probing 8 Example Next we must insert 5BA 0 1 2 3 4 5 6 7 8 9 A B C D E F 207 488 19A 3ADLinear probing 9 Example Next we must insert 5BA – Bin A is occupied – We search forward for the next empty bin 0 1 2 3 4 5 6 7 8 9 A B C D E F 207 488 19A 5BA 3ADLinear probing 10 Example Next we are adding 680, 74C, 826 0 1 2 3 4 5 6 7 8 9 A B C D E F 207 488 19A 5BA 3ADLinear probing 11 Example Next we are adding 680, 74C, 826 – All the bins are empty—simply insert them 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 826 207 488 19A 5BA 74C 3ADLinear probing 12 Example Next, we must insert 946 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 826 207 488 19A 5BA 74C 3ADLinear probing 13 Example Next, we must insert 946 – Bin 6 is occupied – The next empty bin is 9 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 826 207 488 946 19A 5BA 74C 3ADLinear probing 14 Example Next, we must insert ACD 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 826 207 488 946 19A 5BA 74C 3ADLinear probing 15 Example Next, we must insert ACD – Bin D is occupied – The next empty bin is E 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 826 207 488 946 19A 5BA 74C 3AD ACDLinear probing 16 Example Next, we insert B32 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 826 207 488 946 19A 5BA 74C 3AD ACDLinear probing 17 Example Next, we insert B32 – Bin 2 is unoccupied 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 B32 826 207 488 946 19A 5BA 74C 3AD ACDLinear probing 18 Example Next, we insert C8B 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 B32 826 207 488 946 19A 5BA 74C 3AD ACDLinear probing 19 Example Next, we insert C8B – Bin B is occupied – The next empty bin is F 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 B32 826 207 488 946 19A 5BA 74C 3AD ACD C8BLinear probing 20 Example Next, we insert D59 0 1 2 3 4 5 6 7 8 9 A B C D E F 680 B32 826 207 488 946 19A 5BA 74C 3AD ACD C8B