Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Chained Scatter Table

Figure gif illustrates a chained scatter table . The elements of a chained scatter table are ordered pairs. Each array element contains a key and a pointer. All keys are stored in the table itself. Consequently, there is a fixed limit on the number of items that can be stored in a scatter table.

   figure12037
Figure: Chained Scatter Table

Since the pointers point to other elements in the array, they are implemented as integer-valued array subscripts rather than as address-valued pointer variables. Since valid array subscripts start from the value zero, the null pointer must be represented not as zero, but by an integer value that is outside the array bounds.

To find an item in a chained scatter table, we begin by hashing that item to determine the location from which to begin the search. E.g., to find the string "åtta", which hashes to the value tex2html_wrap_inline62902, we begin the search in array location tex2html_wrap_inline62904. The item at that location is "två", which does not match. So we follow the pointer in location tex2html_wrap_inline62904 to location tex2html_wrap_inline62908. The item there, "fyra", does not match either. We follow the pointer again, this time to location tex2html_wrap_inline62910 where we ultimately find the string we are looking for.

Comparing Figures gif and gif, we see that the chained scatter table has embedded within it the linked lists which appear to be the same as those in the separately chained hash table. However, the lists are not exactly identical. When using the chained scatter table, it is possible for lists to coalesce .

For example, when using separate chaining, the keys "tre" and "sju" appear in a separate list from the key "tolv". This is because both "tre" and "sju" hash to position tex2html_wrap_inline62912, whereas "tolv" hashes to position tex2html_wrap_inline62914. The same keys appear together in a single list starting at position tex2html_wrap_inline62912 in the chained scatter table. The two lists have coalesced.




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.