Arief Sujatmiko on Blogspot: Januari 2026

As a Computer Science student I have learn a lot of algorithm that not only usable in programming but also in my daily life. For example, I save alot of time when using binary search for searching in ordered objects.

1. Hash Map

Hash Map using integer of hash function result of item's key to map object into bucket array. The object is mapped using modulo of hash value and bucket size as index in the bucket array. And if there is collision the item is added using linked list in the collided index. The item search is doing by calculate hash value of search key and using modulo to find index in the bucket array. And if index in bucket is occupied then continue to compare item's key with search key, if not equal then continue with items in the linked list until the key is equal, if all items is not equal then item is not found.

Using Hash Map is very fast for alot of items and is frequently searched but when new item is added and the bucket need to grow it need to rehash the entire bucket into new bucket.

This is an example of my Hash Map classes in Free Pascal:

type
IListIterator = interface
['{16585733-6438-4D58-A772-FC6811EB19BB}']
procedure First;
function Next: TObject;
procedure Delete;
end;
{ THashable }
THashable = class(TObject)
private
FNext__: THashable;
protected
FHash: Integer;
public
constructor Create;
function IsEqual(AKey: Pointer): Boolean; virtual;
property Next__: THashable read FNext__;
property Hash: Integer read FHash;
end;
{ THashMap }
THashMap = class(TObject)
private
FBucket: PObjectArray;
FCapacity: integer;
FCount: Integer;
procedure SetCapacity(NewCapacity: Integer);
public
function ObjectByKey(AKey: Pointer): THashable;
protected
procedure Grow; virtual;
function HashKey(AKey: Pointer): Integer; virtual;
property Capacity: integer read FCapacity write SetCapacity;
property Count: Integer read FCount;
public
destructor Destroy; override;
procedure Clear;
function GetObject(AKey: Pointer): THashable;
procedure Put(AItem: THashable);
procedure Remove(const AKey: Pointer);
function GetIterator: IListIterator;
end;
{ THashMapIterator }
THashMapIterator = class(TInterfacedObject, IListIterator)
private
FHashMap: THashMap;
FIndex: Integer;
FNode, FBefore: THashable;
FReread: Boolean;
public
constructor Create(AHashMap: THashMap);
procedure First;
function Next: TObject;
procedure Delete;
end;
{ THashable }
constructor THashable.Create;
begin
FHash := 0;
FNext__ := nil;
end;
function THashable.IsEqual(AKey: Pointer): Boolean;
begin
Result := False;
end;
{ THashMap }
procedure THashMap.Clear;
var
I: integer;
begin
if (FBucket <> nil) then
begin
for I := 0 to FCapacity - 1 do
begin
if (FBucket^[I] <> nil) then FreeAndNil(FBucket^[I]);
end;
FreeMem(FBucket);
FBucket := nil;
end;
FCapacity := 0;
FCount := 0;
end;
destructor THashMap.Destroy;
begin
Clear;
inherited;
end;
function THashMap.GetObject(AKey: Pointer): THashable;
var
P: THashable;
H: integer;
begin
if (FCount > 0) then
begin
H := HashKey(AKey);
P := THashable(FBucket^[H mod FCapacity]);
while ((P <> nil) and ((P.Hash <> H) or not P.IsEqual(AKey))) do
P := P.FNext__;
Result := P;
end
else
Result := nil;
end;
procedure THashMap.Grow;
var
Delta: Integer;
begin
if FCapacity > 64 then
Delta := FCapacity div 4
else if FCapacity > 8 then
Delta := 16
else
Delta := 4;
SetCapacity(FCapacity + Delta);
end;
function THashMap.HashKey(AKey: Pointer): Integer;
begin
Result := Integer(AKey);
end;
function THashMap.ObjectByKey(AKey: Pointer): THashable;
begin
Result := GetObject(AKey);
if (Result = nil) then
raise EListError.CreateFmt(SListItemNotFoundError,[IntToHex(Integer(AKey),8)]);
end;
procedure THashMap.Put(AItem: THashable);
var
I: integer;
begin
if (AItem = nil) then exit;
Inc(FCount);
if ((FCount * 4) div 3 > FCapacity) then Grow;
I := AItem.Hash mod FCapacity;
AItem.FNext__ := THashable(FBucket^[I]);
FBucket^[I] := AItem;
end;
procedure THashMap.Remove(const AKey: Pointer);
var
P, Q: THashable;
I, H: Integer;
begin
if (FCount > 0) then
begin
H := HashKey(AKey);
I := H mod FCapacity;
P := THashable(FBucket^[I]);
Q := nil;
while ((P <> nil) and (P.Hash <> H) and not P.IsEqual(AKey)) do
begin
Q := P;
P := P.FNext__;
end;
if (P <> nil) then
begin
if (Q = nil) then
FBucket^[I] := P.FNext__
else
Q.FNext__ := P.FNext__;
P.Free;
Dec(FCount);
end;
end;
end;
function THashMap.GetIterator: IListIterator;
begin
Result := THashMapIterator.Create(Self);
end;
procedure THashMap.SetCapacity(NewCapacity: Integer);
var
P, Q: THashable;
NewList: PObjectArray;
I, J: Integer;
begin
if ((NewCapacity = FCapacity) or (NewCapacity < FCount)) then exit;
if (NewCapacity > 0) then
begin
GetMem(NewList,NewCapacity*SizeOf(TObject));
FillChar(NewList^,NewCapacity*SizeOf(TObject),0);
for I := 0 to FCapacity - 1 do
begin
P := THashable(FBucket^[I]);
while (P <> nil) do
begin
Q := P;
P := P.FNext__;
J := Q.Hash mod NewCapacity;
Q.FNext__ := THashable(NewList^[J]);
NewList^[J] := Q;
end;
end;
end
else
NewList := nil;
if (FBucket <> nil) then FreeMem(FBucket);
FBucket := NewList;
FCapacity := NewCapacity;
end;
{ THashMapIterator }
constructor THashMapIterator.Create(AHashMap: THashMap);
begin
FHashMap := AHashMap;
FIndex := -1;
FNode := nil;
FBefore := nil;
FReread := False;
end;
procedure THashMapIterator.First;
begin
FIndex := -1;
FNode := nil;
FBefore := nil;
FReread := False;
end;
function THashMapIterator.Next: TObject;
begin
if (FReread) then
begin
FReread := False;
end
else begin
if (FNode <> nil) then
begin
FBefore := FNode;
FNode := FNode.FNext__;
end;
if (FNode = nil) then
begin
Inc(FIndex);
while ((FIndex < FHashMap.Capacity) and (FHashMap.FBucket^[FIndex] = nil)) do
Inc(FIndex);
if (FIndex < FHashMap.Capacity) then
FNode := THashable(FHashMap.FBucket^[FIndex])
else
FNode := nil;
FBefore := nil;
end;
end;
Result := FNode;
end;
procedure THashMapIterator.Delete;
var
P: THashable;
begin
if (FNode <> nil) then
begin
P := FNode;
if (FBefore <> nil) then
FBefore.FNext__ := P.FNext__
else
FHashMap.FBucket^[FIndex] := P.FNext__;
FNode := FNode.FNext__;
if (FNode = nil) then
begin
Inc(FIndex);
while ((FIndex < FHashMap.Capacity) and (FHashMap.FBucket^[FIndex] = nil)) do
Inc(FIndex);
if (FIndex < FHashMap.Capacity) then
FNode := THashable(FHashMap.FBucket^[FIndex])
else
FNode := nil;
FBefore := nil;
end;
FReread := True;
P.Free;
end;
end;
{ TNamedObject }
function TNamedObject.GetName: String;
begin
Result := FName;
end;
procedure TNamedObject.SetName(const Value: string);
begin
FName := Value;
FHash := HashName(Value);
end;
function TNamedObject.IsEqual(AKey: Pointer): Boolean;
begin
Result := SameText(FName, String(AKey));
end;

