Hashtable.pas

Hashtable.pas contains the implementation of THashTable and related classes, such as tHashTableIterator and tHashTableEntry. The HashTable is a map from TComparable to TObject. This is am incomplete rip-off of Java Collections package. Sorry :)

Please note : class definitions listed below include only public and published fields, properties and methods.


Please note - the class definitions in this section list only (re)implemented protected, public and published methods, fields and properties. For more details look in the source code.

When compiling this unit with freePascal, use -S2 switch.
THashEntry = class(TComparable)
protected
function compareObjects(object2 : tComparable) : integer; override;
public
next : tHashEntry
function hashCode : integer; override
function getKey : tComparable
function getValue : tObject
procedure setValue(avalue : tObject)
property key : tComparable read getKey
property value : tObject read getValue write setValue
constructor create(akey : tComparable; avalue : tObject)

This class holds the key-value pair in the hash table.

hashCode is a pass-through to the hash code of the key member.

next points to the next entry in the chain of entries with the same hash code. Last entry in the chain has this set to nil.

compareObjects will make sure that object2 is an object of the same clas and then compare keys

key is immutable.

THashEntryClass = class(THashEntry)

Need this to pass the class of THashEntry or its descendant as parameter to the constructor of THashEntryFactory



THashEntryFactory = class(TObject)
public
function getEntry(key: tComparable; value : tObject) : tHashEntry; virtual
constructor create(hashEntryClass : tHashEntryClass);

I am not sure why I decided that THashEntry needed a factory but here it is. It has not been tested with anything other than THashEntry but it should work. Or should it?

getEntry returns a new instance of the class passed to the constructor, initialized with key and value. The user of the new instance (THashTable in all likelyhood) is responsible for freeing it when it is no longer needed. This method relies on the constructor of hashEntryClass having identical parameters to those found in THashEntry.

create should gets the target class as the only parameter.

TMapIterator = class(tObject)
public
procedure next; virtual; abstract
procedure remove; virtual; abstract
function hasNext : boolean; virtual; abstract
function getKey : tComparable; virtual; abstract
function getValue : tObject; virtual; abstract
procedure setValue(value : tObject); virtual; abstract;
function validEntry : boolean; virtual; abstract
function isValid : boolean; virtual; abstract
property key : tComparable read getKey
property value : tObject read getValue write setValue

This is a base class for all map iterators. The functionality and most of the structure is taken from Java iterator, which is probably taken from somewhere else :). All methods are abstract.

next iterate to the next entry, if it exists

remove remove the current entry

hasNext is there a next entry?

validEntry is the entry valid? returns false if current entry no longer exists (e.g. after a call to remove) or the internal counter is invalid

isValid returns returns false if the internal mod counter is not the same as the mod counter of the hashTable

key is the read-only access to the key of the current entry. See getKey for the details of it's operation

value is the read / write access to the value of the entry. See setValue for the specifics

PHashEntryTable
This is a data structure that serves as the internal storage in THashTable. The only reason I mention it here is that it is defined differently for Delphi/Kylix and for FreePascal.
For delphi it is defined as
THashEntryTable = array of THashEntry;
pHashEntryTable = ^tHashEntryTable;

While for FreePascal it is defined simply as
pHashEntryTable = ^THashEntry;
The reason for this is that delphi has dynamic arrays, while freepascal does not (or does it?). However, freepascal allows pointers to be treated as arrays (much like in C), which in some respects is even better. This is the reason why you have to use -S2 switch when compiling this with freepascal compiler.

All access to the variables of this class should be done via function getNewEntryTable(size : integer) : pHashEntryTable, procedure freeEntryTable(table : pHashEntryTable; oldSize : integer), function arrayGet(arr : pHashEntryTable; index : integer) : tHashEntry and procedure arrayPut(arr : pHashEntryTable; index : integer; value : tHashEntry).
These functions and procedures, implemented separately for delphi and freepascal, are not published in the interface of the unit but can be if necessary. Note to self : instead of a type and 4 functions, create a class with constructors, destructors and a read/write property


THashTable = class(TObject)
protected
fTable : pHashEntryTable;
fEntryFactory : tHashEntryFactory;
fModCount : integer;
fCapacity : integer;
fThreshHold : integer;
fLoadFactor : real;
fCount : integer;
fOwnKeys : boolean;
function hashToIndex(key : tComparable) : integer;
procedure rehash; virtual;
procedure fSetValue(key : tComparable; value : tObject); virtual;
procedure clearTable(deleteValues : boolean);
public
function getIterator : tMapIterator; virtual;
function containsKey(key : tComparable) : boolean; virtual;
function containsValue(value : tObject) : boolean; virtual;
function getValue(key : tComparable) : tObject; virtual;
function setValue(key : tComparable; value : tObject) : boolean; virtual;
function remove(key : tComparable) : tObject; virtual;
function getCount : integer; virtual;
property values[key : tComparable] : tObject read getValue write fsetValue;
property count : integer read getCount;
{$IFNDEF FPC}
constructor create(initialcapacity : integer = 10; loadfactor : real = 0.75; entryfactory : tHashEntryFactory = nil; ownKeys : boolean = true);
{$ELSE FPC}
constructor create(initialcapacity : integer; loadfactor : real; entryfactory : tHashEntryFactory; ownKeys : boolean);
constructor create;
{$ENDIF}
destructor destroy; override;
procedure clear; virtual;
procedure deleteAll; virtual;

