DynHashArray unit

dynhasharray.pp extends the functionality of Pascal by offering alternative data structure: set like array (the order is not kept) with fast find/delete. Its size can change automatically during the execution of the program. The price is that it is somewhat slower than a number indexes access of an array.

This unit defines TDynHashArray, which is very similar to a TList, since it also stores pointer/objects.

It supports Add, Remove, Contains, First, Count and Clear.

Because of the hashing nature the operations adding, removing and finding is done in constant time on average.

Inner structure:

There are three parts:

• The array itself (FItems). Every entry is a pointer to the first TDynHashArrayItem of a list with the same hash index. The first item of every same index list is the list beginning and its IsOverflow flag is set to false. All other items are overflow items. To get all items with the same hash index, do a FindHashItem. Then search through all "Next" items until Next is nil or its IsOverflow flag is set to false.
• The items beginning with FFirstItem is a 2-way-connected list of TDynHashArrayItem. This list contains all used items.
• To reduce GetMem/FreeMem calls, free items are cached.

Issues:

The maximum capacity is the PrimeNumber. You can store more items, but the performance decreases. The best idea is to provide your own hash function.

Important: Items in the TDynHashArray must not change their key. When changing the key of an item, remove it and add it after the change.

dynhasharray.pp is part of the LazUtils package.

Classes and records

EDynHashArrayException	class	Raised if index is invalid in IndexOfKey.
TDynHashArray	class	Name of the class that store all functions and data for an hashed array.
TDynHashArrayItem	record	Record type with pointers to the current, previous, and next has items in a linked list.
TDynHashArrayItemMemManager	class	Custom memory manager for TDynHashArrayItem instances.

Types

PDynHashArrayItem	type	Pointer to a TDynHashArrayItem instance.
TDynHashArrayOption	enumeration	Options for how this class should work.
TDynHashArrayOptions	set	Set type used to store values from TDynHashArrayOption.
THashFunction	procedure type	Type for hash function.
TOnEachHashItem	procedure type	Defines a Boolean function type used to enumerate hash items in TDynHashArray.
TOnGetKeyForHashItem	procedure type	Defines a Pointer function type used to get the key value for a hash item in TDynHashArray.
TOwnerHashFunction	procedure type	Defines a hash function implemented as an object procedure.

Constants

ItemMemManager

constant

A small memory manager.

Uses

• Classes
• SysUtils
• LazLoggerBase