How can I create a dictionary with a custom Equality comparer?

Viewed 560

To create a TObjectDictionary<ansiString, boolean> with a custom Equality compared I have to do:

TObjectDictionary<ansiString, boolean>.create(
  TDelegatedEqualityComparer<ansiString>.Create(
   function(const Left, Right: ansiString): Boolean
   begin
     Result := ALSameText(Left, Right);
   end,
   function(const Value: ansiString): Integer
   begin
     // !! here i want the default GetHashCode !! I don't want to write it myself 
   end))

So I need to give an implementation for the function Equals AND for the GetHashCode. But I want to give an implementation only for the Equals function. Is it possible?

3 Answers

But I want to give an implementation only for the Equals function. Is it possible?

No. You need to provide implementation to both EqualityComparison and Hasher functions.

In order to do that properly, you need to understand the purpose of those functions in dictionary implementation.

Equality Comparison

Dictionary is collection that stores key value pairs where key must be unique. That uniqueness of the key is ultimately determined by EqualityComparison function. Depending on the implementation of that function dictionary will store and update values associated with particular key.

For instance, dictionary with string keys may have requirement that distinct keys must be exact match, including case. For such implementation 'abc' and 'ABC' will be two distinct keys and you can store different values associated with each key. This is default implementation for Delphi dictionary with string keys.

abc -> true
ABC -> false

Storing above key value pairs will result with dictionary with two pairs. After you set 'ABC' key value, you can still retrieve unchanged 'abc' value that will be true.

However, dictionary with string keys may also be implemented in case insensitive manner where 'abc' and 'ABC' would be same keys. This is kind of implementation you have in your example.

abc -> true
ABC -> false 

Storing above key value pairs in case insensitive dictionary will result with dictionary containing only single pair. After you store ABC key value, original abc value will be lost, and reading value stored in both abc or ABC keys will yield false.

In theory you could have dictionary implementation where you don't need Hasher function.

Hasher

If the Hasher function is not needed, what is its purpose?

Hasher function is what makes retrieving values from dictionary fast. It divides stored key value pairs in buckets based on key hash value. So instead of going through all keys until particular key is found, searching for key will be only done in particular bucket and in that bucket equality comparison will be used to finally determine whether two keys match.

So Hasher function needs to result with same hash value for every unique key during the runtime of the program. Different keys can have same hash value - collisions are acceptable. Performance of the dictionary ultimately depends on the performance of the hash function and number of collisions (however, choosing the best hashing function that is different topic)

If you need to have case insensitive string dictionary, default hashing function will not work because different case in key can result with different hash values.

procedure Test;
var
  d: TDictionary<string, boolean>;
  b: Boolean;
begin
  d := TDictionary<string, boolean>.Create(
  TDelegatedEqualityComparer<string>.Construct(
   function(const Left, Right: string): Boolean
   begin
     Result := SameText(Left, Right);
   end,
   function(const Value: string): Integer
   begin
     Result := THashBobJenkins.GetHashValue(PChar(Value)^, Length(Value) * SizeOf(Char));
   end));

  d.AddOrSetValue('abc', true);
  d.AddOrSetValue('ABC', false);

  b := d.Items['abc'];
  Writeln(b); // TRUE 

  b := d.Items['ABC'];
  Writeln(b); // FALSE
end;

Running above code will output

TRUE 
FALSE 

which is not exactly what we want. We want that setting value for ABC key overrides value stored in abc key.

So how to solve that? What would be correct hasher function.

Since only condition that hasher function must satisfy is that equal keys must have same hash value, the simplest (dumbest) implementation would be just returning same fixed integer value for all keys - all keys will belong to same bucket.

Replacing the hasher function in previous example with following one will yield correct results

   function(const Value: string): Integer
   begin
     Result := 0;
   end));

However, such dumb hasher function will have negative impact on dictionary performance. Slightly better hasher function that will result with same hash value for case insensitive keys is returning string length instead of fixed value.

   function(const Value: string): Integer
   begin
     Result := Length(Value);
   end));

This is just one of possible hash functions that will work with case insensitive requirement. Finding better one ultimately depends on what will be typical key values - for instance, if all keys in the dictionary will have same length, then length based hasher function will perform just (actually, worse) as badly as the fixed value one.

TDictionary and TObjectDictionary require hashing of keys. And if you want to use TDelegatedEqualityComparer then you have to provide it with a function that generates a hash, that is just how it works.

However, if you don't want to write your own hashing code from scratch, you can leverage the RTL's native hashing for AnsiString, eg:

function(const Value: AnsiString): Integer
begin
  Result := TEqualityComparer<AnsiString>.Default.GetHashCode(Value);
end

Which will ultimately delegate to an internal function named GetHashCode_LString() that passes the AnsiString data to a BobJenkinsHash() function that is publicly accessible from the System.Generics.Defaults unit, so you could just call that function directly instead, eg:

function(const Value: AnsiString): Integer
begin
  Result := BobJenkinsHash(PAnsiChar(Value)^, Length(Value) * SizeOf(AnsiChar), 0);
end

Or, as the function's documentation says in XE8+:

Warning: BobJenkinsHash is deprecated. Please use Hash.THashBobJenkins.GetHashValue().

uses
  System.Hash; 

function(const Value: AnsiString): Integer
begin
  Result := THashBobJenkins.GetHashValue(PAnsiChar(Value)^, Length(Value) * SizeOf(AnsiChar)); 
end

But me I want to give an implementation only for the Equals function. Is it possible?

No. You have to provide a hash function. That's needed for a dictionary.

Related