TDynHashArray class

In unit DynHashArray

Name of the class that store all functions and data for an hashed array.

Declaration

pascal

TDynHashArray = class

Description

TDynHashArray is a class which is similar to TList which allows both pointers and objects to be maintained in its internal storage. It includes common methods like Add, Remove, Contains, First, Count and Clear. Because of its hashing nature, the add, remove, and find operations are 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.

Properties

`Count`	public	Number of elements stored in the set/array.
`FirstHashItem`	public	Pointer which provides access to the first TDynHashArrayItem stored in the hash array.
`MinCapacity`	public	The minimum number of items that will be allocated for an array.
`MaxCapacity`	public	The size of the array cannot be larger than this number.
`Capacity`	public	Space is allocated for this number of items.
`CustomHashFunction`	public	The pointer to the user-defined hash function.
`OwnerHashFunction`	public	The pointer to the user-defined hash function.
`Options`	public	Set of TDynHashArrayOption values enabled for the class instance.

Methods

`RebuildItems`	protected	Rebuilds the internal data structures.
`SaveCacheItem`	protected	Sets the cache.
`Create`	public	Constructor for the class instance.
`Destroy`	public	Destructor for the class instance.
`Add`	public	Adds an item to the set/array.
`Contains`	public	Returns True if the item is in the set.
`ContainsKey`	public	Returns True if the item is in the set.(through OnGetKeyForHashItem).
`Remove`	public	Removes an element from the set/hash array.
`Clear`	public	Removes all elements from the set/hash array.
`ClearCache`	public	Clears the FContainsCache cache.
`First`	public	Returns the first item or nil.
`IndexOf`	public	Returns calculated index from Item through OnGetKeyForHashItem.
`IndexOfKey`	public	Returns calculated index from Item.
`FindHashItem`	public	Finds an item as PDynHashArrayItem among all items.
`FindHashItemWithKey`	public	Finds an item as PDynHashArrayItem among all items (through OnGetKeyForHashItem).
`FindItemWithKey`	public	Finds an item among all items (through OnGetKeyForHashItem).
`GetHashItem`	public	Gets a link list from the "main" array FItems by index.
`Delete`	public	Deletes a PDynHashArrayItem from link list.
`AssignTo`	public	Copies all items into a given TList.
`ForEach`	public	Calls the specified function for each of the items in the hash array.
`SlowAlternativeHashMethod`	public	Another hash function that can be used.
`ConsistencyCheck`	public	Check if data in TDynHashArray are OK.
`WriteDebugReport`	public	Prints out essential data to aid debugging TDynHashArray.

Events

OnGetKeyForHashItem public User-defined function to obtain a key from an item.

An experiment, built from development snapshots. Not the official Free Pascal or Lazarus documentation.