This is it, the class all the fuss is about. The hash table.

Nothing private in this class. Not a very good practice, I am quite sure. Oh well, sue me :) Don't pay any attention to the protected section if you do not intend to inherit from it.

fTable - the internal storage (see pHashEntryTable). You should not have to deal with it directly unless you're inheriting a class and making a major functionality change.

fEntryFactory - the class factory for THashEntry or its descendants (see tHashEntryFactory). It is initialized by the constructor from the parameter (if it is not nil) or by creating an instance if THashEntryFactory

fModCount - internal counter of modifications. This field provides a way to invalidate existing iterators after a change has been made to the hash table. The iterators (see THashTableIterator keep a copy of this value and check their validity by comparing it with the original. Every change the hash table should increment fModCount

fCapacity - the size of internal storage

fThreshHold - the number of entries after reaching which the table should be rehashed.

fLoadFactor - fThreshHold = fCapacity * fLoadFactor

fCount - count of entries in the hash table

fOwnKeys - if true, the hash table should delete the keys when it's done using them

hashToIndex - return the index into the fTable corresponding to the hash code of the key parameter

rehash - create a new hash with twice the capacity

fSetValue enters the (key, value) pair into the hash table. A procedure wrapper for function setValue

clearTable clears the table. Frees the keys if fOwnKeys is true. If parameter deleteValues is true, also frees the values

getIterator returns a new iterator. Returns a new instance of tHashTableIterator

containsKey returns true if key is in the hash table.

containsValue returns true if value is in the hash table. This function will only work if value objects are TComparable. If not, the matching value will not be found.

getValue returns the value corresponding to the key parameter, or nil if key is not in the hash table

setValue enters the pair (key, value) into the hash table. It returns true if the value was not replaced. Be careful when using this function - if the key is already in the hash table, the object passed in the value parameter will replace the original value. The hash table will not free the original value, it is your responsibility! If fOwnKeys is true and the key is already in the table, the incoming key object will be freed.

remove removes the (key, value) pair that corresponds to the key parameter from the hash table. It returns the value, if key was found in the hash table, or nil. If fOwnKeys is true, it will free the key of the entry, as well as the object passed as the parameter.

getCount returns the number of entries in the hash table

values read / write access to the keys and values. See getValue and setValue count returns the number of entries in the hash table

create is the constructor. Delphi allows default parameter values so it gets one constructor with all values initialized. FreePascal gets 2 versions, one with all parameters initialized to defaults and another with none of the parameters initialized.

destroy frees the hash table. It does not free values but does free the keys if fOwnKeys is true

clear clears the hash table. It does not free values but does free the keys if fOwnKeys is true

deleteAll clears the hash table. Unlike clear, it will free all values

tHashTableIterator = class(tMapIterator)
protected
fIndex : integer;
fEntry : tHashEntry;
fModCount : integer;
fIsRemoved : boolean;
fCurrent : integer;
fHashTable : tHashTable;
public
constructor create(table : tHashTable);
procedure next; override;
procedure remove; override;
function hasNext : boolean; override;
function getKey : tComparable; override;
function getValue : tObject; override;
procedure setValue(avalue : tObject); override;
function validEntry : boolean; override;
function isValid : boolean; override

This is a very simple implementation of TMapIterator.
All methods raise an exception if the iterator is no longer valid

fIndex - current entry's index in fHashTable.fTable

fEntry - current entry

fModCount - copy of fHashTable.fModCount, initialized in the constructor. When fHashTable is modified, it's fModCount is increased and the iterators become invalid

fIsRemoved - set to true by remove, set to false by the next call to next

fCurrent - number of the current entry

fHashTable - the hash table

create - create the iterator. To be called by the hash table. You shouldn't ever have to directly create the iterator, get a new instance by calling THashTable.getIterator

next - iterate to the next entry in the hash table (if there is a next entry).

remove - remove the current entry from the hash table. After a call to this method, current entry will no longer be valid.

hasNext - is there a next entry?

getKey - get the key of the current entry. If the entry is not valid, returns nil

getValue - get the value of the current entry. If the entry is not valid, returns nil

setValue - set the new value of the current entry. If the entry is not valid, throws an exception. Be careful with this function - it does not free the value you're replacing. So if the value is not kept track of somewhere else, free it here

validEntry - true so long as the current entry is not nil and has not just been removed. false after a call to remove or after creating a new iterator over an empty hash table

isValid - true so long as the iterator is in sync with the hash table (the hash table's mod counter's value is the same as fModCount stored in the iterator