Skip to content

THashTable

Jump to bottom
Ivan Semenkov edited this page Feb 5, 2021 · 3 revisions

Table of contents

About

A hash table stores a set of values which can be addressed by a key. Given the key, the corresponding value can be looked up quickly.

uses
  container.hashtable, utils.functor;
  
type
  generic THashTable<K, V, KeyBinaryCompareFunctor> = class

KeyBinaryCompareFunctor is based on utils.functor.TBinaryFunctor interface and used to compare two keys.

TOptionalValue

If macro {$USE_OPTIONAL} is defined, then all methods return a TOptionalValue wrapper, otherwise V.

uses
  utils.optional;

type
  TOptionalValue = {$IFDEF FPC}specialize{$ENDIF} TOptional<V>;

For non-existent values, returns a empty TOptionalValue if defined or an EKeyNotExistsException is thrown.

type
  {$IFNDEF USE_OPTIONAL}
  EKeyNotExistsException = class(Exception);
  {$ENDIF}

Create

A new hash table can be created by call its constructor.

constructor Create (HashFunc : THashTableHashFunc);

HashTableFunc is a function that generate a hash key for a THashTable value.

Hash functions

Unit container.hashtable contains next hash functions:

function HashPointer(location : Pointer) : Cardinal;

Generate a hash key for a pointer. The value pointed at by the pointer is not used, only the pointer itself.

function HashInteger(location : Integer) : Cardinal;

Generate a hash key for an integer. The value is used to generate the key.

function HashString(location : String) : Cardinal;

Generate a hash key from a string. This is the djb2 string hash function.

function HashStringNoCase(location : String) : Cardinal;

Generate a hash key from a string, ignoring the case of letters. This is the djb2 string hash function.

Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  
  FreeAndNil(hash);
end;

Insert

Insert a value into a hash table, overwriting any existing entry using the same key.

function Insert (Key : K; Value : V) : Boolean;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  hash.Insert(1, 'one');
  
  FreeAndNil(hash);
end;

Remove

Remove a value from a hash table. Return false if no node with the specified key was found in the tree, true if a node with the specified key was removed.

function Remove (Key : K) : Boolean;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  hash.Remove(1);
  
  FreeAndNil(hash);
end;

Search

Search

Look up a value in a hash table by key.

function Search (Key : K) : {$IFNDEF USE_OPTIONAL}V{$ELSE}TOptionalValue{$ENDIF};

If value not exists returns empty TOptionalValue or raise EKeyNotExistsException.

Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  hash.Search(1);
  
  FreeAndNil(hash);
end;

SearchDefault

Look up a value in a hash table by key. Return default value if Key not exists.

function SearchDefault (Key : K; ADefault : V) : V;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  hash.SearchDefault(1, 'none');
  
  FreeAndNil(hash);
end;

NumEntries

Retrieve the number of entries in a hash table.

function NumEntries : Cardinal;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  writeln(hash.NumEntries);
  
  FreeAndNil(hash);
end;

IsEmpty

Return true if container is empty.

function IsEmpty : Boolean;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  if hash.IsEmpty then
    ;
  
  FreeAndNil(hash);
end;

Iterate

It is possible to iterate for THashTable values using in operator. Each value would present as THashTable.TIterator object.

uses
  container.hashtable, utils.functor;
  
type
  generic THashTable<K, V, KeyBinaryCompareFunctor> = class
  type
  	TIterator = class({$IFDEF FPC}specialize{$ENDIF}
        TForwardIterator<TKeyValuePair, TIterator>)
  end;

TForwardIterator is a abstract class which provide interface for iterable object that can moves to forward side.

Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  iterator : TIntStrHashTable.TIterator;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  for iterator in hash do
    ;
  
  FreeAndNil(hash);
end;

FirstEntry

Retrive the iterator for first entry in a AVL tree.

function FirstEntry : TIterator
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  iterator : TIntStrHashTable.TIterator;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  iterator := hash.FirstEntry;
  
  FreeAndNil(hash);
end;

TIterator

HasValue

Return true if iterator has correct value.

function HasValue : Boolean;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  iterator : TIntStrHashTable.TIterator;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  iterator := hash.FirstEntry;
  while iterator.HasValue do
    ;
  
  FreeAndNil(hash);
end;
Next

Retrieve the iterator for next entry in an array list.

function Next : TIterator;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  iterator : TIntStrHashTable.TIterator;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  iterator := hash.FirstEntry;
  while iterator.HasValue do
  begin
  
    iterator := iterator.Next;
  end;
  
  FreeAndNil(hash);
end;
Key

Return key value.

property Key : K;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  iterator : TIntStrHashTable.TIterator;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  iterator := hash.FirstEntry;
  while iterator.HasValue do
  begin
  	writeln(iterator.Key);
    iterator := iterator.Next;
  end;
  
  FreeAndNil(hash);
end;
Value

Return value.

property Value : V;
Example
uses
  container.hashtable, utils.functor;
  
type
  TIntStrHashTable = {$IFDEF FPC}type specialize{$ENDIF} THashTable<Integer, String, TCompareFunctorInteger>;

var
  hash : TIntStrHashTable;
  iterator : TIntStrHashTable.TIterator;
  
begin
  hash := TIntStrHashTable.Create(@HashInteger);
  iterator := hash.FirstEntry;
  while iterator.HasValue do
  begin
  	writeln(iterator.Value);
    iterator := iterator.Next;
  end;
  
  FreeAndNil(hash);
end;
Clone this wiki locally