Hash Tables



A hash table is a list of strings in which each item is in the form Name=Value. It can be illustrated as follows:

Name1 Value1
Name2 Value2
Name3 Value3
Name4 Value4

There is no strict rule as to when, where, why, or how to use a hash table. Everything depends on the programmer. For example, it can be used to create a list that would replace a 2-dimensional array. Nevertheless, a hash table presents advantages: it saves space, it reduces the likelihood of making a mistake when referring to an item that belongs to the list. For example, if you create a 2-dimensional array of strings, whenever you want to refer to an item of the second dimension, you must do some gymnastics to locate the item of the first dimension and you must make sure that you refer to the right item, otherwise... A hash table solves such problems by keeping track of each item as a combination of two objects although still giving you a tremendous easy way to refer to the left or the right parts of the item. Hash tables are commonly used in lists of items. Typical examples include .ini files


Creating a Hash Table

In Borland C++ Builder 5 and prior versions, you could create a hash table using the TStringList class. In Borland C++ Builder 6, the Visual Component Library ships with the THashedStringList class that is defined in the IniFiles.hpp header file. This class is derived from the StringList. If you are already familiar with how wonderful the StringList is and how it makes it particularly easy to create and manage a list of strings, you would find the THashedStringList up to the point. In reality the THashedStringList adds only the ability to find the index of an item in the table.

To create a hash table, you can first declared a THashedStringList instance:

#ifndef Unit1H
#define Unit1H
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <IniFiles.hpp>
class TForm1 : public TForm
__published:	// IDE-managed Components
    THashedStringList *ListOfColors;    // User declarations
public:		// User declarations
    __fastcall TForm1(TComponent* Owner);
extern PACKAGE TForm1 *Form1;

Then, you can initialize it using the new operator:

ListOfColors = new THashedStringList;

As a class derived from TStrings (because TStringList itself derives from TStrings), to build the list of items, you can use the Add(), AddObject(), Insert(), and InsertObject() methods. The Add() and the Insert() methods take a string as argument. This argument specifies the item that needs to be added to the table. Unlike an item of a regular list of strings, an item of a hash table is in fact made of 3 sections:


The Name and the Value parts are strings and can be made of any characters. You must include the = operator between them, otherwise the item would not be considered a valid hash table item although the program would still compile fine. Here is an example that creates a list of colors:
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
    ListOfColors = new THashedStringList;

    ListOfColors->Add("Aqua Marine=0x7FFFD4");
    ListOfColors->Add("Spring Green=RGB(0, 255, 127)");

In the strict sense, a hash table is, first of all, a list of strings. This means that each string can be used as an individual item: you can move it, you can delete it, you can swap its position with another item in the same table. All these operations are possible using methods of the TStringList class. For example, as a child of the TStringList class, you can assign the list of items of a THashedStringList list to a list-based control such as a Memo, a list box, a rich edit, or a combo box, etc. Here is an example:
void __fastcall TForm1::FormCreate(TObject *Sender)
    ListBox1->Items = ListOfColors;

In the same way, since the hash table is primarily list of strings, you can locate each string using its index. You can also look for an item by specifying a string.

The beauty of using hash table is perform special operations on items. These operations are possible because you can refer to only the left or only the right sections of an item. As seen above, the left section is referred to as the Name part of an item. The right section is referred to as the Value part of the item. From our study of VCL strings lists, we know that we can retrieve the (whole) string of an item using the Strings[] member array. On the other hand, to retrieve the Name part of a string in a hash table, you can call the Names[] member array of the TStrings class. Using a loop, this same technique would allow you to scan a hash table looking for a particular item, or you can create a separate list of the Name parts of each item. Here is an example:
void __fastcall TForm1::Button1Click(TObject *Sender)
    for(int i = 0; i < ListOfColors->Count; ++i)

You can use this same technique to retrieve the Value part of an item. In the same way, you can use a loop to scan the list of items, look for an item, or create a new list made of Value parts of each item.



Copyright © 2003-2007 FunctionX, Inc.