Page 84 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes 3. Open addressing: If the first probe provides a position K and that position is filled, then
the next location K + 1 is probed, and so on in anticipation of a free position. If the hunt
runs off the bottom of the table, then it is transformed at the top. Specifically, the table is
considered to be cyclic.

!
Caution Out of these three techniques, the open addressing scheme is the simplest.

Example: Let us see an example to illustrate this technique.
Consider a table of 17 positions (N= 17) in which the following twelve numbers are to be
accumulated: 19. 13, 05, 27, 01, 26, 31, 16, 02, 09, 11.21. These items are to be placed in the table at
a position defined by the remainder after division by 17; if that position is filled, then the next
position is observed, etc. Figure 5.4 displays the progress of entry for the 12 items. Observe the
resolution of disagreemenst on items 02. 09, and 11. The column ‘Probes to find’ provides the
number of probes essential to locate the corresponding items in the table; so it takes 3 probes to
locate items 09, and 1 to locate item 26. The column ‘Probes to locate not’ provides the number
of probes needed to find out that an item is not in the table. So, the search for the number S4
would provide an initial position of 3 and it would take 4 probes to locate that the item is not
present. The item is recognized not to be present when a void position came across (position 6
in this case). Observe here that the following figures hold’
Length of table N = 17

Items stored M = 12
Density  = 12/17 = 0.705
Probes to store T = 16
s
Average probes to find T = 16/12 = 1.33
p
Average probes to find not T = 54/16 = 3.31
n
The proportional times for a packed table, by means of radix exchange sort (explained in the
next unit) and binary search are as follows:
Probes to store and sort T = M+M–log (M) = 55
s 2
Average probe to find T = log (M) = 3.58
p 2
Average probe to find not T = log (M) = 3.58
n 2
Therefore, it would emerge that the open addressing plan holds significant benefit in speed, but
it pays for this by having a table almost 50 percent longer than required. Moreover, the table
cannot be compacted after its initial allotment nor can the allotted area be simply shared between
several tables. One final drawback is that it is very complex to delete any item from the table.

Note One cannot just zero out that location since this might break the addressing chain.

Random entry with replacement is considered to be a simpler method to assess.

78 LOVELY PROFESSIONAL UNIVERSITY