This is an example of Hash function used to map object using case insensitive name:

function HashName(const AName: string): integer;
var
I: integer;
C: Byte;
begin
Result := 0;
for I := 1 to Length(AName) do
begin
C := Byte(AName[I]);
if ((C >= Ord('a')) and (C <= Ord('z'))) then Dec(C,Ord('a')-Ord('A'));
Result := ((Result SHL 5) OR (Result AND $1F)) + C;
end;
Result := Result AND $7FFFFFFF;
end;

This an example of using the Hash Map class to map objects by case insensitive name:

type
{ TNamedObject }
TNamedObject = class(THashable)
private
FName: string;
protected
function GetName: String;
procedure SetName(const Value: string); virtual;
public
function IsEqual(AKey: Pointer): Boolean; override;
property Name: string read GetName write SetName;
end;
{ TNamedObjectMap }
TNamedObjectMap = class(THashMap)
protected
function HashKey(AKey: Pointer): Integer; override;
public
function GetObject(const AName: String): TNamedObject;
procedure Remove(const AName: string);
end;
{ TNamedObject }
function TNamedObject.GetName: String;
begin
Result := FName;
end;
procedure TNamedObject.SetName(const Value: string);
begin
FName := Value;
FHash := HashName(Value);
end;
function TNamedObject.IsEqual(AKey: Pointer): Boolean;
begin
Result := SameText(FName, String(AKey));
end;
{ TNamedObjectMap }
function TNamedObjectMap.HashKey(AKey: Pointer): Integer;
begin
Result := HashName(String(AKey));
end;
function TNamedObjectMap.GetObject(const AName: String): TNamedObject;
begin
Result := TNamedObject(inherited GetObject(Pointer(AName)));
end;
procedure TNamedObjectMap.Remove(const AName: string);
begin
inherited Remove(Pointer(AName));
end;

