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|
------------------------------------