Java Reference
In-Depth Information
T
's Nondefault
From
T
's
Index
Contents
Row Column
0
L
1
1
1
P
1
4
2
Q
2
2
3
R
2
5
4
U
3
3
5
W
4
1
6
X
4
2
7
Y
5
2
8
Z
5
4
Figure 5.21: Compact version of the table in Figure 5.20 using binary
search. Only the boxed information is stored in the compact
table.
To create the compact table, we process the nondefault entries of
T
in any
order. The nondefault entry at
T
[
i
,
j
] is stored in the compact table at
h
(
i
,
j
)
if that position is unoccupied. Otherwise, we search forward in the table,
storing
T
[
i
,
j
] at the next available slot. This method of handling
collisions
in the compact table is called
linear resolution
. Because the compact table
contains
1 slots, one slot is always free after all nondefault entries are
hashed. The vacant slot avoids an infinite loop when searching the compact
table for a default entry.
Hashperformance can be improved by allocatingmore slots in the compact
table and by choosing a hash function that results in fewer collisions. Because
the nondefault entries of
T
are known in advance, bothgoals canbe achieved by
using
perfect hashing
[Spr77, CLRS01]. With this technique, each nondefault
entry
T
[
i
,
j
]mapstooneof
|
E
|+
slots using the key (
i
,
j
). A nondefault entry is
detected when the perfect hash function returns a value greater than
|
E
|
|
E
|
.
Compaction reduces the storage requirements of a parse table by eliminating
default entries. However, the indices of a nondefault entry must be stored
in the compact table to facilitate nondefault entry lookup. As shown in Fig-
ures 5.21 and 5.22, a given row or column index can be repeated multiple
times. We next examine a
compression
method that tries to eliminate such
redundancy and take advantage of default entries.
