Rogue Wave banner
Previous fileTop of documentContentsIndexNext file

13.7 A Note on How Objects are Found

You may save yourself some difficulty by remembering the following point: the virtual functions of the object within the collection, not those of the target, are called when comparing or testing a target for equality.

The following code fragment illustrates the point:

SortedCollection sc;
RWCollectableString member;

sc.insert(&member);

RWCollectableString target;
RWCollectableString* p = (RWCollectableString*)sc.find(&target);

In this example, the virtual functions of member within the collection RWCollectableString are called, not the virtual functions of target. In other words:

member.compareTo(&target);               //This will get called.
target.compareTo(&member);               //Not this.

13.7.1 Hashing

Hashing is an efficient method for finding an object within a collection. All the collection classes that use hashing follow the same general strategy. First, member function hash() of the target is called to find the proper bucket within the hash table. A buckets is implemented as a singly-linked list. Because all the members of a bucket have the same hash value, the bucket is linearly searched to find the exact match. This is done by calling member function isEqual() of the candidate (see above) with each member of the bucket as the argument. The first argument that returns TRUE is the chosen object. Be careful not to design your class so that two objects that test true for isEqual() can have different hash values, since this algorithm will fail for such objects.

In general, because of this combination of hashing and linear searching, as well as the complexity of most hashing algorithms, the ordering of the objects within a hash collection will not make a lot of sense. Hence, when the apply() function or an iterator scans through the hashing table, the objects will be visited in what appears to be random order.



Previous fileTop of documentContentsIndexNext file
©Copyright 1999, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.