This is an example of name and row index search helper using Hash Map:

type
{ TNameIndexItem }
TNameIndexItem = class(THashable)
private
FKey: String;
FRow: Integer;
FData: Pointer;
public
constructor Create(const AKey: String; ARow: Integer; AData: Pointer=nil);
function IsEqual(AKey: Pointer): Boolean; override;
property Key: String read FKey;
property Row: Integer read FRow;
property Data: Pointer read FData;
end;
{ TNameIndex }
TNameIndex = class(THashMap)
protected
function HashKey(AKey: Pointer): Integer; override;
public
function GetObject(const AKey: String): TNameIndexItem;
procedure Remove(const AKey: String);
procedure PutRow(const AKey: String; ARow: Integer; AData: Pointer=nil);
function FindRow(const AKey: String): Integer;
function GetRowAndData(const AKey: String; var ARow: Integer;
var AData: Pointer): Boolean;
// procedure IndexTable(ATable: ITransportTable; const AColName: String);
end;
{ TNameIndexItem }
constructor TNameIndexItem.Create(const AKey: String; ARow: Integer;
AData: Pointer);
begin
FKey := AKey;
FHash := HashName(AKey);
FRow := ARow;
FData := AData;
end;
function TNameIndexItem.IsEqual(AKey: Pointer): Boolean;
begin
Result := SameText(FKey, String(AKey));
end;
{ TNameIndex }
function TNameIndex.FindRow(const AKey: String): Integer;
var
P: TNameIndexItem;
begin
P := GetObject(AKey);
if (P <> nil) then
Result := P.Row
else
Result := -1;
end;
function TNameIndex.GetRowAndData(const AKey: String; var ARow: Integer;
var AData: Pointer): Boolean;
var
P: TNameIndexItem;
begin
P := GetObject(AKey);
if (P <> nil) then
begin
ARow := P.Row;
AData := P.Data;
Result := True;
end
else
Result := False;
end;
function TNameIndex.GetObject(const AKey: String): TNameIndexItem;
begin
Result := TNameIndexItem(inherited GetObject(Pointer(AKey)));
end;
function TNameIndex.HashKey(AKey: Pointer): Integer;
begin
Result := HashName(String(AKey));
end;
//procedure TNameIndex.IndexTable(ATable: ITransportTable;
// const AColName: String);
//var
// i, col: Integer;
//begin
// if (ATable = nil) then
// exit;
// col := ATable.FindField(AColName);
// if (col < 0) then
// exit;
// Clear;
// for i := 0 to ATable.RowCount - 1 do
// PutRow(ATable.Cells[col,i].AsString, i);
//end;
procedure TNameIndex.PutRow(const AKey: String; ARow: Integer;
AData: Pointer);
begin
if (GetObject(AKey) = nil) then
begin
Put(TNameIndexItem.Create(AKey, ARow, AData));
end;
end;
procedure TNameIndex.Remove(const AKey: String);
begin
inherited Remove(Pointer(AKey));
end;

2. Hash Marking

Hash marking using integer of hash function result of item's key to mark list items. Because comparing an integer only need 1 cpu clock and comparing text need 1 cpu clock per character we can skip comparing entire key by first comparing only hash values and only if it is equal then we continue to compare the key.

This method is very effective if item's key is a string or large complex type such as struct and number of items is limited or frequently recreated. For very alot of items and is frequently searched using Hash Map is faster.

This is an example of using hash marking to search for an object in a linked list:

function TChain.GetObject(AKey: Pointer): THashable;
var
P: THashable;
H: Integer;
begin
P := FFirst;
H := HashKey(AKey);
while ((P <> nil) and ((P.Hash <> H) or not P.IsEqual(AKey))) do
P := P.FNext__;
Result := P;
end;

3. Binary Search

Binary Search work with ordered list by repeatly search the middle first and if not the equal then search the half part of the list that is possibly still cotains the items until the item is found or range start > range end.

This is an example of searching data using binary search:

function TIntegerList.IndexOfB(AItem: Integer): Integer;
var
Low,High,Mid: Integer;
begin
Result := -1;
Low := 0;
High := Count - 1;
Mid := (Low + High) div 2;
while (Low <= High) do
begin
if (Items[Mid] > AItem) then High := Mid - 1
else if (Items[Mid] < AItem) then Low := Mid + 1
else begin
Result := Mid;
exit;
end;
Mid := (Low + High) div 2;
end;
end;

Arief Sujatmiko on Blogspot

Kamis, 22 Januari 2026

Searching Algorithms That I Often Use

1. Hash Map

2. Hash Marking

3. Binary Search

Building New PC To Study LLM