RiverSoftAVG Products Help

The TGCustomHashTable class is the base class for all hash tables in the unit. It implements a bucket hash table where the user can store Key-Value pairs where the retrieval of a value from the table using its key takes constant time (actually constant * K where K is determined by the number of collisions) no matter how large the table grows. Compare this to a TStringList where accessing an object based on its string (using the IndexOf method) is an O(n) operation, or O(log n) operation if the string list is sorted. The Key may be a non-contiguous value (unlike a TList index). You never use the TGCustomHashTable class in your code, use one of its descendants, such as TGHashTable or TGStringHashTable .

Key-Value pairs are stored in the table using a hashing function (controlled by the GHashTable.TGCustomHashtable.HashType property). A hashing function maps key values into a smaller number of contiguous indices. Since a hashing function "shrinks" the number of items into a smaller number of items, it is guaranteed that when the number of items exceeds the capacity (and usually much earlier) there will be different keys mapped to the same hash value (called a collision). A good hashing function will minimize the number of collisions that occur. When a collision occurs, the table stores the separate key-value pairs in a linked list under that hash value. The TGCustomHashtable class provides several different hashing functions to see what works best for your group of keys.

The hash table starts with an initial GHashTable.TGCustomHashtable.Capacity which specifies the size of the hash value table. As the number of items exceeds a percentage of the capacity (controlled by the GHashTable.TGCustomHashtable.LoadFactor property), the hash table will expand and rehash the items already in the table (potentially an expensive operation). The LoadFactor property controls how full the table may get and indirectly affects the number of collisions that will occur. A high LoadFactor (say 75%) property wastes less memory and avoids lots of rehashing but as the table fills up there will be more collisions. A low LoadFactor property avoids more collisions at the cost of more memory and more frequent hashing operations. If you know the number of items you are placing in the table beforehand, increasing the Capacity property before adding items can reduce the number of collisions as well as expensive rehashing operations. The Collisions property tracks the number of collisions that are occurring as you add items; if a high number of collisions is occurring, you may want to change the hashing function.

To iterate through the entire table of items, you can use the iterators returned from the Elements or Indices methods, or use the Reset method, NextElement method, and EOT property.

Namespace: GHashTable