ABSTRACT
While a digitized ordered collection extends an ordered collection, it can also be a good choice for applications that simply require searching for an equivalent element. For such applications, no ordering among the elements is used. There are two important advantages of a DigitizedOrderedCollection over a Set or Mapping ADT implementation based on hashing. The first is the ability to efficiently find all extensions of a given prefix or all elements sharing a longest common prefix. The second advantage is that often an unsuccessful search requires looking at only a small number of digits, whereas a hashing-based data structure uses all of the digits in computing the hash function and in making the comparison at each probe. We briefly describe an application that benefits from each of these advantages.
