Top Up Prev Next Bottom Contents Index Search

3.7 Hash Tables

Hash tables are lists that are indexed by an ASCII string. A " hashing function" is computed from the string to make random accesses reasonably efficient; they are much more efficient, for example, than a linear search over a SequentialList. Two such classes are provided in the Ptolemy kernel. The first, HashTable, is generic, in that the table entries are of type Pointer, and thus can point to any user-defined data structure. The second, TextTable, is more specialized; the entries are strings. It is derived from HashTable.

The HashTable class is summarized in table 3-12

and TextTable class is summarized in table 3-13. Only the most useful (and easily used) methods are described. You may want to refer to the source code for more information. The HashTable class has a standard iterator called HashTableIter, where the next method and ++ operator return a pointer to class HashEntry. This class has a const char* key() method that returns the key for the entry, and a Pointer value() method that returns a pointer to the entry. TextTable has an iterator called TextTableIter, where the next method and ++ operator return type const char*.

Sophisticated users will often want to derive new classes from HashTable. The reason is that the methods that look up data in the table can be defined to return pointers of the appropriate type. Moreover, the deallocation of memory when an entry is deleted or the table itself is deleted can be automated. TextTable is a good example of such a derived class. This is not possible with the generic HashTable class, because the Pointer type does not give enough information to know what destructor to invoke. Thus, when using the generic HashTable class, the user should explicitly delete the objects pointed to by the Pointer if they were dynamically created and are no longer needed. A detailed example that directly uses the HashTable class, without defining a derived class, is given in the next section. In that example, the Pointer entries point to stars in a universe, so they should not be deleted when the entries in the table are deleted. Their memory will be deallocated when the universe is deleted.

In some future version, HashTable might be reimplemented using templates.



Top Up Prev Next Bottom Contents Index Search

Copyright © 1990-1997, University of California. All rights reserved.