Copyright © 1998 T. H. Merrett 308-420A Secondary Storage Algorithms and Data Structures Week 5 Hash Delete with Linear Probing Algorithm LD, on pp.34-5, works, but I want to revise it to work block by block, not location by location. To delete record r found on block f: | | | | | | | | r | | | | | | ----------------------------------------------------- 0 f home n-1 LD1 (Remove record) l <- loc(r); oldf <- f; mark l on oldf empty LD2 (Move later records up) if block f not full (apart from deletion, if any, just made by LD1), stop. f <- if f=0 then n-1 else f-1 if f = original home block, stop. /* else full file can thrash */ for each record, r, on block f if ncycle(f, h(r), oldf) /*h(r) not cyclically between f, oldf or = oldf; i.e., h(r) at or beyond oldf*/ then {copy r to l on oldf; goto LD1} goto LD2 | | | r | | | | | | | | | | | ----------------------------------------------------- f h(r) oldf Try it to delete 10 in | |3, 1 |9, 16 |17, 10| | |13 | f | 3 2 1 0 -------------------------------------------------- h(r)| 2 2 3 0 1 2 3 4 5 6 oldf| 3 1 Result: 3 is moved to where 10 was. Load and Probe Factors Load factor N number of records alpha = --- = ----------------- n b capacity Probe factor total number of probes to place/read all records pi = ------------------------------------------------ number of records Example |xx |x |xxx|xx |xxx|xx |xx |xxx|x |xxx|xx |xxx|x | ----------------------------------------------------- xx x x x n = 13, b = 3, N = 33, assume overflow blocks hold at least 2 records alpha = 33/39 = 0.846, pi = 38/33 = 1.15 Multidimensional Hashing For instance, in two dimensions, hash each of two fields, a and b. Use h(a) and h(b) as two-dimensional coordinates for the page. Convert this to a one-dimensional page number by one of the usual array-addressing methods. E.g., row-major order page address = h(b) + w * h(a) where w is the width of the space. Example of 7 * 5 space (w = 7), with h(a), h(b) in upper left and page address in lower right corners of each page shown: ------------------------------------ |4,0 |4,1 |4,2 |4,3 |4,4 |4,5 |4,6 | | 28| 29| 30| 31| 32| 33| 34| ------------------------------------ |3,0 |3,1 |3,2 |3,3 |3,4 |3,5 |3,6 | | 21| 22| 23| 24| 25| 26| 27| ------------------------------------ |2,0 |2,1 |2,2 |2,3 |2,4 |2,5 |2,6 | | 14| 15| 16| 17| 18| 19| 20| ------------------------------------ |1,0 |1,1 |1,2 |1,3 |1,4 |1,5 |1,6 | | 7| 8| 9| 10| 11| 12| 13| ------------------------------------ |0,0 |0,1 |0,2 |0,3 |0,4 |0,5 |0,6 | | 0| 1| 2| 3| 4| 5| 6| ------------------------------------