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

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

```